Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Лекция 11. Параллельные методы сортировки Образовательный комплекс Введение в методы параллельного программирования Гергель В.П., профессор, д.т.н. Кафедра математического обеспечения ЭВМ

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 2 из 52 Постановка задачи Принципы распараллеливания Пузырьковая сортировка Сортировка Шелла Параллельная быстрая сортировка Обобщенная быстрая сортировка Сортировка с использованием регулярного набора образцов Заключение Содержание

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 3 из 52 Постановка задачи Сортировка является одной из типовых проблем обработки данных и обычно понимается как задача размещения элементов неупорядоченного набора значений в порядке монотонного возрастания или убывания

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 4 из 52 Базовая операция – "сравнить и переставить" (compare- exchange) Принципы распараллеливания… // базовая операция сортировки if ( A[i] > A[j] ) { temp = A[i]; A[i] = A[j]; A[j] = temp; } Последовательное применение данной операции позволяет упорядочить данные В способах выбора пар значений для сравнения проявляется различие алгоритмов сортировки

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 5 из 52 Принципы распараллеливания… Параллельное обобщение базовой операции при p = n ( каждый процессор содержит 1 элемент данных ): выполнить взаимообмен имеющихся на процессорах и значений (с сохранением на этих процессорах исходных элементов), сравнить на каждом процессоре и получившиеся одинаковые пары значений (, ) и по результатам сравнения разделить данные между процессорами – на одном процессоре (например, ) оставить меньший элемент, на другом процессоре (т.е. ) запомнить большее значение пары

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 6 из 52 Принципы распараллеливания… Результат выполнения параллельного алгоритма: имеющиеся на процессорах данные упорядочены, порядок распределения данных по процессорам соответствует линейному порядку нумерации (т.е. значение элемента на процессоре меньше или равно значения элемента на процессоре, где ).

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 7 из 52 Параллельное обобщение базовой операции при p < n (каждый процессор содержит блок данных размера ): упорядочить блок на каждом процессоре в начале сортировки, выполнить взаимообмен блоков между процессорами и, объединить блоки и на каждом процессоре в один отсортированный блок с помощью операции слияния, разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре, а другую часть (с большими значениями соответственно) – на процессоре Рассмотренная процедура обычно именуется в литературе как операция " сравнить и разделить" (compare-split). Принципы распараллеливания…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 8 из 52 Трудоемкость вычислений имеет порядок O(n 2 ) В прямом виде сложен для распараллеливания Пузырьковая сортировка: последовательный алгоритм // Последовательный алгоритм пузырьковой сортировки BubbleSort(double A[], int n) { for (i=0; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 9 из 52 Пузырьковая сортировка: алгоритм чет-нечетной перестановки… Вводятся два разных правила выполнения итераций метода: на всех нечетных итерациях сравниваются пары (a 1, a 2 ), (a 3, a 4 ),..., (a n-1,a n ) (при четном n), на четных итерациях обрабатываются элементы (a 2, a 3 ), (a 4, a 5 ),..., (a n-2,a n-1 ).

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 10 из 52 Пузырьковая сортировка: алгоритм чет-нечетной перестановки/// // Последовательный алгоритм чет-нечетной перестановки OddEvenSort(double A[], int n) { for (i=1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 11 из 52 Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки… // Параллельный алгоритм чет-нечетной перестановки ParallelOddEvenSort ( double A[], int n ) { int id = GetProcId(); // номер процесса int np = GetProcNum(); // количество процессов for ( int i=0; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 12 из 52 Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки… и тип итерации Процессоры 1234 Исходные данные нечет (1,2),(3.4) чет (2,3) нечет (1,2),(3.4) чет (2,3)

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 13 из 52 Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки… Анализ эффективности: –Общая оценка показателей ускорения и эффективности

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 14 из 52 Анализ эффективности ( уточненные оценки ): - Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет: - Длительность выполнения операции сбора данных при использовании модели Хокни определяется при помощи следующего выражения: Общее время выполнения параллельного алгоритма составляет Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 15 из 52 Результаты вычислительных экспериментов… –Сравнение теоретических оценок и экспериментальных данных Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 16 из 52 Результаты вычислительных экспериментов: –Ускорение вычислений Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 17 из 52 Параллельный вариант алгоритма работает медленнее исходного последовательного метода пузырьковой сортировки: – объем передаваемых данных между процессорами является достаточно большим и сопоставим с количеством выполняемых вычислительных операций, – этот дисбаланс объема вычислений и сложности операций передачи данных увеличивается с ростом числа процессоров Пузырьковая сортировка: параллельный алгоритм чет-нечетной перестановки

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 18 из 52 Общая идея сортировки Шелла состоит в сравнении на начальных стадиях сортировки пар значений, располагаемых достаточно далеко друг от друга в упорядочиваемом наборе данных (сортировка таких пар обычно требует большого количества перестановок, если используется сравнение только соседних элементов): –На первом шаге алгоритма происходит упорядочивание элементов n/2 пар (a i, a n/2+i ) для 1 i n/2, –На втором шаге упорядочиваются элементы в n/4 группах из четырех элементов (a i, a n/4+1, a n/2+1, a 3n/4+1 ) для 1 i n/4 и т.д., –На последнем шаге упорядочиваются элементы сразу во всем массиве (a 1, a 2,…, a n ). Общее количество итераций алгоритма Шелла является равным log 2 n Сортировка Шелла: последовательный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 19 из 52 Трудоемкость вычислений имеет порядок O(nlog 2 n). Сортировка Шелла: последовательный алгоритм // Последовательный алгоритм сортировки Шелла ShellSort ( double A[], int n ){ int incr = n/2; while( incr > 0 ) { for ( int i=incr+1; i 0 ) if ( A[j] > A[j+incr] ){ swap(A[j], A[j+incr]); j = j - incr; } else j = 0; } incr = incr/2; }

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 20 из 52 Сортировка Шелла: параллельный алгоритм… Пусть топология коммуникационной сети имеет вид N-мерного гиперкуба (т.е. количество процессоров равно p=2 N ). Действия алгоритма состоят в следующем : Первый этап (N итераций): выполнение операции "сравнить и разделить" для каждой пары процессоров в гиперкубе. Формирование пар процессоров происходит по правилу – на каждой итерации i, 0 i < N, парными становятся процессоры, у которых различие в битовых представлении их номеров имеется только в позиции N-i, Второй этап: реализация обычных итераций параллельного алгоритма чет-нечетной перестановки. Итерации выполняются до прекращения фактического изменения сортируемого набора. Общее их количество L может быть различным - от 2 до p.

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 21 из 52 Сортировка Шелла: параллельный алгоритм… Пример:

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 22 из 52 Анализ эффективности: –Общая оценка показателей ускорения и эффективности Сортировка Шелла: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 23 из 52 Анализ эффективности ( уточненные оценки ): - Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет - Длительность выполнения операции сбора данных при использовании модели Хокни определяется при помощи следующего выражения: Общее время выполнения параллельного алгоритма составляет Сортировка Шелла: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 24 из 52 Результаты вычислительных экспериментов… –Сравнение теоретических оценок и экспериментальных данных Сортировка Шелла: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 25 из 52 Результаты вычислительных экспериментов: –Ускорение вычислений Сортировка Шелла: параллельный алгоритм

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 26 из 52 Быстрая сортировка: последовательный алгоритм… Алгоритм быстрой сортировки, предложенной Хоаром (Hoare C.A.R.), основывается на последовательном разделении сортируемого набора данных на блоки меньшего размера таким образом, что между значениями разных блоков обеспечивается отношение упорядоченности (для любой пары блоков все значения одного из этих блоков не превышают значений другого блока): – На первой итерации метода осуществляется деление исходного набора данных на первые две части – для организации такого деления выбирается некоторый ведущий элемент и все значения набора, меньшие ведущего элемента, переносятся в первый формируемый блок, все остальные значения образуют второй блок набора, – На второй итерации сортировки описанные правила применяются рекурсивно для обоих сформированных блоков и т.д. При оптимальном выборе ведущих элементов после выполнения log 2 n итераций исходный массив данных оказывается упорядоченным.

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 27 из 52 Быстрая сортировка: последовательный алгоритм… // Последовательный алгоритм быстрой сортировки QuickSort(double A[], int i1, int i2) { if ( i1 < i2 ){ double pivot = A[i1]; int is = i1; for ( int i = i1+1; i

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 28 из 52 Быстрая сортировка: параллельный алгоритм… Пусть топология коммуникационной сети имеет вид N-мерного гиперкуба (т.е. количество процессоров равно p=2 N ). Действия алгоритма состоят в следующем: выбрать каким-либо образом ведущий элемент и разослать его по всем процессорам системы (например, в качестве ведущего элемента можно взять среднее арифметическое элементов, расположенных на ведущем процессоре), разделить на каждом процессоре имеющийся блок данных на две части с использованием полученного ведущего элемента, образовать пары процессоров, для которых битовое представление номеров отличается только в позиции N, и осуществить взаимообмен данными между этими процессорами; в результате таких пересылок данных на процессорах, для которых в битовом представлении номера бит позиции N равен 0, должны оказаться части блоков со значениями, меньшими ведущего элемента; процессоры с номерами, в которых бит N равен 1, должны собрать, соответственно, все значения данных, превышающие значения ведущего элемента, перейти к подгиперкубам меньшей размерности и повторить описанную выше процедуру

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 29 из 52 Анализ эффективности: –Общая оценка показателей ускорения и эффективности Быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 30 из 52 Анализ эффективности ( уточненные оценки ): - Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет - Длительность выполнения операции сбора данных при использовании модели Хокни определяется при помощи следующего выражения: Общее время выполнения параллельного алгоритма составляет Быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 31 из 52 Результаты вычислительных экспериментов… –Сравнение теоретических оценок и экспериментальных данных Быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 32 из 52 Результаты вычислительных экспериментов: –Ускорение вычислений Быстрая сортировка: параллельный алгоритм

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 33 из 52 Обобщенная быстрая сортировка: параллельный алгоритм… Основное отличие от предыдущего алгоритма – конкретный способ выбора ведущего элемента Сортировка блоков выполняется в самом начале выполнения вычислений. В качестве ведущего выбирается средний элемент какого-либо блока (например, на первом процессоре вычислительной системы). Выбираемый подобным образом ведущий элемент в отдельных случаях может оказаться более близок к настоящему среднему значению всего сортируемого набора, чем какое-либо другое произвольно выбранное значение Для поддержки упорядоченности в ходе вычислений процессоры выполняют операцию слияния частей блоков, получаемых после разделения

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 34 из 52 Анализ эффективности: –Общая оценка показателей ускорения и эффективности Обобщенная быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 35 из 52 Анализ эффективности ( уточненные оценки ): - Время выполнения параллельного алгоритма, связанное непосредственно с вычислениями, составляет - Длительность выполнения операции сбора данных при использовании модели Хокни определяется при помощи следующего выражения: Общее время выполнения параллельного алгоритма составляет Обобщенная быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 36 из 52 Программная реализация… –Первый этап: Инициализация и распределение данных между процессорами: получение размера сортируемого массива, определение исходных данных для сортируемого массива, пересылка исходных данных между процессорами вынесено в отдельную функцию DataDistribution. Программа Обобщенная быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 37 из 52 Программная реализация: –Второй этап: выполнение итераций параллельной обобщенной быстрой сортировки реализовано в функции ParallelHyperQuickSort Программа Обобщенная быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 38 из 52 Результаты вычислительных экспериментов… –Сравнение теоретических оценок и экспериментальных данных Обобщенная быстрая сортировка: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 39 из 52 Результаты вычислительных экспериментов: –Ускорение вычислений Обобщенная быстрая сортировка: параллельный алгоритм

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 40 из 52 Первый этап: упорядочивание блоков каждым процессором независимо друг от друга при помощи обычного алгоритма быстрой сортировки; далее каждый процессор формирует набор из элементов своих блоков с индексами 0, m, 2m,…,(p-1)m, где m=n/p 2, Второй этап: все сформированные на процессорах наборы данных собираются на одном из процессоров системы и объединяются в ходе последовательного сливания в одно упорядоченное множество; из полученного множества значений из элементов с индексами формируется набор ведущих элементов, который передается всем процессорам; в завершение этапа каждый процессор выполняет разделение своего блока на p частей с использованием полученного набора ведущих значений, Третий этап: каждый процессор рассылает выделенные ранее части своего блока всем остальным процессорам системы в соответствии с порядком нумерации - часть j, 0 j

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 41 из 52 Сортировка с использованием регулярного набора образцов: параллельный алгоритм… Пример: (p=3)

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 42 из 52 Анализ эффективности: –Общая оценка показателей ускорения и эффективности Сортировка с использованием регулярного набора образцов: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 43 из 52 Анализ эффективности ( уточненные оценки ): - Время выполнения первого этапа параллельного алгоритма: Общее время выполнения параллельного алгоритма: - Время выполнения второго этапа параллельного алгоритма: - Время выполнения третьего этапа параллельного алгоритма: - Время выполнения четвертого этапа параллельного алгоритма: Сортировка с использованием регулярного набора образцов: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 44 из 52 Результаты вычислительных экспериментов… –Сравнение теоретических оценок и экспериментальных данных Сортировка с использованием регулярного набора образцов: параллельный алгоритм…

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 45 из 52 Результаты вычислительных экспериментов: –Ускорение вычислений Сортировка с использованием регулярного набора образцов: параллельный алгоритм

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 46 из 52 Заключение Рассмотрены способы параллельного выполнения трех широко известных метода упорядочения данных: –Алгоритм пузырьковой сортировки, –Сортировка Шелла, –Быстрая сортировка Для алгоритма быстрой сортировки приведены две дополнительные модификации: –Обобщенная быстрая сортировка, –Сортировка с использованием регулярного набора образцов Представлена программная реализация метода обобщенной быстрой сортировки Использованный порядок изложения параллельных методов сортировки можно рассматривать как пример процесса последовательного совершенствования параллельных вычислений с целью улучшения показателей ускорения и эффективности

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 47 из 52 Вопросы для обсуждения В чем состоит параллельное обобщение базовой операции сортировки? Какие оценки трудоемкости последовательных вычислений следует использовать при определении показателей ускорения и эффективности? Какой из рассмотренных алгоритмов обладает наилучшими показателями ускорения и эффективности? Какие схемы выбора ведущих элементов могут быть предложены для алгоритма быстрой сортировки? Какие операции передачи данных необходимы в параллельных алгоритмах сортировки?

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 48 из 52 Темы заданий для самостоятельной работы Выполните реализацию параллельного варианта алгоритма пузырьковой сортировки. Выполните реализацию сортировки Шелла. Разработайте параллельный вариант для алгоритма сортировки слиянием. Постройте теоретические оценки времени работы алгоритма. Проведите вычислительные эксперименты. Сравните результаты реальных экспериментов с полученными теоретическими оценками

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 49 из 52 Гергель В.П. (2007). Теория и практика параллельных вычислений. – М.: Интернет-Университет, БИНОМ. Лаборатория знаний. Akl, S. G. (1985). Parallel Sorting Algorithms. – Orlando, FL: Academic Press Knuth, D.E. (1973). The Art of Computer Programming: Sorting and Searching. – Reading, MA: Addison-Wesley. Кормен Т., Лейзерсон Ч., Ривест Р. (1999). Алгоритмы: построение и анализ. – М.: МЦНТО. Kumar V., Grama, A., Gupta, A., Karypis, G. (1994). Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc. (2nd edn., 2003) Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. – New York, NY: McGraw-Hill. Литература

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 50 из 52 Параллельные методы обработки графов Следующая тема

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 51 из 52 Гергель В.П., профессор, д.т.н., руководитель Гришагин В.А., доцент, к.ф.м.н. Сысоев А.В., ассистент (раздел 1) Лабутин Д.Ю., ассистент (система ПараЛаб) Абросимова О.Н., ассистент (раздел 10) Гергель А.В., аспирант (раздел 12) Лабутина А.А., магистр (разделы 7,8,9, система ПараЛаб) Сенин А.В. (раздел 11) Авторский коллектив

Н.Новгород, 2005 г. Основы параллельных вычислений: Сортировка © Гергель В.П. 52 из 52 Целью проекта является создание образовательного комплекса "Многопроцессорные вычислительные системы и параллельное программирование", обеспечивающий рассмотрение вопросов параллельных вычислений, предусматриваемых рекомендациями Computing Curricula 2001 Международных организаций IEEE-CS и ACM. Данный образовательный комплекс может быть использован для обучения на начальном этапе подготовки специалистов в области информатики, вычислительной техники и информационных технологий. Образовательный комплекс включает учебный курс "Введение в методы параллельного программирования" и лабораторный практикум "Методы и технологии разработки параллельных программ", что позволяет органично сочетать фундаментальное образование в области программирования и практическое обучение методам разработки масштабного программного обеспечения для решения сложных вычислительно-трудоемких задач на высокопроизводительных вычислительных системах. Проект выполнялся в Нижегородском государственном университете им. Н.И. Лобачевского на кафедре математического обеспечения ЭВМ факультета вычислительной математики и кибернетики ( Выполнение проекта осуществлялось при поддержке компании Microsoft. О проекте