Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [ 93 ] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

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.

з

>4

Рис. 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.п. Объединение частей А и В диаграммы сортировки.

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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [ 93 ] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.001