100 200

DO 200 CDNC FOR all (I,J)e{1 IslO.I£js10> C(I.J) = 0 DO 100 SEQ FOR Ke{1sKs10}

c(i.j)=c(i.J)+a(i;k).b(k.j)

COrmNUE CONTINUE

Параллельный алгоритм сортировки

Рассмотрим задачу сортировки п целых чисел или ключей Предположим, что имеется п процессоров Pi, Р, . . ., Р„. В каждом из них помещен один ключ. Не теряя общности, предположим, что целые числа tj, ii, . . ., in представляют собой первые п натуральных чисел. Рис. 5.5.8 иллюстрирует одну из возможных конфигураций для п=8.

Рис. 5.5.8. Восемь параллельных процессоров для упорядочения целых чисел 1.2,... ,8 при заданном начальном расположении.

Каждому процессору Р разрешено связываться и обмениваться ключами только с двумя процессорами Pi i и Pt+i, его непосредственными соседями слева и справа. Например, на рис. 5.5.8 Р„ может связываться только с и Р,.

Algorithm PARSORT (параллельная сортировка) для перестановки ключей It, /2, . . ., /лг в порядке возрастания. Шаг 0. [Инициализация] Set М 0; and TIME -t- 0. Шаг 1. [Чередовать, пока дважды не произойдет ни одного обмена местами в строке]

DO through шаг 3 while Мф2 od; and STOP.

Шаг 2. [Четный или нечетный] If TIME четно

then одновременно сравнить ключи /2 в процессорах РкС ключами /2/(- 1 в процессорах Pk-i Для

всех К=\, 2..... N12; И hK<hK-i then

обменять местами ключи в этих двух процессорах fi

else одновременно сравнить ключи /гл- в процессорах Рд- с ключами IK+i процессорах P2/f+i для всех К=\,2, . . ., N12; if /2a-+i< </s/(- then обменять ключи в этих двух процессорах fi fi.

Шаг 3. [Были обмены?] И хотя бы один обмен произведен на шаге 2 then set Л1О else set М-Л1+1 fi; set Т1МЕч- TIME+1.

Алгоритм PARSORT чередует сравнение /а- с Izk-i или h+t при исполнении шагов 1 и 2 до тех пор, пока при двух последовательных шагах расположение не останется неизменным.

л I г. а , щ,

1Шаг1 2 Шаг 2

АШг 2

$шаг1

£Шаг2 7Шаг1 ВШаг2 ашаг!

X. х; X

Окончание

Рис. 5.5.9. Диаграмма сортировки алгоритмом PARSORT.

На рис. 5.5.9 показано, как алгоритм PARSORT сортировал бы ключи с рис. 5.5.8. Такое изображение называется диаграммой сортировки. Заметим, что, хотя алгоритм останавливается после выполнения п--1=9 шагов, фактически он завершает сортировку за семь шагов. Далее мы докажем, что сортировка всегда завершается не более, чем за п шагов.

Теорема 5.5.1. Алгоритм PARSORT упорядочивает в порядке возрастания произвольный набор п ключей fi, iz, . . ., in не более, чем за п шагов.

Доказательство. Доказательство проводится индукцией по числу ключей п. Легко убедиться непосредственно, что при п=1, 2, 3 алгоритм работает в соответствии с формулировкой теоремы.

Предположим далее, что алгоритм PARSORT может упорядочить произвольный набор т ключей не более, чем за т шагов. Нам нужно

показать, что он сможет упорядочить произвольный набор fi, iz, . . ., fm+i из m+l ключей не более, чем за m+l шагов.

Рассмотрим диаграмму сортировки алгоритмом PARSORT ключей il, fg, . . ., t„+i. Рассмотрим также путь наибольшего ключа, т. е. рассмотрим путь целых чисел, помеченных как М=т+1. Общий вид этого пути показан на рис. 5.5.10.

Рис. 5.5.10. Путь наибольшего ключа УИ по диаграмме сортировки.

Рис. 5.5.п. Объединение частей А и В диаграммы сортировки.

Такой путь делит диаграмму сортировки на две части А и В. Рассмотрим диаграмму, которая получится после удаления этого пути и