Параллельная сортировка

Параллельную сортировку можно осуществлять различными способами. В этом параграфе подробно рассматриваются два способа и обсуждаются в общем другие подходы, которые не вошли в данный учебник.

Сортировка на линейных сетях

Начнем с метода сортировки, основанного на линейной конфигурации сети. Если число процессоров равно числу сортируемых значений, то сортировку можно осуществить, передавая сети в каждом цикле одно значение. Первый процессор читает поданное значение, сравнивает его с текущим и передает большее значение своему соседу. Остальные процессоры делают то же самое: сохраняют меньшее из двух значений и пересылают большее следующему звену в цепочке. Получаем следующий алгоритм:

for / = 1 to N - 1 do

занести следующее значение в М[)

Parallel Start

Pj читает Mj] в Current for k= toj- 1 do

P[k] читает M[k] в New if Current > New then

Pk пишет Current в M[k + 1]

Current = New

else

P[k] пишет New в M[k + 1] end if endfor к Parallel End

занести следующее значение в М[ 1]

Parallel Start

P[j] читает Mj] в Current for k= to j - 1 do

P[k] читает M[k] в New if Current > New then P[k пишет Current в M[k + 1]

Current = New

else

P[k пишет New в M[k + 1] end if endfor к Parallel End Parallel Start

for j = 1 to N - 1 do

Pj] пишет Current в m endfor j Parallel End

Перед каждым параллельным проходом очередной элемент списка (если в списке еще остались элементы) заносится в первую ячейку памяти. В самом начале это значение просто читается первым процессором. На последующих этапах первый процессор читает следующее значение в переменную New, сравнивает ее со значением переменной Current в процессоре, а затем записывает большее из двух значений во вторую ячейку памяти. Во внешнем цикле for имеется два параллельных блока, поскольку при каждом проходе этого цикла к сортировке привлекается очередной процессор; в первом блоке этот процессор читает первое для себя значение, а во втором блоке он вовлекается в процесс сравнения. В самом конце все значения опять записываются в память.

На рис. 9.4 и 9.5 изображена работа этого алгоритма на входном списке 15, 18, 13, 12, 17, 11, 19, 16, 14.

Параллельная сортировка на линейной сети

Рис. 9.4. Параллельная сортировка на линейной сети

Видно, что на этапе А первый элемент списка заносится в память и его читает первый процессор. На этапе В в память заносится второе значение, оно сравнивается с текущим значением в процессоре Р1? и большее из двух значений заносится в М2. На этапе С в Mi заносится третий элемент списка, который сравнивается с текущим значением в процессоре Рь а процессор Р2 производит первую операцию чтения из М2. На шаге D сравнение могут делать уже оба процессора Р и Р2. Так, на каждом «нечетном» шаге новый процессор собирается выполнить первое чтение, а на «четном» шаге все активные процессоры выполняют сравнения.

Из рис. 9.4 и 9.5 видно, что сортировка поданного списка требует 16 параллельных шагов, и один шаг нужен для записи результата. В общем случае алгоритм выполняет 2 * (N - 1) + 1, т. е. 0(N), действий. В работе принимают участие N процессоров, поэтому стоимость алгоритма равна 0(N2) - она такая же, как и у самых медленных сортировок.

Параллельная сортировка на линейной сети

Рис. 9.5. Параллельная сортировка на линейной сети

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >