Автоматическое распараллеливание для супер-ЭВМ с параллельной памятью затруднено из-за необходимости решения сложной задачи автоматического размещения данных. Эта задача и будет рассмотрена в данном разделе для суперкомпьютера [73], имеющего архитектуру перестраиваемого конвейера и обладающего общей (совместно используемой) распределенной памятью. Полученные результаты могут быть применены и к другим суперкомпьютерам с памятью такого типа, например, к суперкомпьютеру RP-3 фирмы IBM [112]. Полученные алгоритмы могут быть использованы не только при автоматическом, но и при "ручном" распараллеливании.

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

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

Далее будут исследоваться такие размещения массивов, которые обеспечивают эффективное выполнение циклов вида

DO 1 I = 1, N

1 .. X(a1*I+b1),..,Y(a2*I+b2) …

Такая условная запись будет означать, что тело цикла содержит вхождение переменной X и вхождение переменной Y с соответствующими индексными выражениями. Могут рассматриваться циклы, содержащие по нескольку вхождений одной и той же переменной. Поскольку для целей данной работы интерес представляют только вхождения массивов с их индексными выражениями, сами циклы выписываться не будут.

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

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

Пример 25.

DO 1 I = 1, N

1 W(I) = X(a1*I+b1) + Y(a2*I+b2)

При конвейерном выполнении приведенного выше цикла возникает необходимость для каждого I одновременно считывать из памяти переменные X(a1*I+b1) и Y(a2*I+b2). Следовательно, массивы X и Y надо разместить так, чтобы для каждого I оба числа X(a1*I+b1) и Y(a2*I+b2) оказывались в разных модулях памяти.

Пример 26.

DO 1 I = 1, N

1 W(I) = X(a1*I+b1) + X(a2*I+b2)

При конвейерном выполнении этого цикла возникает необходимость такого размещения массива X, чтобы для каждого I оба числа X(a1*I+b1) и X(a2*I+b2) оказывались в разных модулях памяти.

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

Отметим, что при построении параллельных алгоритмов часто о размещении данных ничего не говорится, поскольку время на их пересылки не учитывается [90], [91]. В работе [81] алгоритмы предполагают регулярные размещения данных. Метод пирамид [17] допускает размещение данных, которое не является полурегулярным. Полностью размещениям данных посвящена книга [75], но без связи с распараллеливанием программ.

Многомерные массивы могут рассматриваться как семейства одномерных. Однако в некоторых случаях может оказаться полезным разные элементы такого семейства размещать по-разному в зависимости от параметра. Примером может послужить скошенная форма хранения матрицы [81], которую можно рассматривать как семейство одномерных массивов, размещенных регулярно с разными сдвигами. Задачи с такими размещениями в данном разделе не рассматриваются.

Далее будет использоваться следующий факт из теории диофантовых уравнений. Линейная система уравнений с целыми коэффициентами с расширенной матрицей ранга k имеет целочисленные решения тогда и только тогда, когда наибольший общий делитель всех миноров k-ого порядка расширенной матрицы делится на наибольший общий делитель всех миноров k-ого порядка основной матрицы системы [56, с. 19].