Файл: Алгоритмы сортировки данных (Алгоритмы сортировки).pdf

j-=step;

}

}

step = step / 2;

}

}

1.6.Быстрая сортировка

Быстрая сортировка (англ. quicksort) — широко известный алгоритм сортировки, разработанный английским информатиком Чарльзом Хоаром. Даёт в среднем O(nlogn) сравнений при сортировке n элементов. В худшем случае, однако, получается O(n2) сравнений. Обычно на практике быстрая сортировка значительно быстрее, чем другие алгоритмы с оценкой O(nlogn), по причине того, что внутренний цикл алгоритма может быть эффективно реализован почти на любой архитектуре, и на большинстве реальных данных можно найти решения, которые минимизируют вероятность того, что понадобится квадратичное время.

Интересно, что Хоар разработал этот метод применительно к машинному переводу: дело в том, что в то время словарь хранился на магнитной ленте, и если отсортировать все слова в тексте, их переводы можно получить за один прогон ленты.

Быстрая сортировка использует стратегию «разделяй и властвуй». Шаги алгоритма таковы:

Выбираем в массиве некоторый элемент, который будем называть опорным элементом.

Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы, меньшие или равные опорному элементу, оказались слева от него, а все элементы, большие опорного — справа от него.

Рекурсивно сортируем подсписки, лежащие слева и справа от опорного элемента.

Базой рекурсии являются списки, состоящие из одного или двух элементов, которые уже отсортированы. Алгоритм всегда завершается, поскольку за каждую итерацию он ставит по крайней мере один элемент на его окончательное место.

сортировка данные алгоритм внутренний

C#:

int partition (int[] array, int start, int end)

{

int marker = start;

for (int i = start; i <= end; i++)

{

if (array[i] <= array[end])

{

int temp = array[marker]; // swap

array[marker] = array[i];

array[i] = temp;

marker += 1;

}

}

return marker - 1;

}

void quicksort (int[] array, int start, int end)

{

if (start >= end)

{

return;

}

int pivot = partition (array, start, end);

quicksort (array, start, pivot-1);

quicksort (array, pivot+1, end);

}

Улучшения

При выборе опорного элемента из данного диапазона случайным образом, худший случай становится очень маловероятным и ожидаемое время выполнения алгоритма сортировки - O(nlogn).

ГЛАВА 2. СИСТЕМА СОРТИРОВКИ НА БАЗЕ АРХИТЕКТУРЫ СУПЕРКОМПЬЮТЕРА

При разработке программного обеспечения для HPC-системы, нельзя не учитывать особенности её реализации, в частности архитектуру вычислительной машины. Разработчику следует понимать способы коммутации вычислительных узлов для эффективной работы с памятью. Организация вычислительной машины может существенно влиять на работу конкретного приложения. Это обуславливает проблемы, связанные с переносимостью программного обеспечения для сложных HPC-систем. Поэтому на начальном этапе разработки следует классифицировать вычислительную машину.

2.1. Классификация параллельных компьютерных систем

За последние годы было построено и предложено множество видов параллельных компьютерных систем. Исследователи пытались произвести классификацию таких систем [13, 14], но наиболее полной классификации до сих пор нет [12]. Чаще всего используется классификация Флинна или классификации на её основе (табл. 2.1).

Таблица 2.1 Классификация параллельных компьютерных систем по Флинну [12]

Основу классификации Флинна [13] составляют понятия потоков команд и потоков данных. В SISD-архитектуре один поток выполнения работает с одним потоком данных. Компьютеры с SIMD-архитектурой, как правило, имеют один управляющий модуль, который назначает инструкцию выполнения для всех потоков выполнения, каждый из которых имеет собственный поток данных. Архитектура MISDподразумевает выполнение различных операцийнад одними и теми же данными.

К вычислительным машинам с MIMD-архитектурой относят мультипроцессорные машины, многоядерные и многопоточные процессоры и компьютерные кластеры (рис. 2.1). Безусловно, СКЦ «Политехнический» следует классифицировать как вычислительную систему с MIMD- архитектурой.

Рис. 2.1 Схема MIMD-архитектуры

На практике такой классификации недостаточно: классификация Флинна не даёт разработчику понимание системы с точки зрения организации памяти. Существует более подробная классификация, учитывающая такие особенности [12] (рис. 2.2). MIMD-машины разделяют на две категории: мультипроцессоры и мультикомпьютеры. К мультипроцессорам относят системы с общей памятью, к мультикомпьютерам – машины с обменом сообщениями.

с

Рис. 2.2 Классификация параллельных систем с учётом организации памяти [12]

Мультикомпьютеры не имеют общей памяти на архитектурном уровне. Можно сказать, что операционная система процессора, входящего в мультикомпьютер, может получить доступ к памяти другого процессора только посредством обмена сообщениями. Существует две категории мультикомпьютеров: MPP (MassiveParallelProcessor- процессор с массовым параллелизмом) и COW (ClusterofWorkstation - кластер рабочих станций). MPPхарактерна для дорогостоящих компьютеров, состоящих из большого числа процессоров, соединённых высокоскоростной коммутационной сетью. К COWотносят набор вычислительных устройств, использующих некоторую коммутационную технологию. Принципиальной разницы между такими машинами нет: последние менее производительные и намного дешевле [12].

