Введение в практику разработки параллельных программ в стандарте MPI. Баканов В.М - 52 стр.

  Лежащий на поверхности способ распараллеливания заключается в посыл-
ке (в цикле по k-i индексам [A] и соответственно k-j индексам [B]) каждому
процессу значений a ik и b kj , перемножению их процессом, отсылке произ-
ведению главному процессу и суммированию в нем для получения cij . Одна-
ко этот подход наименее рационален по производительности, ибо каждое ум-
                                       3
ножение (а их число пропорционально N , где N – характерный размер мат-
риц) сопровождается минимум 3 обменами, причем длительность каждого
сравнима или превышает длительность операции умножения. Кроме того,
при таком способе велика избыточность пересылок (и a ik и b kj участвуют в
формировании не одного cij , а многих).
  Более рационально при вычислении каждого cij пересылать каждому
процессу i-тую строку [A] и j-тый столбец [B]. При этом в результате
сложения частичных произведений процессом получается готовое cij ,
которое и отсылается главному процессу; однако и при этом число обменов
                      2
(пропорциональное N ) все еще излишне высоко (но оперативная память
процессоров также малонагружена). Известно, что в языке С/C++ элементы
матрицы располагаются в ОП по строкам (в Fortran’е – по столбцам), поэтому
в С пересылка строк записывается тривиально, а обмен столбцами потребует
некоторых ухищрений.
  Более рационально пересылать каждому процессу серию строк матрицы
[A] и серию столбцов [B]; этим реализуется крупнозернистый (coarse-
grained) параллелизм. Каждый процесс при этом вычисляет серию строк мат-
рицы [C], аналогичную по размерам таковой матрицы [A]. При программиро-
вании на C для пересылки процессорам столбцов [B] необходимо использо-
вать временный (рабочий) массив, при программировании на Fortran’е - то
же для серии строк [A]. Недостатком способа является необходимость пере-
сылки серии столбцов [B] между процессорами (алгоритм должен преду-
сматривать определение, в каком процессоре находится нужный столбец
матрицы [B] и пересылку его процессору, который нуждается в нем в данный
момент; такой проблемы не возникает, если матрицу [B] целиком хранить на
каждом процессоре).
  Т.к. обычно число столбцов матрицы [B] много меньше числа строк [A]
(часто NCB=1 и матрица [B] фактически является вектором), приведенной
ниже программе MM_MPI.C матрица [B] пересылается всем процессам цели-
ком (рис.6). При NCB ≅ NCA или затруднениях в размещении матрицы [B]
целиком в ОП узла целесообразно будет разделить [B] на столбцы (см. вы-
ше).




                                    - 52 -