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

[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]

Таким образом, если мы обозначим через n{k) число деревьев, остающихся после {k-1)-кратного применения шага 3 и однократного применения шага 1, то

или в общем виде

п(2)<

«(1)

п(3)<

ft (2)

Если обозначить через К наименьшее целое, для которого п(Д)1, то в наихудшем случае К удовлетворяет неравенству 2~<сМ2, т. е. /ClogaM. Следовательно, в наихудшем случае алгоритм SOLLIN выполняет 0(log2M) шагов.

Такова элементарная часть анализа сложности алгоритма SOLLIN. Сколько операций и сколько времени потребуется на выполнение каждого шага алгоритма? Ответ на этот вопрос зависит от типа ЭВМ и других факторов.

Представим, что у нас имеется М процессоров (компьютеров) Pi, Р2, . . ., Рм< каждый из которых назначен одной из вершин Vi, Vi, .... % сети G. На любом шаге алгоритма каждый процессор Pi будет, по существу, просматривать г-ю строку матрицы смежности сети G, отыскивая ребро с наименьшим весом и наименьшим индексом, от Vi до какой-нибудь вершины в дереве, отличающемся от дерева, которое содержит Vi. Представим, что с каждой вершиной связана метка TREE (О поддерева, к которому в данный момент времени принадлежит вершина Wj. На рис. 5.5.6 показаны матрица смежности для сети

1 2 3 4 5 6 7 8

Р,-*1

Рз-*3 Р,-4 Pg ->5 Рб-*6 Р,->7 Ра-*8

О оо оо оо оо 4

оо оо

00 4

4 «.

00 4

~ 3 2

0 1 ~

1 О ~

оо оо О

3 ~ 1

со oq 2

оо oq

Дерево Дерево Дерево

2 2 4 4

1 2 3 4 5 6 7 8

Рис. 5.5.6. Применение параллельных процессоров Р, Р,

зации алгоритма SOLLIN-

Pg для реали-

рис. 5.5.3 И метки TREE, которые могли бы появляться после шага 1, после шагов 2 и 3 и после второго исполнения шагов 2 и 3.

Следовательно, шаг 1 может исполняться параллельно за время 0(М), но он потребует от каждого из М процессоров 0(М) шагов, т. е. будет выполнено О(М) шагов.

На шаге 3 процессор Pi снова просмотрит все ребра, инцидентные вершине Vi, для отыскания наименьшего индекса на ребре с мини-



мальным весом, идущем к вершине в другом дереве от Vt. Для всех процессоров это потребует 0(М) времени и О(М) шагов. Кроме того, потребуется второй проход [О (УИ)] по всем вершинам для выбора ребра с наименьшим весом в каждом дереве Tj. Окончательный проход [0(УИ)] по всем вершинам потребуется для обновления вектора TREE и объединения поддеревьев.

Таким образом, алгоритм SOLLIN потребует времени 0(М) на шаг 1 и О (УИ) на каждое из О ( logM J) исполнений шагов 2 и 3, т. е. он потребует 0(М Iog2yH) времени. Однако легко видеть, что он выполнит 0(yk[Iog2yvi) операций. Сравните это с алгоритмом PRIM, требующим О(УИ) времени и О(УИ) операций.

О языках параллельного программирования

Для реализации параллельного алгоритма, аналогичного алгоритму SOLLIN, нам понадобилась бы вычислительная система с достаточным количеством процессоров, способных выполнять команды параллельно и независимо друг от друга. Нам также понадобился бы язык программирования, который позволял бы выразить параллелизм в алгоритмах, т. е. такой, чтобы он позволял записывать команды, реализующие слово «одновременно».

Рассмотрим блок-схему на рис. 5.5.7, а. Если блоки программы Qu Qz и Qs могут выполняться одновременно, а блок q4 может быть выполнен только после выполнения всех команд блоков Qi, q2 и Qs, то мы могли бы перейти от последовательной схемы на рис. 5.5.7, а к параллельной на рис. 5.5.7, б. На языке программирования это можно было бы выразить так:

Эта запись показывает, что блоки Qu Q2 и Qs независимы и могут выполняться параллельно. Чтобы гарантировать, что мы достигнем желаемого результата, мы могли бы потребовать, чтобы ни одна из переменных, изменяемых в Qt, не использовалась в Qj

Действие этого оператора состоит в инициации выполнения каждого блока операторов Qt параллельно. Оператор завершается - и q4 может выполняться - только после завершения всех операторов во всех блоках

Внутри каждого блока можно использовать большинство обычных типов операторов, как то: присваивания, условные операторы, пик-

Рис. 5.5.7. Преобразование после-» довательного процесса в параллельный.



лы DO, вызовы подпрограмм. Возможно, придется сделать исключение для условных переходов из данного Qj (или снаружи в него), реализовать которые было бы затруднительно.

Подобные операторы реализованы в фортраноподобном языке IVTRAN, который был разработан в Иллинойском университете для ЭВМ Иллиак IV- с высокой степенью параллелизма. Оператор имеет вид

DO k CONG FOR ALL (к, . . ., QS

где k - метка выполняемого оператора, ограничивающего цикл DO; (il, ia, . . ., in).- последовательность целочисленных индексных переменных; S - конечное множество наборов по п целых чисел, которые служат для определения диапазона допустимых значений индексных переменных. Цель этого оператора состоит в том, чтобы назначить по одному процессору каждому набору из п чисел, например (ut, v, . . ., Vn)S. Этот процессор далее будет выполнять все операторы, лежащие внутри цикла DO, в предположении ii=Vi, izv, . . ., i„=n- Одновременно другие процессоры, соответствующие различным наборам по п чисел, будут выполнять те же операторы внутри цикла DO.

Например, рассмотрим следующий сегмент текста программы, вычисляющий параллельно квадратный корень от каждого элемента массива В (3x5) и помещающий результат в массив А:

DO 10 CONC FOR ALL (I,J)6{1 £Г£3,1 sJsS).. A{LJ) = SQRT(B(I,J)) 10 CONTINUE

Этот параллельный цикл DO потребует 15 различных процессоров, каждый из которых будет выполнять тело этого цикла DO, что называется, асинхронно, т. е. никакие два процессора не обязаны выполнять одну и ту же команду в точности одновременно.

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

DO k SIM FOR ALL (ii, .....i„)€S

где S - конечное множество наборов целых чисел по п штук. Этот оператор подобен оператору DO k CONC, за исключением того, что команды в цикле DO выполняются синхронно всеми процессорами.

Иногда возникает необходимость выполнить определенные вычисления последовательно. Б виде цикла DO это можно выразить так:

DO k SEQ FOR Кеи<КЩ

Мы теперь можем объединить эти операторы в программе умножения двух матриц 10X 10 Л и В; это потребует 10х 10=100 процессоров.



[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.0009