Стр. 51 - Параллельное программирование
Упрощенная HTML-версия
ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
49
Блочная реализация (
p
<
n
2
)
Очевидно, что при решении практических задач требование
p = n
2
является
трудно выполнимым. Так, при умножении двух матриц порядка
n
= 100 уже требу-
ется 10 000 процессоров. Естественным решением проблемы является назначение
процессорам не отдельных элементов, а квадратных подматриц порядка
n/(p
1/2
)
от
каждой из матриц
A, B
и
С
. В этом случае алгоритм Фокса будет выполнять умно-
жение матриц
А
и
В
за
p
1/2
этапов. На каждом этапе процессор (
i,j
) будет получать
подматрицу
C
i
,
j
, формула для вычисления которой имеет вид, аналогичный формуле
для вычисления элемента
с
i,j
матрицы
С
, с той лишь разницей, что вместо элементов
a
i,j
и
b
i,j
следует использовать подматрицы
A
i,j
и
B
i,j
и
i,j
будут изменяться от 0 до
p
1/2
- 1. В этом случае этап
k
для процессора (
i,j
) будет иметь следующий вид:
(
i,j
):
C
i,j
=
C
i,j
+
A
i
,
k
⋅
B
k
,
j
Единственной проблемой при таком подходе является отсутствие какой-либо
гарантии в том, что
n/(p
1/2
)
будет целым числом. Основная сложность состоит в не-
известности порядка матриц
n
, так как
p
1/2
можно сделать целым числом, если из
общего числа процессоров взять то число, из которого извлекается корень, а остав-
шиеся процессоры будут просто неработающими. Трудности, связанные с порядком
матриц, могут быть преодолены за счет введения недостающих строк и столбцов,
заполненных нулевыми элементами. В дальнейшем будем полагать, что
n/(p
1/2
)
- це-
лое число.
Пример работы алгоритма Фокса
Рассмотрим работу алгоритма Фокса на примере умножения матриц 6-го по-
рядка на 9-ти процессорах, то есть
n
=6, а
p
=9. В этом случае каждому процессору
назначается подматрица порядка
n/(p
1/2
)
= 2 от каждой из матриц
А, В
и
С,
и алго-
ритм Фокса выполняет умножение матриц за
p
1/2
= 3 этапа:
Рис. 5.5. Этап 0 (шаг 1 (слева), шаг 2 (в центре), шаг 3 (справа))
На начальном этапе происходит рассылка подматриц
A
i,i
, стоящих на главной
диагонали, процессорам, работающим с подматрицами в той же строке. Далее на
