1.1. Сортировка данных
Общая схема параллельных вычислений при сортировке данных (см. раздел 3 пособия) состоит в разделении исходного упорядочиваемого набора на блоки и их распределения между процессорами, в ходе сортировки блоки пересылаются между процессорами и содержащиеся в них данные сравниваются между собой для упорядочения. Результирующий (отсортированный) набор, как правило, также разделен между процессорами; при этом для систематизации такого разделения для процессоров вводится та или иная система последовательной нумерации и обычно требуется, чтобы при завершении сортировки значения, располагаемые на процессорах с меньшими номерами, не превышали значений процессоров с большими номерами.
В системе ПараЛаб в качестве методов упорядочения данных представлены пузырьковая сортировка, сортировка Шелла, быстрая сортировка.
1.1.1. Алгоритм пузырьковой сортировки
Напомним кратко общую схему данного метода упорядочения данных [1]. Алгоритм основан на применении базовой операции “сравнить и переставить” (compare-exchange), состоящей в сравнении той или иной пары значений из сортируемого набора данных и перестановки этих значений, если их порядок не соответствует условиям сортировки:
// операция “сравнить и переставить”
if ( a[i] > a[j] ) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
На первой итерации алгоритма осуществляется последовательное сравнение всех соседних элементов; в результате прохода по упорядочиваемому набору данных в последнем (верхнем) элементе оказывается максимальное значение (“всплывание пузырька”); далее для продолжения сортировки этот уже упорядоченный элемент не рассматривается и действия алгоритма повторяются:
// пузырьковая сортировка
for ( i=1; i<n; i++ ){
for ( j=0; j<n-i; j++ )
<сравнить и переставить элементы (a[j],a[j+1])>
}
Алгоритм пузырьковой сортировки в прямом виде достаточно сложен для распараллеливания: сравнение пар соседних элементов происходит строго последовательно. Для организации параллельных вычислений обычно используется модификация алгоритма пузырьковой сортировки – метод чет-нечетной перестановки [23]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами, т.е. на всех нечетных итерациях сравниваются пары:
(a1, a2), (a3, a4),…, (an-1, an) (при четном n),
на четных итерациях обрабатываются элементы
(a2, a3), (a4, a5),…, (an-2, an-1) (при нечетном n).
После n-кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным.
Параллельное обобщение этого алгоритма не вызывает затруднений, так как сравнение элементов в парах происходит независимо и может выполняться одновременно. Сначала рассмотрим схему вычислений, когда на каждый процессор приходится один элемент исходного массива. Предположим, что процессоры соединены в кольцо и элементы ai расположены на процессорах pi (i=1, 2,…, n). Тогда сравнение пары значений ai и ai+1 1≤ i <n, располагаемых на процессорах Pi и Pi+1 соответственно, можно организовать следующим образом:
- выполнить взаимообмен имеющихся на процессорах Pi и Pi+1 значений (с сохранением на этих процессорах исходных элементов);
- сравнить на каждом процессоре Pi и Pi+1 получившиеся одинаковые пары значений ai и ai+1; результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т.е Pi+1) запоминает для дальней обработки большее значение пары
ai =min(ai , ai+1 ), ai+1 =max(ai , ai+1).
Рассмотренная параллельная схема может быть надлежащим образом адаптирована и для случая p<n, когда количество процессоров является меньшим числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера n/p) сортируемого набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (предварительная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров Pi и Pi+1 для совместного упорядочения содержимого блоков Ai и Ai+1 и может быть осуществлено следующим образом:
- выполнить взаимообмен блоков между процессорами Pi и Pi+1;
- объединить блоки Ai и Ai+1 на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);
- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре Pi, а другую часть (с большими значениями соответственно) – на процессоре Pi+1.
Следует отметить, что сформированные в результате такой процедуры блоки на процессорах Pi и Pi+1 совпадают по размеру с исходными блоками Ai и Ai+1 и все значения, расположенные на процессоре Pi, являются меньшими значений на процессоре Pi+1.
Рассмотренная процедура обычно именуется в литературе как операция “сравнить и разделить” (compare-split). Для пояснения такого параллельного способа сортировки на рис. 1 приведен пример упорядочения данных при n=8, p=4 (т.е. блок значений на каждом процессоре содержит n/p =2 элементов). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняется операция “сравнить и разделить”; взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.
Вычислительная трудоемкость алгоритма определяется выражением:
Tp =6 (n/p)2 +2n
Первая часть выражения определяет сложность начальной сортировки блоков с использованием алгоритма пузырьковой сортировки. Вторая часть отражает суммарную сложность всех итераций алгоритма чет-нечетной перестановки блоков (для слияния двух упорядоченных блоков размера n/p необходимо 2(n/p) операций).
