ПАРАЛЛЕЛЬНОЕ ПРОГРАММИРОВАНИЕ
48
Перед тем как рассматривать следующий этап введем понятие деления по
модулю
n
:
•
i
mod
n
=
i
, если
i < n
;
•
i
mod
n
=
i
%
n
, если
i > = n
(
i
%
n
- остаток от деления
i
на
n
).
Теперь перейдем непосредственно к рассмотрению следующего этапа. На пер-
вом этапе процессор (
i,j
) умножает элемент
a
i, (i+1)
mod
n
матрицы
А
на элемент
b
(i+1)
mod
n, j
матрицы
В
. Результат умножения складывается со значением элемента
c
i,j
началь-
ного этапа, и полученная сумма снова помещается в элемент c
i,j
матрицы
С
. Следует
сказать, что элемент
a
i, (i+1)
mod
n
матрицы
А
- это элемент, стоящий непосредственно
справа от диагонального элемента
a
i,i
, если
i
принимает значение от 0 до
n
-2, и эле-
мент
a
i, (i+1)
mod
n
равен элементу
a
i,
0
, если
i
=
n
-1. На рис. 5.4 элементы
a
i, (i+1)
mod
n
по-
казаны для случая, когда
n
= 4.
Рис. 5.4. Распределение блоков матрицы A по процессорам
Аналогично элемент
b
(i+1)
mod
n, j
матрицы
В
- это элемент, стоящий на одну
строчку ниже, в отличие от элемента
b
i,j
этапа 0, если
i
принимает значение от 0 до
n
-2, и элемент
b
(i+1)
mod
n, j
равен элементу
b
0,j
, если
i
=
n
-1.
Этап 1 для процессора (
i,j
):
c
i,j
= c
i,j
+ a
i, (i+1)
mod
n
⋅
b
(i+1)
mod
n, j
.
В общем случае, во время
k-
го этапа процессор (
i,j
) выполняет умножение
элемента
a
i, (i+k)
mod
n
матрицы
А
на элемент
b
(i+k)
mod
n, j
матрицы
В
, и складывает ре-
зультат умножения с элементом
c
i,j
предыдущего этапа. Обозначим через
k
сумму
(
i+k
) mod
n
, тогда этап
k
для процессора (
i,j
) будет выглядеть следующим образом:
c
i,j
= c
i,j
+ a
i,k
⋅
b
k,j
.
После выполнения последнего этапа алгоритма Фокса элемент
c
i,j
будет
представляться в виде следующей суммы:
c
i,j
= a
i,i
⋅
b
i,j
+ a
i,i+1
⋅
b
i+1,j
+...+ a
i,n-1
⋅
b
n-1,j
+ a
i,0
⋅
b
0,j
+...+ a
i,i-1
⋅
b
i-1,j
.
А эта сумма есть не что иное, как сумма произведений элементов
i
-й строки
матрицы
А
на элементы
j
-го столбца матрицы
В
. Таким образом, можно сделать
вывод о том, что алгоритм Фокса для перемножения квадратных матриц порядка
n
и
числа процессоров
p = n
2
работает правильно.
1...,40,41,42,43,44,45,46,47,48,49 51,52,53,54,55,56,57,58,59,60,...180