Paralab. Описание параллельных методов решения сложных вычислительных задач

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]. Суть модификации состоит в том, что в алгоритм сортировки вводятся два разных правила выполнения итераций метода – в зависимости от четности или нечетности номера итерации сортировки для обработки выбираются элементы с четными или нечетными индексами соответственно, сравнение выделяемых значений всегда осуществляется с их правыми соседними элементами, т.е. на всех нечетных итерациях сравниваются пары:

(a₁, a₂), (a₃, a₄),…, (a_n-1, a_n) (при четном n),

на четных итерациях обрабатываются элементы

(a₂, a₃), (a₄, a₅),…, (a_n-2, a_n-1) (при нечетном n).

После n-кратного повторения подобных итераций сортировки исходный набор данных оказывается упорядоченным.

Параллельное обобщение этого алгоритма не вызывает затруднений, так как сравнение элементов в парах происходит независимо и может выполняться одновременно. Сначала рассмотрим схему вычислений, когда на каждый процессор приходится один элемент исходного массива. Предположим, что процессоры соединены  в кольцо и элементы a_i расположены на процессорах p_i (i=1, 2,..., n). Тогда сравнение пары значений a_i и a_i+1 1≤ i <n, располагаемых на процессорах P_i и P_i+1 соответственно, можно организовать следующим образом:

- выполнить взаимообмен имеющихся на процессорах P_i и P_i+1 значений (с сохранением на этих процессорах исходных элементов);

- сравнить на каждом процессоре P_i и P_i+1 получившиеся одинаковые пары значений ai и a_i+1; результаты сравнения используются для разделения данных между процессорами – на одном процессоре (например, Pi) остается меньший элемент, другой процессор (т.е P_i+1) запоминает для дальней обработки большее значение пары

a_i =min(a_i , a_i+1 ),    a_i+1 =max(a_i , a_i+1).

Рассмотренная параллельная схема может быть надлежащим образом адаптирована и для случая p<n, когда количество процессоров является меньшим числа упорядочиваемых значений. В данной ситуации каждый процессор будет содержать уже не единственное значение, а часть (блок размера n/p) сортируемого набора данных. Эти блоки обычно упорядочиваются в самом начале сортировки на каждом процессоре в отдельности при помощи какого-либо быстрого алгоритма (предварительная стадия параллельной сортировки). Далее, следуя схеме одноэлементного сравнения, взаимодействие пары процессоров P_i и P_i+1 для совместного упорядочения содержимого блоков A_i и A_i+1 и может быть осуществлено следующим образом:

- выполнить взаимообмен блоков между процессорами P_i и P_i+1;

- объединить блоки A_i и A_i+1 на каждом процессоре в один отсортированный блок двойного размера (при исходной упорядоченности блоков и процедура их объединения сводится к быстрой операции слияния упорядоченных наборов данных);

- разделить полученный двойной блок на две равные части и оставить одну из этих частей (например, с меньшими значениями данных) на процессоре P_i, а другую часть (с большими значениями соответственно) – на процессоре P_i+1.

Следует отметить, что сформированные в результате такой процедуры блоки на процессорах P_i и P_i+1 совпадают по размеру с исходными блоками A_i и A_i+1 и все значения, расположенные на процессоре P_i, являются меньшими значений на процессоре P_i+1.

Рассмотренная процедура обычно именуется в литературе как операция "сравнить и разделить" (compare-split). Для пояснения такого параллельного способа сортировки на рис. 1 приведен пример упорядочения данных при n=8, p=4 (т.е. блок значений на каждом процессоре содержит n/p =2 элементов). В первом столбце таблицы приводится номер и тип итерации метода, перечисляются пары процессоров, для которых параллельно выполняется операция "сравнить и разделить"; взаимодействующие пары процессоров выделены в таблице двойной рамкой. Для каждого шага сортировки показано состояние упорядочиваемого набора данных до и после выполнения итерации.

Вычислительная трудоемкость алгоритма определяется выражением:

Tp  =6 (n/p)² +2n

Первая часть выражения определяет сложность начальной сортировки блоков с использованием алгоритма пузырьковой сортировки. Вторая часть отражает суммарную сложность всех итераций алгоритма чет-нечетной перестановки блоков (для слияния двух упорядоченных блоков размера n/p необходимо 2(n/p) операций).

Download Lab_3