Таким образом, если мы обозначим через 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 процессоров.