Стр. 49 - Параллельное программирование
Упрощенная HTML-версия
ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
47
o
блок A
ij
матрицы
A
, размещенный в процессоре перед началом
вычислений;
o
блоки
A
'
ij
,
B
'
ij
матриц
A
и
B
, получаемые процессором в ходе выпол-
нения вычислений.
Выполнение метода включает следующие действия:
•
этап инициализации
, на котором на каждый процессор
p
ij
передаются
блоки
A
ij,
B
ij
и обнуляются блоки
C
ij
на всех процессорах;
•
этап вычислений
, на каждой итерации
l, 1
≤
l
≤
k
, которого выполняется:
o
для каждой строки
i, 1
≤
i
≤
k
, процессорной решетки блок A
ij
процессо-
ра
p
ij
пересылается на все процессоры той же строки
i
; индекс
j
,
определяющий положение процессора
p
ij
в строке, вычисляется по
соотношению:
(mod есть операция получения ос-
татка от целого деления);
o
полученные в результаты пересылок блоки
A
'
ij
,
B
'
ij
каждого
процессора
p
ij
перемножаются и прибавляются к блоку
C
ij
;
o
блоки B
'
ij
каждого процессора
p
ij
пересылаются процессорам
p
ij
, яв-
ляющимся соседями сверху в столбцах процессорной решетки (блоки
процессоров из первой строки решетки пересылаются процессорам
последней строки решетки).
Случай
p = n
2
В данном случае получается, что каждому процессору назначается по одному
элементу от каждой из матриц
А, В
и
С
. Распределим элементы матриц между про-
цессорами следующим образом. Процессору с номером
in+j
(в дальнейшем процес-
сору (
i,j
)) назначим элементы матриц
А, В
и
С
, находящиеся в
i
-той строке и
j
-том
столбце. Здесь
i,j
изменяются от 0 до
n
-1. В данном частном случае алгоритм Фокса
будет выполнять умножение матриц
А
и
В
за
n
этапов. Примем, что начальный этап
имеет номер 0, а последний этап номер
n
-1. Тогда на начальном этапе процессор (
i,j
)
умножает диагональный элемент
a
i,i
матрицы
А
на элемент
b
i,j
матрицы
В
, а резуль-
тат умножения помещает в элемент
с
i,j
матрицы
С
.
Этап 0 для процессора (
i,j
):
.
Процессор (
i,j
) будет иметь доступ к элементу
a
i,i
матрицы
А
за счет того, что
процессоры обмениваются данными между собой. Вопросы обмена данными будут
рассмотрены позднее.
1)
mod(
)1 (
+
−+=
k
l i j
`
j,i
`
j,i
j,i
j,i
BA C C
⋅
+ =
j,i
i,i
j,i
b a c
⋅
=
