Архитектура SIMD (Single Instruction Multiple Data) одновременно выполняет одинаковые команды над разными данными. Векторные компьютеры можно считать частным случаем архитектуры SIMD. Кроме того, к этой архитектуре относятся и такие известные суперкомпьютеры с распределенной памятью, как американские ILLIAK-4 (64 процессора), Connection Machine2 (64000 процессоров) и советская ПС-2000 (64 процессора). Такие вычислительные системы синхронны и позволяют параллельно выполнять программы, состоящие из циклов и операторов присваивания, и допускают потоковые, анти- и выходные зависимости, которые на графе информационных связей направлены сверху-вниз (от вхождений, которые раньше обращаются к памяти, к вхождениям, которые позже обращаются к памяти). При этом, если векторные компьютеры распараллеливают только самые глубоко вложенные циклы, то SIMD компьютеры с распределенной памятью допускают гнезда вложенных циклов.

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

     DO 99 I = 1, N

     X(I) = C(I)+B(I);

     DO 99 J = 1, N

     A(J) = A(J) + D(I,J)*X(I); 

99 CONTINUE

       Конец примера.

В суперкомпьютерах типа SIMD все не отключенные процессоры в один момент времени выполняют одну и ту же операцию. Если на каком-то этапе работы алгоритма необходимо в разных процессорах выполнить разные операции, то процессоры активируются по очереди теми группами, которые должны выполнять одинаковые операции. Для таких суперкомпьютеров распараллеливаются самые вложенные циклы, причем количество итераций этих циклов не должно зависеть от вычислений в теле цикла (как бывает в итерационных процессах). Здесь очень удобны циклы DO языка ФОРТРАН или циклы FOR языка ПАСКАЛЬ. Частным случаем таких суперкомпьютеров иногда являются векторные суперкомпьютеры, обрабатывающие векторы фиксированной длины. 

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

Пример 280. Предположим, что в вычислительной системе имеется P процессорных элементов, и пусть все массивы размещены так, что I-ый элемент массива находится в модуле памяти с номером (I mod P). 

     DO 99 I = 1, N

     X(I) = A(I)+B(I);

     A(I) = C(I+1)+X(I); 

     A(I-1) = X(I-1)*B(I+3); 

99 CONTINUE

В приведенном цикле входная зависимость между вхождениями переменной B предполагает пересылку до выполнения цикла; истинная зависимость (X(I), X(I-1)) требует выполнение пересылки после первого оператора перед третьим. Антизависимости и выходная зависимость не влияют на параллельное выполнение – новые элементы массивов окажутся сдвинутыми относительно старых элементов.

       Конец примера.

       Основные распараллеливающие преобразования, как и при векторизации: перестановка операторов, повышение размерности массивов, введение временных массивов.

Конвейерные вычисления

В данной главе рассматривается задача автоматического распараллеливания циклов для суперкомпьютера с архитектурой перестраиваемого конвейера. Конвейерные архитектуры описываются в [66]. Примеры архитектуры перестраиваемого конвейера описаны в [115], [72]. Такая архитектура оказывается удобной для эффективного выполнения широкого класса задач с регулярными зависимостями по данным, в том числе и для информационно сильно связных. Получены алгоритмы, которые по тексту распараллеливаемого цикла формируют граф соединения сегментов памяти и процессоров в конвейер для вычисления этого цикла. Отображаемые циклы могут быть рекуррентными. Некоторые ограничения часто могут быть преодолены с помощью преобразований программ. Примерная схема компьютера с архитектурой перестраиваемого конвейера (со структурно-процедурной организацией вычислений) [72] изображена на следующем рисунке.

                              П Р О Ц Е С С О Р Ы

                                 К О М М У Т А Т О Р

                   М О Д У Л И     П А М Я Т И

Рис. 69. Схема коммутации процессоров и модулей памяти.      

Каждый процессор имеет на входе буфер. Этот буфер позволяет задерживать поступление данных в процессор. Такие действия бывают важными при синхронизации конвейерного вычисления.

Допускается в один момент времени обращаться к разным секторам памяти (для чтения или записи).

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

Отметим, что близкой к данной модели (по доступу к параллельной памяти) является архитектура суперкомпьютера RP-3 фирмы IBM [112].

Граф вычислений программы

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

Ясно, что операции считывания из памяти данного, обозначенного безиндексной переменной, соответствует источник на графе (т. е. такая вершина, в которую не входит ни одна дуга), а операции записи в память соответствует сток (не выходит ни одна дуга).

Пример 281. Рассмотрим оператор присваивания:

X = (X*A(I)+B(I))+C(I)

Этому оператору соответствует дерево вычислений.

X           *           +           +        X

A(I)    B(I)    C(I)

Рис. 70. Дерево вычислений

Отметим, что в общем случае граф вычислений представляет собой ориентированный лес.

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

Рассмотрим теперь задачу построения графа для программного цикла.

      DO 99 I=1, N

99  ТЕЛОЦИКЛА(I)                                                                  (451)

Раскрутка цикла [20] - это замена предыдущего цикла на следующий эквивалентный фрагмент программы:

ТЕЛОЦИКЛА(1)

ТЕЛОЦИКЛА(2)

...........

ТЕЛОЦИКЛА(N)

Граф вычислений раскрутки цикла представляет собой объединение N изоморфных друг другу подграфов.

Граф вычислений раскрутки цикла слишком громоздкий для практической обработки. По этой причине далее будет строиться другой граф – называемый свернутым графом, который имеет значительно меньшие размеры (как у одной итерации тела цикла) и содержит в себе всю информацию о графе вычислений раскрутки цикла.