Стр. 52 - Параллельное программирование
Упрощенная HTML-версия
ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
50
каждом процессоре происходит умножение полученной диагональной подматрицы
A
i,i
на подматрицу
B
i,j
,
хранящуюся на данном процессоре. Результат умножения
помещается в подматрицу
C
i,j
процессора (
i,j
). Здесь
i,j
изменяются от 0 до 2. Перед
переходом к следующему этапу происходит перемещение подматрицы
B
i,j
от про-
цессора (
i,j
) к процессору (
i
-1,
j
), то есть к непосредственно "верхнему" процессору.
Процессоры нулевой строки посылают подматрицы
B
0,j
процессорам последней
(в данном случае второй) строки.
Рис. 5.6. Этап 1 (слева) и этап 2 (справа)
На первом этапе также происходит рассылка, но только уже подматриц
A
i,(i+1)
mod
q
, где
q
=
p
1/2
= 3, а
i
изменяется от 0 до 2. То есть процессоры нулевой, пер-
вой и второй строк получат подматрицы
A
0,1
,
A
1,2
и
A
2,0
соответственно. Далее на
каждом процессоре происходит умножение полученной подматрицы
A
i,(i+1)
mod3
на
подматрицу
B
i,j
, полученную на предыдущем этапе от процессора непосредственно
нижней строки. Результат умножения складывается с подматрицей
С
i,j
и снова в нее
записывается. Перед переходом к следующему этапу снова происходит восходящее
перемещение подматриц B
i,j
, аналогичное их перемещению на этапе 0.
Второй (и в данном случае последний) этап работы алгоритма Фокса полно-
стью аналогичен предыдущим этапам и может быть описан следующей последова-
тельностью шагов:
•
рассылка подматрицы
A
i,(i+
2
)
mod3
процессорам
i
-той строки (на рисунке эти
подматрицы выделены);
•
умножение на процессоре (
i,j
) подматриц
A
i,(i
+2) mod 3
и
B
i,j
(Понятно, что в
общем случае, подматрицы
B
i,j
на данном этапе и предыдущем не совпада-
ют);
•
C
i,j
=
C
i,j
+
A
i
,(
i
+2) mod 3
⋅
B
i,j
.
Заметим также, что перемещение подматриц
B
i,j
на последнем этапе является
излишним. После заключительного этапа мы получим девять подматриц
С
i,j
,
которые будут составлять матрицу
С
, являющуюся решением данной задачи.
