Блочно-рекурсивный параллельный алгоритм перемножения матриц
Поможем в ✍️ написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

 

Будем считать, что количество процессорных элементов p вычислительной системы является степенью числа 4.

Рассмотрим задачу вычисления произведения квадратных матриц X = A*B размерности n на вычислительной системе с n процессорными элементами. Матрицы A и B рассмотрим, как блочные матрицы 2*2 с квадратными блоками размера (n/2) * (n/2). Всего в каждой матрице получается по 4 блока. Обозначим Aij , i,j = 1,2, блоки матрицы A. Аналогично обозначим блоки матрицы B.

Множество всех процессорных элементов разобьем на 4 равных группы с номерами 0, 1, 2, 3. Разместим элементы обоих матриц поблочно – в каждой группе модулей памяти по одному:

Блок Aij , i,j = 1,2, матрицы A разместим в группе модулей памяти с номером (i-1)*2 + j-1.

Блок  Bij , i,j = 1,2, матрицы B разместим в группе модулей памяти с номером (j-1)*2 + i-1.

 

Модуль памяти 0 A11, B11, C11 Модуль памяти 1  A12, B21, C12 
Модуль памяти 2 A21, B12, C21 Модуль памяти 3 A22, B22, C22

 

 

 

 

 Рис. 58 Соответствие 4 групп процессорных элементов блокам матрицы.

 

B11 B21
  B12   B22
A11*B11 A12*B21  
A21*B12   A22*B22

 

Рис. 59. Первое перемножение блоков и первая группа пересылок.

 

A11*B12 A12*B22  
A21*B11   A22*B21
A11*B12 A12*B21  
A21*B12 A22*B21  

 

 

Рис. 60. Второе перемножение блоков и вторая группа пересылок.

 

 

Модуль памяти 0   C11 = A11*B11 + A12*B21 Модуль памяти 1   C12 = A12*B22 + A11*B12
Модуль памяти 2   C21 = A21*B11 + A22*B21 Модуль памяти 3   C22 = A21*B12 + A22*B22

 

 

 Рис. 61 Сложение блоков.

 

Для вычисления произведения матриц в этом случае требуется два перемножения блоков, два сложения блоков и две пересылки блоков. 

Перемножения блоков в каждой группе процессорных элементов можно выполнять по такой же схеме рекурсивно. Всего у этого алгоритма log4p шагов. На каждом шаге размерности блоков в два раза уменьшаются, но количество блоков в 4 раза возрастает.

 

 

 

0.0 0.1 1.0 1.1
0.2 0.3 1.2 1.3
2.0 2.1 3.0 3.1
2.2 2.3 3.2 3.3

 

Рис. 62. Разбиение каждой из 4 групп ПЭ еще на 4 группы второго уровня. При двойной нумерации цифра перед точкой означает номер группы ПЭ первого уровня. Цифра после точки – номер группы ПЭ второго уровня.

 

Количество параллельных шагов с умножениями (скалярными) в данном алгоритме, как и в других известных параллельных алгоритмах, равно n3/p. При наличии p процессорных элементов и при базовом последовательном алгоритме перемножения матриц со сложностью n3 – эта формула, очевидно, не улучшаема. 

Для пересылок данных в этом алгоритме удобно использовать полнодоступный коммутатор или (log2p)-мерный куб. Всего в этом алгоритме получается 2*log4p = log2p блочных пересылок.

 

На каждом шаге пересылается n2 элементов по p штук одновременно. Всего скалярных пересылочных шагов n2/p . Итого, общее количество скалярных пересылочных шагов n2*log2p/p . Если p = n, то количество одновременных скалярных пересылок равно n*log2n – это существенно меньше, чем при размещениях матриц по строкам или столбцам и меньше, чем пересылок в алгоритмах Кэннона и Фокса [35]. 

Перемножение прямоугольных матриц тоже может быть выполнено блочно-рекурсивным алгоритмом. Действительно, пусть требуется перемножить матрицу A размера n*m на матрицу B размера m*k. Обозначим q = p1/2 . Разобьем матрицу A на блоки размера (n/q)*(m/q) , а матрицу B на блоки размера (m/q)*(k/q). Тогда задача перемножения прямоугольных матриц будет сведена к задаче перемножения квадратных блочных матриц размера q * q , где q = p1/2 .      

 

Блочно-рекурсивное размещение данных предполагает количество процессорных элементов (вычислительных узлов) равным степени четверки. Это жесткое ограничение. Иногда, если количество ПЭ равно степени четверки, умноженной на некоторое число, можно комбинировать блочно-рекурсивное размещение данных с блочно-аффинным. На следующем рисунке изображено такое размещение для случая 12 ПЭ.

 

Группа ПЭ 0
0 A11 B11
1 A12 B21
2 A13 B31

 

 

Группа ПЭ 1
3 A14 B41
4 A15 B51
5 A16 B61

 

Группа ПЭ 2
6 A21 B12
7 A22 B22
8  A23 B32

 

 

Группа ПЭ 3
9 A24 B42
10 A25 B52
11 A26 B62

 

 

Рис. 63. Вычислительная система состоит из 12 ПЭ, которые разбиваются на 4 группы по 3 ПЭ в каждой.

 

В данном примере матрицы разбиваются на блоки следующим образом:

A = {Aij} i = 1,2, j = 1,…,6 ; B = {Bij} i = 1,2, j = 1,…,6 

 

 

Дата: 2018-12-21, просмотров: 322.