Алгоритм Фокса умножения матриц

Свойства и структура алгоритмов

Общее описание алгоритма

Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.

Математическое описание алгоритма

Исходные данные: квадратная матрица [math]\displaystyle{ A }[/math] (состоит из блоков [math]\displaystyle{ A_{ij} }[/math]), квадратная матрица [math]\displaystyle{ B }[/math] (состоит из блоков [math]\displaystyle{ B_{ij} }[/math]).

Вычисляемые данные: квадратная матрица [math]\displaystyle{ C }[/math] (состоит из блоков [math]\displaystyle{ C_{ij} }[/math]).

При этом каждый блок [math]\displaystyle{ C_{ij} }[/math] определяется как произведение соответствующих блоков матриц [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] :

[math]\displaystyle{ \begin{align} C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1]. \end{align} }[/math]

Вычислительное ядро алгоритма

Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы [math]\displaystyle{ A }[/math] на блоки матрицы [math]\displaystyle{ B }[/math]

[math]\displaystyle{ \begin{align} \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1]. \end{align} }[/math]

Макроструктура алгоритма

Как уже записано в описании ядра алгоритма, основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы [math]\displaystyle{ A }[/math] на блоки матрицы [math]\displaystyle{ B }[/math]. Перемножать блоки будем стандартным методом, используя определение произведения матриц:

[math]\displaystyle{ \begin{align} \sum_{k = 1}^{n} a_{ik} b_{kj} \end{align} }[/math]

Схема реализации последовательного алгоритма

Вначале производится рассылка в процесс с координатами (i, j) блоков Aij, Bij исходных матриц. Кроме того, выполняется обнуление матрицы Cij, предназначенной для хранения соответствующего блока результирующего произведения AB. Затем запускается цикл по m (m = 0, …, q), в ходе которого выполняются три действия:

• для каждой строки i (i = 0, …, q) блок Aij одного из процессов пересылается во все процессы этой

же строки; при этом индекс j пересылаемого блока определяется по формуле j = (i + m) mod q;

• полученный в результате подобной пересылки блок матрицы A и содержащийся в процессе (i, j)

блок матрицы B перемножаются, и результат прибавляется к матрице Сij;

• для каждого столбца j (j = 0, …, q) выполняется циклическая пересылка блоков матрицы B, содержащихся в каждом процессе (i, j) этого столбца, в направлении убывания номеров строк.

После завершения цикла в каждом процессе будет содержаться матрица Cij, равная соответствующему блоку произведения AB. Останется переслать эти блоки главному процессу.

Литература

1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007