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

Оптимальное количество процессорных элементов

Давно известно, что для некоторых параллельных масштабируемых программ увеличение количества используемых процессоров лишь до некоторого момента ведет к увеличению быстродействия, а затем быстродействие снижает [55]. Здесь будет теоретически обосновано данное явление и для некоторого класса программ для различных коммуникационных сетей будет вычислено оптимальное количество процессоров. Для получения формулы оптимального количества процессоров используется модель времени вычисления программ (рассматриваемого класса), учитывающая время пересылок данных. Без учета пересылок данных время выполнения программ рассматривалось, например, в [114].

Принцип сдваивания

Пусть * – некоторая ассоциативная операция и рассматривается задача параллельного вычисления последовательности из n-1 таких операций a₁*a₂*...*a_n. Тогда это вычисление можно выполнить на n/2 ПЭ за ]log₂n[ шагов [ 25 ]. (Здесь ]x[ означает наименьшее целое число, которое не меньше x). Идея этого алгоритма – уменьшение на каждом шаге размерности задачи вдвое – называется принципом сдваивания. Поскольку операция * бинарная, очевидно, что меньшее количество шагов невозможно. Данный результат следующим очевидным образом обобщается на случай p (< n/2) ПЭ.

Теорема 16. Пусть * – ассоциативная операция. Тогда параллельное вычисление последовательности из n-1 такой операции a₁*a₂*...*a_n на p (< n/2) ПЭ можно выполнить за ]n/p[+]log₂p[ шагов. Если p – степень двойки, то меньшее количество шагов невозможно. В общем случае наименьшее количество шагов может быть равно ]n/p[+]log₂p[-1.

Подсчитаем затраты времени на пересылки данных при использовании принципа сдваивания.

Для универсального коммутатора, очевидно, количество тактов с пересылками равно ]log₂p[.

Для гиперкуба тоже достаточно ]log₂p[ пересылок. Действительно, при первом такте пересылок, следует брать данные в ПЭ с номерами вида (1, x2, x3,..., xm) и пересылать в (0, x2, x3,..., xm) для всех xiÎ {0, 1}, i=2,..., k. После этого задача вычисления a₁*a₂*...*a_n сводится к точно такой же, но для вдвое меньшего числа данных, которые следует обработать на гиперкубе размерности на 1 меньше.

На кольцевой сети тоже достаточно ]log₂p[ пересылок [81]. Но на первом шаге данные пересылаются в соседние ПЭ, на втором шаге – пересылаются через один ПЭ, ..., на k-ом шаге – через 2 **(k-1)-1 ПЭ. Всего потребуется времени T1* ]log₂p[ + T2*(p-1).

Рассмотрим m-мерную решетку, как декартово произведение m колец C1´ C2´...´ Cm. Тогда алгоритм сдваивания сначала следует выполнить на кольцах первой размерности за ]log₂|C1|[ шагов (здесь |C1| – количество узлов в кольце C1), затем на кольцах второй размерности и т.д..

Теорема 17. Пусть дана функция f(x₁,..., x_n) от n переменных и данные x₁,..., x_n размещены в p (< n) ПЭ так, что ни одно данное не записано дважды и каждый ПЭ содержит хотя бы одно данное. Тогда для вычисления функции f кроме арифметических операций требуется не менее ]log₂p[ тактов межпроцессорных пересылок.

Доказательство. Не умаляя общности можно считать, что n=p, то есть в каждом ПЭ находится ровно одно данное. Воспользуемся методом математической индукции.

Используя лишь один такт межпроцессорных пересылок можно вычислить лишь функцию двух аргументов, лежащих в разных ПЭ. Три аргумента уже нельзя собрать в одном ПЭ за один такт, поскольку ПЭ может читать за один такт лишь одно данное. Предположим, что, используя k тактов межпроцессорных пересылок можно вычислить функцию 2^k аргументов. Докажем, что за k+1 шаг можно вычислить функцию не более чем 2^k+1 аргументов. Действительно, на последнем шаге можно будет вычислить функцию двух промежуточных аргументов. Каждый из этих промежуточных аргументов был вычислен за k шагов и, следовательно, не может быть функцией более чем 2^k+1 исходных данных. Итого, за k+1 шаг можно вычислить функцию 2^k+1 переменных.

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

Ограничения на рассматриваемые циклы

Пусть D – подмножество R^m и D – множество отображений пространства D в D, которое замкнуто относительно операции суперпозиции. Будем говорить, что множество D является рекуррентно замкнутым, если выполняются следующие требования:

1. Множество D замкнуто относительно операции суперпозиции.

2. Существует число Ta и алгоритм, который для любых двух отображений G₁ и G₂ из D вычисляет суперпозицию G₁о G₂ за время Ta.

3. Существует число Tb и алгоритм, который для любого G из D и x из D вычисляет G(x) за время Tb.

4. Вычисление суперпозиции на компьютере является ассоциативной операцией на D. (Теоретически суперпозиция отображений всегда ассоциативна, но, как известно, это свойство может нарушаться из-за погрешности округлений на компьютере).

Будем говорить, что множество D является N-рекуррентно замкнутым, если выполняются условия 1-3, а вместо условия 4 выполняется следующее условие:

4а. Если вычисление суперпозиции N отображений из D на компьютере выполнить по-разному, т.е. изменив порядок взятия операций суперпозиции, то результаты будут отличаться на пренебрежимо малую величину.

Описанное абстрактное множество D было введено в [99] для исследования параллельного выполнения рекуррентных программных циклов с условными операторами.

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

Пример 9. Пусть D = Z^m, тогда множество D всех линейных отображений из Z^m в Z^m вида y=Ax, где A – матрица с целыми коэффициентами, удовлетворяет указанным выше требованиям.

Пример 10. Пусть D = R^m, тогда, если погрешность округлений на компьютере достаточно мала, то множество D всех линейных отображений из R^m в R^m удовлетворяет указанным выше требованиям. Это возможно, если количество разрядов в машинном слове достаточно велико для рассматриваемых погрешностей и значений N.

Пример 11. Множество D всех булевых отображений вида

f(X) = PÙ X Ú QÙ Ø X Ú R удовлетворяет указанным выше требованиям.

Вычисление массивов данных

Будем рассматривать цикл, в котором вычисляются элементы массива:

DO I = 1, N (12)

X(I) = G_I(X(I-1));

Здесь G_I, I=1,..., N – отображения из N-рекуррентного множества D. В частности, если m=1, G_I(Y)=Y+A(I), то цикл ( 12 ) для каждого k=1,..., N вычисляет суммы чисел A(I), I=1,..., k. Для вычисления этого цикла воспользуемся следующим алгоритмом, предполагающим вертикальное размещение массивов:

1. В каждом ПЭ с номером k вычисляем ]N/p[ следующих суперпозиций H_ki = G_k*]_N/_p[-_i+1 o...oG₍_k-1)*]_N/_p[+1. Это потребует (]N/p[-1)*Ta времени. Здесь Ta – время вычисления G_I(X)

2. Пользуясь принципом сдваивания [ 25, с.34], вычисляем все суперпозиции

W₁ = H₁₁

W₂ = H₂₁ oH₁₁

......

W_k = H_k1 o...oH₂₁ oH₁₁

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

W_n = H_n₁ o... oH₂₁ oH₁₁

Это потребует log₂p шагов, на каждом из которых вычисляется одна операция суперпозиции и выполняется одна межпроцессорная пересылка отображения H_k1. Для универсальных коммутаторов и гиперкуба здесь понадобится log₂p*(Ta+T0) тактов, а для m-мерной решетки – log₂p*(Ta+T1)+T2*k*( - 1) тактов (в частности, для кольцевой коммутационной сети – log₂p *(Ta+T1)+T2*(p-1) ).

3. Одновременно за 1 шаг в каждом ПЭ с номером k вычисляем W_k(X(0)). Это отнимет Tb времени.

4. Одновременно за ]N/p[ шагов в каждом ПЭ с номером k вычисляем значения G_i(W_k(X(0))) для всех индексов i, для которых G находится в этом ПЭ. Это требует ]N/p[*Tb времени.

5. Конец.

Итак, для МВС с универсальным коммутатором или с архитектурой гиперкуба время работы оценивается величиной

F(p) = (]N/p[ - 1)*Ta+log (p)*(Ta+T0)+(]N/p[+1)*Tb =

]N/p[ *(Ta+Tb)+log (p)*(Ta+T0)+(Tb-Ta),

оптимальное количество ПЭ равно

p = N*(Ta+Tb)*ln2/(Ta+T0),

минимальное время работы равно

(Ta+T0)* 1/ln2+ln((Ta+Tb)*ln2/(Ta+T0)) +Tb-Ta.

Для МВС с m-мерной решеткой время работы оценивается величиной

F(p) = (]N/p[-1)*Ta+log (p)*(Ta+T1)+m*( -1) * T2+(]N/p[+1) * Tb = ]N/p[ *(Ta+Tb)+log (p)*(Ta+T1)+m*( - 1)*T2+(Tb-Ta),