Сети сортировки: различия между версиями

[непроверенная версия]

Версия 20:29, 9 мая 2019

Содержание

1 Свойства и структура алгоритма
2 Программная реализация алгоритма
3 Литература

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

К первым следует отнести сеть сортировки простой вставкой, сеть нечетно-четной перестановки, сеть четно-нечетного слияния Бетчера и сеть битонной сортировки. К немасштабируемым следует отнести ряд оптимальных, с точки зрения времени выполнения сортировки, сетей для 6, 9, 10, 12 и 16 элементов^[1].

1.2 Математическое описание алгоритма

Исходные данные: одномерный массив [math]A[/math], содержащий [math]n[/math] элементов, [math]|A|=n[/math].

Вычисляемые данные: упорядоченный массив [math]B=sort(A)[/math].

1.2.1 Постановка задачи

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

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

Без ограничения общности рассмотрим задачу расположения [math]n[/math] элементов массива в порядке неубывания. Пусть [math]B^i[/math] – [math]i[/math]-ый элемент массива [math]B[/math]. Тогда, массив [math]B[/math] упорядочен, если выполняется соотношение:

[math]B^i\le B^j[/math] , для любых допустимых [math]i,j[/math], при [math]i \lt j[/math].

Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями [math]B_i[/math], [math]B=\bigcup\limits_{i} B_i[/math].

Пусть [math]B_i^k[/math] – [math]k[/math]-ый элемент [math]i[/math]-го фрагмента массива [math]B[/math] (фрагмента, расположенного на процессоре [math]i[/math]).

Тогда, массив [math]B[/math] упорядочен, если выполняются следующие соотношения:

[math]B_i^k\le B_i^j[/math] , для любых [math]i[/math], при [math]k \lt j[/math],

[math]B_i^k\le B_l^j[/math] , для любых [math]k,j[/math], при [math]i \lt l[/math].

1.2.2 Временные материалы (в таком виде их не следует включать)

Будем предполагать, что исходный массив [math]A[/math] распределен по процессорам некоторыми порциями [math]A_i[/math], где [math]i[/math] – номер процессора, [math]A=\bigcup\limits_{i} A_i[/math]. Потребуем, чтобы размеры всех порций были одинаковы: [math]|A_i|=|A_j|, |A_i|=|B_i|[/math], для любых [math]i,j[/math]. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива [math]A[/math]. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.

Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся оценкой вычислительной сложности (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка [math]O(n^2)[/math] операций, где [math]n[/math] – число сортируемых элементов, что неприемлемо при больших значениях n, либо [math]O(n log_2(n))[/math] операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за [math]O(nk)[/math] операций, где [math]k[/math] – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

1.10 Свойства алгоритма

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.2.1 Локальность реализации алгоритма

2.2.1.1 Структура обращений в память и качественная оценка локальности

Профиль доступа к памяти

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

↑ Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.

Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с.

[1] Кнут Д.Э. Искусство программирования. – Т.3. – Сортировка и поиск 2-е изд.: Пер. с английского – М.: Вильямс, 2001. – 824 с.

[1]

@@ Строка 22: / Строка 22: @@
 Тогда, массив <math>B</math> упорядочен, если выполняется соотношение<nowiki>:</nowiki>
-<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i<j</math>.
+<math>B^i\le B^j</math> , для любых допустимых <math>i,j</math>, при <math>i \lt j</math>.
 Уточним, что будет пониматься под упорядоченным массивом в том случае, когда его части распределены по нескольким процессорам. Пусть элементы массива распределены по процессорам некоторыми порциями <math>B_i</math>, <math>B=\bigcup\limits_{i} B_i</math>.
@@ Строка 30: / Строка 30: @@
 Тогда, массив <math>B</math> упорядочен, если выполняются следующие соотношения<nowiki>:</nowiki>
-<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k<j</math>,
+<math>B_i^k\le B_i^j</math> , для любых <math>i</math>, при <math>k \lt j</math>,
-<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i<l</math>.
+<math>B_i^k\le B_l^j</math> , для любых <math>k,j</math>, при <math>i \lt l</math>.
 ==== Временные материалы (в таком виде их не следует включать) ====
 Будем предполагать, что исходный массив <math>A</math> распределен по процессорам некоторыми порциями <math>A_i</math>, где <math>i</math> – номер процессора, <math>A=\bigcup\limits_{i} A_i</math>.
-Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|B_i|</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.
+Потребуем, чтобы размеры всех порций были одинаковы<nowiki>:</nowiki> <math>|A_i|=|A_j|, |A_i|=|B_i|</math>, для любых <math>i,j</math>. Как будет показано ниже, только при выполнении этого условия, рассматриваемые далее параллельные алгоритмы, основанные на сетях сортировки, дают верный результат для любого исходного расположения элементов массива <math>A</math>. В случае, если число элементов сортируемого массива не делится нацело на число процессоров, можно дополнить исходный массив фиктивными элементами, исключив их после окончания сортировки.
 Можно указать три больших класса последовательных алгоритмов сортировки, отличающихся [[оценкой вычислительной сложности]] (видом зависимости числа выполняемых операций от размера массива). Алгоритмы сортировки, основанные на сравнении элементов, имеют сложность порядка <math>O(n^2)</math> операций, где <math>n</math> – число сортируемых элементов, что неприемлемо при больших значениях n, либо <math>O(n log_2(n))</math> операций. Эти методы отличаются универсальностью. Последние из них взяты за основу «наилучшего» последовательного алгоритма сортировки. Известны методы поразрядной сортировки, обеспечивающие выполнение сортировки за <math>O(nk)</math> операций, где <math>k</math> – разрядность сортируемых данных, но их реализация существенно зависит от типа сортируемых данных, в связи с чем далее они не рассматриваются.