Общие условия размещения массивов без пересылок.

 

Будем рассматривать задачу размещения данных с минимизацией межпроцессорных пересылок в суперкомпьютерах с распределенной памятью.

Будем предполагать, что имеется p процессоров, каждый из которых обладает своей локальной памятью, причем доступ к данным своей локальной памяти требует значительно меньших затрат времени, чем доступ к данным из локальной памяти другого процессора. Размещения данных будем рассматривать только линейные по модулю p, т.е. элемент массива X(i1, i2,..., im) находится в памяти процессора с номером u = (s1*i1+s2*i2+...+sm*im+s0) mod p, где s0, s1, s2,...sm – константы, зависящие только от массива X. К таким размещениям, в частности, относятся размещение матрицы по строкам или по столбцам или по диагоналям или скошенная форма хранения матрицы.

       Далее будем рассматривать гнездо циклов, содержащее два вхождения массивов. 

 

DO 1 I₁ = 0, N₁

...................................                                                                                   (16)

DO 99 I_n = 0, N_n                                                  

99… = X(a₁₀+ a_1j*I_j,.., a_m0+ a_mj*I_j) + Y(b₁₀+ b_1j*I_j,.., b_k0+ b_kj*I_j)

 

       Будем рассматривать вопрос о том, когда эти вхождения оказываются в одном и том же модуле памяти.

 

Теорема 18. Пусть в гнезде циклов (16) есть два вхождения

 

X(a₁₁*i1+...+a_1n*in+a₁₀, a₂₁*i1+...+a_2n*in+a₂₀,..., a_m1*i1+...+a_mn*in+a_m0)

 

и

 

Y(b₁₁*i1+...+b_1n*in+b₁₀, b₂₁*i1+...+b_2n*in+b₂₀,..., b_k1*i1+...+b_kn*in+b_k0)

 

 m-мерного массива X и k-мерного массива Y соответственно.

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

 

s1*a₁₁+s2*a₂₁+...+sm*a_m1 = t1*b₁₁+t2*b₂₁+...+tk*b_k1 mod p

.........................................................................................

s1*a_1n+s2*a_2n+...+sm*a_mn = t1*b_1n+t2*b_2n+...+tk*b_kn mod p

s1*a₁₀+s2*a₂₀+...+sm*a_m0+s0 = t1*b₁₀+t2*b₂₀+...+tk*b_k0+t0 mod p

 

Доказательство. Поскольку оба вхождения из условия теоремы находятся в одном и том же модуле памяти должно выполняться равенство

 

s1*(a₁₁*i1+...+a_1n*in+a₁₀)+s2*(a₂₁*i1+...+a_2n*in+a₂₀)+...+ sm*(a_m1*i1+...+a_mn*in+a_m0)+s0 =

t1*(b₁₁*i1+...+b_1n*in+b₁₀)+t2*(b₂₁*i1+...+b_2n*in+b₂₀)+...+ tk*(b_k1*i1+...+b_kn*in+b_k0) +t0 mod p

 

Так как это равенство должно тождественно выполняться для всех значений счетчиков циклов i1, i2,..., in, коэффициенты при этих счетчиках должны быть равны. Отсюда и вытекает заключение теоремы. 

       Конец доказательства.

 

       Аналогичным образом доказывается следующая

 

       Теорема 19. Пусть в гнезде циклов (16) есть два вхождения m-мерного массива X:

 

X(a₁₁*i1+...+a_1n*in+a₁₀, a₂₁*i1+...+a_2n*in+a₂₀,..., a_m1*i1+...+a_mn*in+a_m0)   (17) 

 

и

 

X(b₁₁*i1+...+b_1n*in+b₁₀, b₂₁*i1+...+b_2n*in+b₂₀,..., b_m1*i1+...+b_mn*in+b_m0). (18)

 

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

 

s1*(a₁₁-b₁₁)+s2*(a₂₁-b₂₁)+...+sm*(a_m1-b_m1) = 0 mod p

.........................................................................................                          (19)

s1*(a_1n-b_1n)+s2*(a_2n-b_2n)+...+sm*(a_mn-b_mn) = 0 mod p

s1*(a₁₀-b₁₀)+s2*(a₂₀-b₁₀)+...+sm*(a_m0-b_m0) = 0 mod p

 

Для того чтобы оба вхождения (17) и (18) оказались в одном и том же модуле памяти при некотором наборе счетчиков циклов, должно выполняться условие:

 

(s1*(a₁₁-b₁₁)+s2*(a₂₁-b₂₁)+...+sm*(a_m1-b_m1) )*i1 +(s1*(a_1n-b_1n)+s2*(a_2n-b_2n)+...

+sm*(a_mn-b_mn))*i2 + (s1*(a₁₀-b₁₀)+s2*(a₂₀-b₁₀)+...+sm*(a_m0-b_m0))*in = 

= 0 mod p                                                                                                     (20)

 

Общий вид решения этого уравнения следующий:

 

I1 = d₁₁*t₁+...+d_1(n-1)*t(n-1) 

I2 = d₂₁*t₁+...+d_2(n-1)*t_(n-1)                                                                           (21)

………….

In = d_n1*t₁+...+d_n(n-1)*t_(n-1)

 

Где переменные (параметры) t₁, t₂, …, t_(n-1) пробегают множество целых чисел Z.       

 

