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

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

- 62 -
Алгоритм Фокса иногда именуется клеточным (ибо основан на распреде-
лении блоков матриц по ОП процессов по принципу шахматной доски), этот
алгоритм описан также в работах [3,7]; ограничением его является (непре-
менное) условие M=Q
2
и N % Q = 0 (N – порядок перемножаемых матриц, M
– число процессов, виртуально распределенных на квадратную сетку разме-
ров Q
×
Q, причем каждый процесс связан с блоком размером N/Q
×
N/Q эле-
ментов матриц). Алгоритм Кэннона отличается более разумным распределе-
нием блоков исходных матриц по процессорам, при этом упрощается схема
обмена данными между последними.
Например, при умножении матриц размером 6
×
6 по алгоритму Фокса при
9 процессах каждому из них передаются подматрицы размером
MNQN
N
'
==
=2 следующим образом (процессоры объединены квадрат-
ной сеткой размерности Q, нумерация везде начинается с 0):
Процесс 0
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
1110
0100
00
Процесс 1
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
1312
0302
01
Процесс 2
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
1114
0504
02
Процесс 3
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
3130
2120
10
Процесс 4
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
3332
2322
11
Процесс 5
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
3534
2524
12
Процесс 6
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
5150
4140
20
Процесс 7
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
5352
4342
21
Процесс 8
⎟
⎟
⎠
⎞
⎜
⎜
⎝
⎛
=
aa
aa
A
5554
4544
22
В общем случае действия перемножения матриц иллюстрируются сле-
дующим алгоритмом [3]:
for(step=0; step<Q; step++)
{
1. Выбрать подматрицу матрицы [A] в каждой строке процессов (в r-той строке
находится подматрица A
ru
, где u=(r+step) mod Q).
2. Для процессов каждой строки переслать всем иным процессом той же стро-
ки выбранную подматрицу.
3. Каждый процесс умножает полученную подматрицу матрицы [A] на находя-
щуюся в ОП процесса подматрицу матрицы [B].
4. Для каждого процесса переслать подматрицу матрицы [B] процессу, нахо-
дящемуся в решетке выше (из первой строки пересылка идет в последнюю
строку).
}
Вариант умножения матриц в соответствие с алгоритмом Фокса
mm_fox.c
может быть получен у преподавателя (исходный текст не приводится). 
                                           - 62 -

  Алгоритм Фокса иногда именуется клеточным (ибо основан на распреде-
лении блоков матриц по ОП процессов по принципу шахматной доски), этот
алгоритм описан также в работах [3,7]; ограничением его является (непре-
                     2
менное) условие M=Q и N % Q = 0 (N – порядок перемножаемых матриц, M
– число процессов, виртуально распределенных на квадратную сетку разме-
ров Q × Q, причем каждый процесс связан с блоком размером N/Q × N/Q эле-
ментов матриц). Алгоритм Кэннона отличается более разумным распределе-
нием блоков исходных матриц по процессорам, при этом упрощается схема
обмена данными между последними.
  Например, при умножении матриц размером 6 × 6 по алгоритму Фокса при
9 процессах каждому из них передаются подматрицы размером
N ' = N Q = N M =2 следующим образом (процессоры объединены квадрат-
ной сеткой размерности Q, нумерация везде начинается с 0):

         Процесс 0                  Процесс 1                Процесс 2

           ⎛ a 00 a 01⎞               ⎛ a 02 a 03 ⎞            ⎛ a 04 a 05 ⎞
     A00 = ⎜⎜         ⎟⎟       A01 = ⎜⎜           ⎟⎟     A02 = ⎜⎜          ⎟⎟
             a
           ⎝ 10   a11 ⎠                 a
                                      ⎝ 12   a13 ⎠               a
                                                               ⎝ 14   a 11 ⎠
         Процесс 3                  Процесс 4                Процесс 5

           ⎛ a 20 a 21⎞               ⎛ a 22 a 23 ⎞            ⎛ a 24 a 25 ⎞
     A10 = ⎜⎜         ⎟⎟        A11 = ⎜⎜          ⎟⎟     A12 = ⎜⎜          ⎟⎟
           ⎝ a30 a31 ⎠                ⎝ a32 a33 ⎠              ⎝ a34 a35 ⎠
         Процесс 6                  Процесс 7                Процесс 8

            ⎛ a 40 a 41⎞               ⎛ a 42 a 43 ⎞            ⎛ a 44 a 45 ⎞
     A20 = ⎜⎜          ⎟⎟      A21 = ⎜⎜            ⎟⎟    A22 = ⎜⎜           ⎟⎟
            ⎝ a50 a51 ⎠                ⎝ a52 a53 ⎠              ⎝ a54 a55 ⎠

  В общем случае действия перемножения матриц иллюстрируются сле-
дующим алгоритмом [3]:

  for(step=0; step

Страницы