Умножение матриц (блочный алгоритм Фокса)

Содержание

Описание параллельного метода

Пусть А и В - квадратные матрицы порядка n, а p - общее число процессоров. Ниже рассмотрим следующие вопросы:

случай p = n²
блочная реализация ( p < n² )
пример работы Fox's алгоритма

Случай p = n²

     В данном случае получается, что каждому процессору назначается по одному элементу от каждой из матриц А, В и С. Распределим элементы матриц между процессорами следующим образом. Процессору с номером i*n+j ( в дальнейшем процессору (i,j) ) назначим элементы матриц А, В и С, находящиеся в i-той строке и j-том столбце. Здесь i,j изменяются от 0 до n-1. В данном частном случае Fox's алгоритм будет выполнять умножение матриц А и В за n этапов. Примем, что начальный этап имеет номер 0, а последний этап номер n-1. Тогда на начальном этапе процессор(i,j) умножает диагональный элемент a_i,i матрицы А на элемент b_i,j матрицы В, а результат умножения помещает в элемент с_i,j матрицы С:

этап 0 для процессора (i,j): c_i,j = a_i,i * b_i,j

Процессор (i,j) будет иметь доступ к элементу a_i,i матрицы А за счет того, что процессоры обмениваются данными между собой. Вопросы обмена данными будут рассмотрены позднее.
      Перед тем как рассматривать следующий этап, введем понятие деления по модулю 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. На рисунке элементы a_{i, (i+1) mod n} показаны для случая, когда n = 4.

Аналогично элемент 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) будет выглядеть следующим образом:

этап k для процессора (i,j): c_i,j = c_i,j + a_i,k * b_k,j

После выполнения последнего этапа Fox's алгоритма элемент 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-того столбца матрицы В. Таким образом, можно сделать вывод о том, что Fox's алгоритм для перемножения квадратных матриц порядка n и числа процессоров p = n² работает правильно.

Блочная реализация ( p < n² )

Очевидно, что при решении практических задач требование p = n² является трудно выполнимым. Так, при умножении двух матриц порядка n = 100 уже требуется 10 000 процессоров. Естественным решением проблемы является назначение процессорам не отдельных элементов, а квадратных подматриц порядка n/(p^1/2) от каждой из матриц A, B и С. В этом случае Fox's алгоритм будет выполнять умножение матриц А и В за p^1/2 этапов. На каждом этапе процессор (i,j) будет получать подматрицу C_i,j, формула для вычисления которой имеет вид, аналогичный формуле для вычисления элемента с_i,j матрицы С, с той лишь разницей, что вместо элементов a_i,j и b_i,j следует использовать подматрицы A_i,j и B_i,j и i,j будут изменяться от 0 до p^1/2 - 1. В этом случае этап k для процессора (i,j) будет иметь следующий вид:

этап k для процессора (i,j): C_i,j = C_i,j + A_i,k * B_k,j

Единственной проблемой при таком подходе является отсутствие какой либо гарантии в том, что n/(p^1/2) будет целым числом. Основная сложность состоит в неизвестности порядка матриц n, т.к. p^1/2 можно сделать целым числом, если из общего числа процессоров взять только то число, из которого извлекается корень, а оставшиеся процессоры будут просто неработающими. Трудности, связанные с порядком матриц могут быть преодолены за счет введения недостающих строк и столбцов, заполненных нулевыми элементами. В дальнейшем будем полагать, что n/(p^1/2) - целое число.

Пример работы Fox's алгоритма

Рассмотрим работу Fox's алгоритма на примере умножения матриц 6-го порядка на 9-ти процессорах, то есть n=6, а p=9. В этом случае каждому процессору назначается подматрица порядка n/(p^1/2) = 2 от каждой из матриц А, В и С и Fox's алгоритм выполняет умножение матриц за p^1/2 = 3 этапа:

Этап 0 ( шаг 1 ( слева ), шаг 2 ( по центру ), шаг 3 ( справа ) ):

На начальном этапе происходит рассылка подматриц A_i,i, стоящих на главной диагонали, процессорам, работающим с подматрицами в той же строке. Далее на каждом процессоре происходит умножение полученной диагональной подматрицы A_i,i на подматрицу B_i,j, хранящуюся на данном процессоре. Результат умножения помещается в подматрицу C_i,j процессора (i,j). Здесь i,j изменяются от 0 до 2. Перед переходом к следующему этапу происходит перемещение подматрицы B_i,j от процессора (i,j) к процессору (i-1,j), то есть к непосредственно "верхнему" процессору. Процессоры нулевой строки посылают подматрицы B_0,j процессорам последней ( в данном случае второй ) строки.

Этап 1 ( слева ) и этап 2 ( справа ):

На первом этапе также происходит рассылка, но только уже подматриц A_{i,(i+1) mod q}, где q = p^1/2 = 3, а i изменяется от 0 до 2. То есть процессоры нулевой, первой и второй строк получат подматрицы A_0,1, A_1,2 и A_2,0 соответственно. Далее на каждом процессоре происходит умножение полученной подматрицы A_{i,(i+1) mod 3} на подматрицу B_i,j, полученную на предыдущем этапе от процессора непосредственно нижней строки. Результат умножения складывается с подматрицей С_i,j и снова в нее записывается. Перед переходом к следующему этапу снова происходит восходящее перемещение подматриц B_i,j, аналогичное их перемещению на этапе 0.
Второй ( и в данном случае последний ) этап работы Fox's алгоритма полностью аналогичен предыдущим этапам и может быть описан следующей последовательностью шагов:

рассылка подматрицы A_{i,(i+2) mod 3} процессорам i-той строки ( на рисунке эти подматрицы выделены )
умножение на процессоре (i,j) подматриц A_{i,(i+2) mod 3} и B_i,j ( Понятно, что в общем случае, подматрицы B_i,j на данном этапе и предыдущем не совпадают )
C_i,j = C_i,j + A_{i,(i+2) mod 3} * B_i,j

Заметим также, что перемещение подматриц B_i,j на последнем этапе является излишним. После заключительного этапа мы получим 9 подматриц С_i,j, которые будут составлять матрицу С, являющуюся решением данной задачи.