Организация параллельных вычислений

Для алгоритма Шелла может быть предложен параллельный аналог метода (см., например, [[51]]), если топология коммуникационной сети может быть эффективно представлена в виде N-мерного гиперкуба (т. е. количество процессоров равно p = 2N). Выполнение сортировки в таком случае может быть разделено на два последовательных этапа. На первом этапе (N итераций) осуществляется взаимодействие процессоров, являющихся соседними в структуре гиперкуба (но эти процессоры могут оказаться далекими при линейной нумерации; для установления соответствия двух систем нумерации процессоров может быть использован, как и ранее, код Грея – см. лекцию 3). Формирование пар процессоров, взаимодействующих между собой при выполнении операции "сравнить и разделить", может быть обеспечено при помощи следующего простого правила – на каждой итерации i, 0i<N, парными становятся процессоры, у которых различие в битовых представлениях их номеров имеется только в позиции N-i.

Второй этап состоит в реализации обычных итераций параллельного алгоритма чет-нечетной перестановки. Итерации данного этапа выполняются до прекращения фактического изменения сортируемого набора, и, тем самым, общее количество L таких итераций может быть различным – от 2 до p.

На рис. 9.3 показан пример сортировки массива из 16 элементов с помощью рассмотренного способа (процессоры показаны кружками, номера процессоров даны в битовом представлении). Нужно заметить, что данные оказываются упорядоченными уже после первого этапа и нет необходимости выполнять чет-нечетную перестановку.

Рис. 9.3. Пример работы алгоритма Шелла для 4 процессоров

С учетом представленного описания параллельного варианта алгоритма Шелла базовая подзадача для организации параллельных вычислений, как и ранее (см. п. 9.3.3), может быть определена на основе операции "сравнить и разделить". Как результат, количество подзадач всегда совпадает с числом имеющихся процессоров (размер блоков данных в подзадачах равен n/p) и не возникает проблемы масштабирования. Распределение блоков упорядочиваемого набора данных по процессорам должно быть выбрано с учетом возможности эффективного выполнения операций "сравнить и разделить" при представлении топологии сети передачи данных в виде гиперкуба.

Алгоритм сортировки с использованием регулярного набора образцов (the parallel sorting by regular sampling) также является обобщением метода быстрой сортировки (см., например, в [[63]]).

Упорядочивание данных в соответствии с данным вариантом алгоритма быстрой сортировки осуществляется в ходе выполнения следующих четырех этапов:

на первом этапе сортировки производится упорядочивание имеющихся на процессорах блоков. Данная операция может быть выполнена каждым процессором независимо друг от друга при помощи обычного алгоритма быстрой сортировки; далее каждый процессор формирует набор из элементов своих блоков с индексами 0, m, 2m, ...,(p-1)m, где m=n/p2;
на втором этапе выполнения алгоритма все сформированные на процессорах наборы данных собираются на одном из процессоров системы и объединяются в ходе последовательного слияния в одно упорядоченное множество. Далее из полученного множества значений из элементов с индексами

формируется новый набор ведущих элементов, который передается всем используемым процессорам. В завершение этапа каждый процессор выполняет разделение своего блока на p частей с использованием полученного набора ведущих значений;
на третьем этапе сортировки каждый процессор осуществляет рассылку выделенных ранее частей своего блока всем остальным процессорам системы; рассылка выполняется в соответствии с порядком нумерации – часть j, 0j<p, каждого блока пересылается процессору с номером j;
на четвертом этапе выполнения алгоритма каждый процессор выполняет слияние p полученных частей в один отсортированный блок.

По завершении четвертого этапа исходный набор данных становится отсортированным.

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

Рис. 9.11. Пример работы алгоритма сортировки с использованием регулярного набора образцов

Параллельное обобщение алгоритма быстрой сортировки (см., например, [63]) наиболее простым способом может быть получено, если топология коммуникационной сети может быть эффективно представлена в виде N-мерного гиперкуба (т.е. p=2N). Пусть, как и ранее, исходный набор данных распределен между процессорами блоками одинакового размера n/p; результирующее расположение блоков должно соответствовать нумерации процессоров гиперкуба. Возможный способ выполнения первой итерации параллельного метода при таких условиях может состоять в следующем:

выбрать каким-либо образом ведущий элемент и разослать его по всем процессорам системы (например, в качестве ведущего элемента можно взять среднее арифметическое элементов, расположенных на выбранном ведущем процессоре);
разделить на каждом процессоре имеющийся блок данных на две части с использованием полученного ведущего элемента;
образовать пары процессоров, для которых битовое представление номеров отличается только в позиции N, и осуществить взаимообмен данными между этими процессорами.

В результате выполнения такой итерации сортировки исходный набор оказывается разделенным на две части, одна из которых (со значениями меньшими, чем значение ведущего элемента) располагается на процессорах, в битовом представлении номеров которых бит N равен 0. Таких процессоров всего p/2, и, таким образом, исходный N-мерный гиперкуб также оказывается разделенным на два гиперкуба размерности N-1. К этим подгиперкубам, в свою очередь, может быть параллельно применена описанная выше процедура. После N-кратного повторения подобных итераций для завершения сортировки достаточно упорядочить блоки данных, получившиеся на каждом отдельном процессоре вычислительной системы.

Для пояснения на рис. 9.6 представлен пример упорядочивания данных при n=16, p=4 (т.е. блок каждого процессора содержит 4 элемента). На этом рисунке процессоры изображены в виде прямоугольников, внутри которых показано содержимое упорядочиваемых блоков данных; значения блоков приводятся в начале и при завершении каждой итерации сортировки. Взаимодействующие пары процессоров соединены двунаправленными стрелками. Для разделения данных выбирались наилучшие значения ведущих элементов: на первой итерации для всех процессоров использовалось значение 0, на второй итерации для пары процессоров 0, 1 ведущий элемент равен -5, для пары процессоров 2, 3 это значение было принято равным 4.

Рис. 9.6. Пример упорядочивания данных параллельным методом быстрой сортировки (без результатов локальной сортировки блоков)

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

Содержание раздела