О несовпадении блочно-рекурсивных и блочно-аффинных размещений.

 

Теорема 22. Начиная с размерности 4*4, блочно-рекурсивное размещение матрицы не относится к классу блочно-аффинных размещений.

Доказательство. Рассмотрим блочно-рекурсивное размещение матрицы 4*4 на сетке из 16 узлов. Битовые номера узлов 4-хмерного куба запишем в десятичной системе счисления.  

 

0 A11	1 A12	4 A13	5 A14
2 A21	3 A22	6 A23	7 A24
8 A31	9 A32	12 A33	13
10 A41	11 A42	14 A43	15 A44

 

  Рис. 64. Блочно-рекурсивное размещение матрицы 4*4. Нумерация узлов соответствует нумерации узлов 4-х мерного куба.

 

Предположим, что данное размещение принадлежит к классу аффинных. Тогда, существуют такие числа, s1, s2, s0, что элемент матрицы A_ij находится в ПЭ с номером s1*i+s2*j + s0. Подставляя вместо i и j пары значений (1, 1), (1, 2), (1, 3), получим систему равенств:  

 

 s1+s2 + s0 = 0

 s1+2*s2 + s0 = 1

s1+3*s2 + s0 = 4 

 

Несложно заметить, что эта система несовместна, что означает неверность предположения о принадлежности данного размещения к классу аффинных. Полученное противоречие завершает доказательство.

 

 

Некоторые выводы о блочных размещениях данных в параллельной памяти.

 

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

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

 

 

Размещения массивов в общей распределенной памяти

 

 

Особенности вычислений на вычислительных системах с общей распределенной памятью

 

Автоматическое распараллеливание для супер-ЭВМ с параллельной памятью затруднено из-за необходимости решения сложной задачи автоматического размещения данных. Эта задача и будет рассмотрена в данном разделе для суперкомпьютера [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].

 

 

⇐ Предыдущая9101112131415161718Следующая ⇒

Поделиться: