Теория и практика параллельных вычислений
Краткий обзор лекции
В лекции рассматривается часто встречающаяся в приложениях задача упорядочения данных, для решения которой в рамках данного учебного материала выбраны широко известные алгоритмы пузырьковой сортировки, сортировки Шелла и быстрой сортировки. При изложении методов сортировки основное внимание уделяется возможным способам распараллеливания алгоритмов, анализу эффективности и сравнению получаемых теоретических оценок с результатами выполненных вычислительных экспериментов.
Алгоритм пузырьковой сортировки (подраздел 9.3) в исходном виде практически не поддается распараллеливанию в силу последовательного выполнения основных итераций метода. Для введения необходимого параллелизма рассматривается обобщенный вариант алгоритма – метод чет-нечетной перестановки. Суть обобщения состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода в зависимости от четности номера итерации сортировки. Сравнения пар значений упорядочиваемого набора данных на итерациях метода чет-нечетной перестановки являются независимыми и могут быть выполнены параллельно.
Для алгоритма Шелла (подраздел 9.4) рассматривается схема распараллеливания при представлении топологии сети в виде гиперкуба. При таком представлении топологии оказывается возможной организация взаимодействия процессоров, расположенных далеко друг от друга при линейной нумерации. Как правило, такая организация вычислений позволяет уменьшить количество выполняемых итераций алгоритма сортировки.
Для алгоритма быстрой сортировки (подраздел 9.5) приводятся три схемы распараллеливания. Первые две схемы также основываются на представлении топологии сети в виде гиперкуба. Основная итерация вычислений состоит в выборе одним из процессоров ведущего элемента, который далее рассылается всем остальным процессорам гиперкуба. После получения ведущего элемента процессоры проводят разделение своих блоков, и получаемые части блоков передаются между попарно связанными процессорами. В результате выполнения подобной итерации исходный гиперкуб оказывается разделенным на 2 гиперкуба меньшей размерности, к которым, в свою очередь, может быть применена приведенная выше схема вычислений.
При применении алгоритма быстрой сортировки одним из основных моментов является правильность выбора ведущего элемента. Оптимальная стратегия состоит в выборе такого значения ведущего элемента, при котором данные на процессорах разделяются на части одинакового размера. В общем случае при произвольно сгенерированных исходных данных достижение такой ситуации является достаточно сложной задачей. В первой схеме предлагается выбирать ведущий элемент, например, как среднее арифметическое элементов на управляющем процессоре. Во второй схеме (обобщенный алгоритм быстрой сортировки) данные на каждом процессоре предварительно упорядочиваются с тем, чтобы взять средний элемент блока данных как ведущее значение. Третья схема (сортировка с использованием регулярного набора образцов) распараллеливания алгоритма быстрой сортировки основывается на многоуровневой схеме формирования множества ведущих элементов. Такой подход может быть применен для произвольного количества процессоров, позволяет избежать множества пересылок данных и приводит, как правило, к более равномерному распределению данных между процессорами.
