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

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

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

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

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

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

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

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(n log n).

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

СУПЕРКОМПЬЮТЕРА

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

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

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

---

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

Потоки команд	Потоки данных	Категория	Примеры
1	1	SISD	Классическая машина фон Неймана
1	Много	SIMD	Векторный суперкомпьютер
Много	1	MISD	Отказоустойчивые системы
Много	Много	MIMD	Кластеры

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

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

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

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

с

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

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

---

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

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

Для NUMA-машины характерен, напротив, неоднородный доступ к памяти. Обычно процессоры имеют один модуль памяти, обращение к которому быстрее, чем к модулям, принадлежащим другим процессорам. Поэтому важно, где находится программа и данные, с которыми она работает. Если в системе отсутствует кэш, то есть доступ к удалённой памяти не замаскирован кэшем, то такую систему называют NC-NUMA (No Caching NUMA - NUMA без кэширования). Если присутствуют кэши и система поддержки их согласованности, то такую систему называют CC-NUMA (Coherent Cache NUMA - 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
«Политехник - РСК ПетаСтрим»	MPP
«Политехник - NUMA»	CC-NUMA

---

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

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

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

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

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

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

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

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

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

---

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

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

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

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

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

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

2.4. Способы построения параллельной программы

Наиболее распространённым языком программирования в области HPC- систем являются языки Си и С++ [7]. В рамках реализации компонента будет использована модель с общей памятью. Модель передачи сообщений должна быть использована для более высокоуровневых компонент системы, разработка которых является предметом дальнейшей работы.

Существует несколько способов создания многопоточных программ, реализуемые компиляторами [18, 19]. В рамках модели с общей памятью среди них следует выделить следующие:

• Фреймворк Intel Threading Building Blocks [0]
• Расширение OpenMP [1]
• Расширение Intel Cilk Plus [2]
• Расширение OpenACC [2]
• Средства языка С++ (std: :thread) [4]
• Использование потоков операционной системы PThreads [5]

Выбор фреймворка обуславливается требованиями к реализации поставленной задачи [2].

Стандарт OpenACC используется для гетерогенного программирования, то есть программирования с использованием центрального и графического процессоров. В настоящей работе не рассматривается возможность использования графических процессоров в решении задачи, поэтому предпочтение отдаётся другим расширениям и фреймворкам.

Использование встроенных средств распараллеливания, предоставляемых языком С++ или операционной системой, позволяет реализовывать специфичные низкоуровневые задачи. Реализация компараторов и процедур сортировки не относится к таким задачам.

Intel Cilk Plus и OpenMP имеют существенное преимущество перед другими расширениями и фреймворками. Основная идея этих расширений - преобразование последовательной программы в параллельную путём использования директив компилятора или особых версий операторов (например, оператора цикла). Как известно, разработка параллельных программ сопряжена с рядом трудностей, в основе которых лежит смена парадигмы. OpenMP считается переносимым решением [2], что более предпочтительно в исследовании возможностей системы сортировки.

---