Если не все коэффициенты уравнения (20) нули (что соответствует случаю (19) ), то решения уравнения (20) лежат в пространстве Zⁿ на гиперплоскостях коразмерности 1, параллельных (21) и отстоящих друг от друга на расстоянии p. Статистически количество решений, при которых оба вхождения (17) и (18) оказываются в разных ПЭ, в (p-1) раз больше, чем решений, при которых эти вхождения оказываются в одном и том же ПЭ. Следовательно, требуется сделать пересылок n^n-1 * (p-1) или один раз разослать все элементы массива во все процессоры: n^m пересылок.  

 

 

Примеры матричных алгоритмов с анализом размещения данных.

 

Пример 12.

do i = 1, n

do j = 1, n

B(i, j) = [A(i, j)+A(j, i)]/2

 

Для каждого значения i и каждого значения j элементы B(i, j), A(i, j) и A(j, i) должны оказаться в одном и том же модуле памяти. Это возможно тогда и только тогда, когда существуют такие целые числа s1, s2, t1, t2, что выполняются равенства

 

s1*i+s2*j = s1*j+s2*i = t1*i+t2*j mod p

 

Это возможно лишь при s1=s2=t1=t2 mod p. Например, все эти коэффициенты равны 1. Тогда в k-ом модуле памяти будет находиться k-ая косая диагональ (перпендикуляр к диагоналям) матрицы A и k-ая косая диагональ B – то есть множества элементов A(i, j) и B(i, j), для которых i+j = k (mod p).

 

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

 

do i = 1, n

do j = 1, n

do k = 1, n

X(i, j) = X(i, j)+A(i, k)*B(k, j).

 

Для каждого значения i, каждого значения j и каждого значения k элементы X(i, j), A(i, k) и B(k, j) должны оказаться в одном и том же модуле памяти. Это возможно тогда и только тогда, когда существуют такие целые числа s1, s2, t1, t2, u1, u2, что выполняются равенства

 

s1*i+s2*j = t1*i+t2*k = u1*k+u2*j mod p

 

Это возможно для всех значений i, j, k лишь при выполнении равенств s1=s2=t1=t2=u1=u2=0 mod p, т.е. когда все данные находятся в одном и том же модуле памяти. Итак, задача вычисления произведения матриц не может быть распараллелена на суперкомпьютере с MIMD архитектурой без межпроцессорных пересылок данных.

 

Пример 14.

do i = 1, n

do j = 1, n

B(i, j) = [A(i, j)+A(i-j, j)]/2

 

Размещение без пересылок возможно тогда и только тогда, когда существуют такие целые числа s1, s2, что выполняется равенство

 

s1*i+s2*j = s1*(i-j)+s2*j mod p

 

Это возможно лишь при s1=0 mod p (а S2 = 1).

 

Пример 15.

do i = 1, n

do j = 1, n

B(i, j) = [A(i, j)+A(i-j, i)]/2

 

Размещение массива A без пересылок невозможно. Действительно, если такое размещение существует, то существуют такие целые числа s1, s2, что выполняется равенство

 

s1*i+s2*j = s1*(i-j)+s2*i mod p

 

Это возможно лишь при s1=s2=0 mod p.

 

 

Пример 16.

do i = 1, N

do j = 1, N

B(i, j) = [A(i, j)+A(N-j, N-i)]/2

 

Размещение без пересылок возможно тогда и только тогда, когда существуют такие целые числа s1, s2, что выполняется равенство

 

s1*i+s2*j = s1*(N-j)+s2*(N-i) mod p

 

Если N кратно p, то это возможно при s1+s2=0 mod p.

 

Пример 17.

do i = 1, n

do j = 1, n

B(i, j) = [A(i, j)+A(n-j, i)]/2

 

Размещение массива A без пересылок невозможно. Действительно, если такое размещение существует, то существуют такие целые числа s1, s2, что выполняется равенство

 

s1*i+s2*j = s1*(n-j)+s2*i mod p

 

Это возможно для любых i, j лишь при s1=s2=0 mod p.

 

 

Пример 18. Распараллеливание алгоритма Флойда.

Алгоритм Флойда имеет на входе матрицу A весов дуг графа и преобразует ее в матрицу кратчайших расстояний.

 

do k = 1, n

do i = 1, n

do j = 1, n

if A(i, j) > A(i, k)+A(k, j) then

A(i, j) = A(i, k)+A(k, j)

 

Условие выполнения этого гнезда циклов без межпроцессорных пересылок на параллельном суперкомпьютере с распределенной памятью запишется в виде следующих равенств

 

       s1*i+s2*j = s1*i+s2*k= s1*k+s2*j

 

Эти равенства могут выполняться тождественно для всех i, j, k только при s1=s2=0, т.е. при последовательном вычислении.  

 

Операцию рассылки переменной во все процессоры будем обозначать broadcast, и использовать в следующем виде:

 

       for i broadcast xi = y

 

Эта запись означает, что в каждом модуле памяти с номером i есть переменная xi и всем этим переменным (одновременно) присваивается значение переменной y.

 

       Теорема 20.   Пусть в суперкомпьютере с распределенной памятью есть операция broadcast и пусть n=p. Тогда алгоритм Флойда может быть выполнен за n² пересылочных операций broadcast.

Для доказательства следует разместить элементы матрицы весов A так, что элемент A(i, j) находится в модуле памяти i mod p, после чего алгоритм может быть записан в виде

 

 do k = 1, n

 do j = 1, n

for i broadcast B(i, j) = A(k, j)

do par i = 1, n

if A(i, j) > A(i, k)+B(i, j) then

A(i, j) = A(i, k)+B(i, j)

 

 

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

Поделиться: