Параллельное программирование в стандарте MPI. Баканов В.М - 57 стр.

                                            - 57 -

риц по вычислительным узлам уделяется серьезное внимание. В данной ра-
боте задача распределения содержимого матриц по ВУ не решается, распа-
раллеливаются только вычисления.
  Лежащий на поверхности способ распараллеливания вычислений заключа-
ется в перемножении каждым процессом значений aik и bkj и суммировании
главным процессом этих частичных сумм для получения cij . Однако этот
подход наименее рационален по производительности, ибо каждое умножение
                                3
(а их число пропорционально N ) сопровождается минимум 3 обменами,
причем длительность каждого намного превышает длительность операции
умножения. Кроме того, при таком способе велика избыточность пересылок
(и aik и bkj участвуют в формировании не одного cij , а многих).
  Более рационально в каждом процессе вычислять произведение i-той
строки [A] и j-того столбца [B], в результате сразу получаем готовое значе-
                                                        2
ние cij ; и при этом число обменов (пропорциональное N ) все еще излишне
высоко. Известно, что в языке С/C++ элементы матрицы располагаются в ОП
по строкам (в Fortran’е – по столбцам), поэтому в С пересылка строк запи-
сывается тривиально, а обмен столбцами потребует некоторых ухищрений.
   Еще более эффективно пересылать каждому процессу серию строк (ленту)
матрицы [A] и серию столбцов [B]; этим реализуется крупнозернистый
(coarse-grained) параллелизм (рис.5.1), а метод умножения матриц именуется
ленточным. Каждый процесс при этом вычисляет (определяемый условием
сij , i ∈ [i 1...i 1], i ∈ [j 1... j 2] ) прямоугольный блок матрицы [C]. При программи-
ровании на C для пересылки процессорам вертикальной ленты [B] необхо-
димо использовать временный (рабочий) массив, при программировании на
Fortran’е - то же для горизонтальной ленты [A]. Заметим, что нахождение в
ОП процесса горизонтальной ленты [A] дает возможность вычислить не
только прямоугольный блок сij , i ∈ [i 1...i 1], i ∈ [j 1... j 2] , но и всю вертикальную
ленту сij , i ∈ [ 1...NRA ], i ∈ [j 1... j 2] , см. рис.5.1; для этого необходимо дополни-
тельно пересылать только новые горизонтальные ленты [A]. При программи-
ровании на C для пересылки процессорам вертикальной ленты [B] придется
использовать временный (рабочий) массив, при программировании на For-
tran’е - то же для горизонтальной ленты [A].
   Т.к. обычно число столбцов матрицы [B] много меньше числа строк [A]
(часто NCB=1 и матрица [B] фактически является вектором), в приведенной
ниже программе MM_MPI_2.C матрица [B] пересылается всем процессам це-
ликом.