Мультипроцессоры подразделяются на три категории по доступу к общей памяти: UMA (UniformMemoryAccess- однородный доступ к памяти), NonUniformMemoryAccess(неоднородный доступ к памяти) и COMA (CacheOnlyMemoryAccess - доступ только к кэш-памяти). Такая классификация имеет смысл, потому что память в мультипроцессорах, как правило, имеет несколько модулей [12].

В UMA-машинах процессоры имеют одинаковое время доступа к общей памяти. Другими словами: слово из общей памяти читается с той же скоростью, что и любое другое слово. При этом самые быстрые обращения намеренно замедляются, поэтому для программиста доступ к памяти является однородным.

Для NUMA-машины характерен, напротив, неоднородный доступ к памяти. Обычно процессоры имеют один модуль памяти, обращение к которому быстрее, чем к модулям, принадлежащим другим процессорам. Поэтому важно, где находится программа и данные, с которыми она работает. Если в системе отсутствует кэш, то есть доступ к удалённой памяти не замаскирован кэшем, то такую систему называют NC-NUMA (NoCachingNUMA- NUMAбез кэширования). Если присутствуют кэши и система поддержки их согласованности, то такую систему называют CC-NUMA (CoherentCacheNUMA- NUMAс кэш-когерентной памятью).

Доступ к памяти в COMA-машинах также не является однородным, но по другим причинам. COMA-машины представляют память процессора как его кэш-память:запрашиваемые строки данных перемещаются междупроцессорами по требованию и фактически не имеют «домашнего» расположения.

СКЦ «Политехнический» состоит из нескольких СК [15]. Системы СКЦ работают с общей системой хранения данных и имеют единую систему управления и мониторинга. В вычислительном центре представлены три суперкомпьютера:

• «Политехник - РСК Торнадо» - кластер с пиковой производительностью 943 тфлопс, содержащий 668 двухпроцессорных узлов Intel Xeon E5 2687 v3
• «Политехник - РСК ПетаСтрим» - массивно-параллельный суперкомпьютер с пиковой производительностью 291 тфлопс на базе сопроцессоров Intel Xeon Phi.

• «Политехник - NUMA» - массивно-параллельная система Numascaleс кэш-когерентной глобально адресуемой памятью с пиковой производительностью 30 тфлопс.

Суперкомпьютеры «Политехник - РСК Торнадо» и «Политехник - РСК ПетаСтрим» попадают под классификацию мультикомпьютеров с высокоскоростной коммутационной сетью, то есть относятся к категории MPP(табл. 2.2). Соответственно кластер Numascaleпопадает под категорию мультипроцессора с категорией CC-NUMA.

Таблица 2.2 Классификация СК СКЦ «Политехнический»

Для решения поставленной задачи наибольший интерес представляет система из категории MPP, для которых характерны огромные объёмы ввода- вывода [12]. Предложенный подход (п. 1.5) всё же имеет ограничения по масштабированию, так как в его основе лежат сортировочные сети. Таким образом, для реализации поставленной задачи следует использовать СК «Политехник - РСК Торнадо» (далее РСК Торнадо).

2.2. Особенности архитектуры суперкомпьютера, используемые в системахсортировки

Распространённой топологией коммутационной сети является топология дерева. Её основная проблема - пропускная способность сечения сети соответствует пропускной способности линии связи [12]. Наиболее узким местом в такой сети является верхушка дерева, у которой, как правило, наблюдается основной трафик. Для решения этой проблемы увеличивают пропускную способность сечения путём увеличения пропускной способности верхних линий связи. Такая топология называется толстым деревом (рис. 2.3).

По такой топологии объединены узлы кластера РСК Торнадо линиями связи InfiniBandFDR[15].

При построении сортирующей системы необходимо учесть топологию кластера для повышения скорости выполнения задачи. Рассмотрим прототип сортирующей системы для кластера с топологией толстого дерева.

Пусть имеется большой массив данных. Распределим фрагменты массива по первому уровню топологии. Пусть фрагменты массива в узлах сортируются, некоторым образом. Построим на базе узлов этого уровня сортировочную сеть с компаратором, операнды которого - фрагменты массива. Построение такой сети возможно.

Пусть первоначальная сортировка фрагментовосуществляется путём разбиения фрагмента массива на фрагменты меньшего размера, которые передаются на следующий уровень топологии для создания сортировочной подсети фрагментов. Аналогично вычисление компаратора осуществляется на нижестоящих уровнях топологии.

На таких принципахможно построить систему сортировки, адаптированную под древовидную топологию (рис. 2.4).

Рис. 2.4 Архитектура сети сортировки на базе топологии толстого дерева

В работе реализован частный случай базового компонента системы сортировки. (рис. 2.5), на основе которого будет возможно построение всей системы: сортировка массива с использованием пары узлов - процессоров IntelXeonE5-2697 v3 (14 ядер, 2.6 ГГц).

2.3. Требования к базовому компоненту системы сортировки

Компонент должен работать в соответствии с принципами со следующими принципами :

• Компонент осуществляет сортировку, разделяя исходный массив на фрагменты, с помощью сортировочной сети на базе компаратора, операндами которого являются подпоследовательности,

• Предварительная сортировка фрагментов инварианта относительно алгоритма сортировки: будь то последовательный или параллельный алгоритм,
• Сортировка эффективно распараллелена, то есть загрузка потоков выполнения должна быть равномерной.

Рис. 2.5 Архитектура базового компонента системы с процессорами IntelXeonE5-2697 v3 (14 ядер)