Участник:NataliaPolienko/Блочное умножение матриц по методу Кеннона

Автор: Полиенко Н.А.

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

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

Одной из основных операций над матрицами является их перемножение. Данная операция широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение [math]C = AB[/math]  квадратных матриц с помощью алгоритма Кеннона. Его суть заключается в том, что матрицы разбиваются на блоки, представляющие собой подматрицы исходных матриц. В следствии чего в качестве базовой подзадачи можно выбрать вычисления, связанные с определением одного из блоков результирующей матрицы [math]C[/math] .

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

Исходные данные: матрица [math]A[/math] размера [math]n \times n[/math], матрица [math]B[/math] размера [math]n \times n[/math].

Вычисляемые данные: матрица [math]C[/math] размера [math]n \times n[/math].

Исходные и результирующая матрицы представляются в виде наборов блоков. Операцию матричного умножения матриц [math]A[/math] и [math]B[/math] в блочном виде можно представить следующим образом : [math] \begin{bmatrix} A_{11} & A_{12} & \cdots & A_{1k} \\ A_{21} & A_{22} & \cdots & A_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ A_{k1} & A_{k2} & \cdots & A_{kk} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} & \cdots & B_{1k} \\ B_{21} & B_{22} & \cdots & B_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ B_{k1} & B_{k2} & \cdots & B_{kk} \end{bmatrix} = \begin{bmatrix} C_{11} & C_{12} & \cdots & C_{1k} \\ C_{21} & C_{22} & \cdots & C_{2k} \\ \vdots & \vdots & \ddots & \vdots \\ C_{k1} & C_{k2} & \cdots & C_{kk} \end{bmatrix}, [/math]

где каждый блок [math]C_{ij}[/math] матрицы [math]C[/math] определяется в соответствии с выражением:

[math] \begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align} [/math]

Полученные блоки [math]C_{ij}[/math] являются независимыми.

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

Вычислительное ядро перемножения матриц(квадратных) методом Кеннона можно составить из множественных вычислений умножения блоков матрицы [math]A[/math] на блоки матрицы [math]B[/math], таким образом получая блок результирующей матрицы [math]C[/math]:

[math] \begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align} [/math]

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

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

[math] \begin{align} \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align} [/math]

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

Алгоритм осуществляет последовательное вычисление блоков результирующей матрицы [math]C[/math]:

1. Матрицы [math]A[/math], [math]B[/math] разбиваются на блоки фиксированного размера(будем предполагать, что блоки квадратные и порядок матрицы делится на размер блока без остатка).

2. На одной итерации цикла по переменной [math]i[/math] используется первая строка, состоящая из блоков матрицы [math]A[/math] и все столбцы, состоящие из блоков матрицы [math]B[/math]:

[math] \begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align} [/math]

1.6 Последовательная сложность алгоритма

Для перемножения матриц размера [math]n \times n[/math] в последовательной реализации алгоритма требуется [math]n^3[/math] умножений и сложений.

1.7 Информационный граф

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Граф алгоритма умножения квадратных матриц методом Кеннона состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция вычисляет функцию f, где [math]f = с+a*b[/math].

Естественно введённые координаты области таковы:

• [math]i[/math] — меняется в диапазоне от [math]1[/math] до [math]m[/math], принимая все целочисленные значения;
• [math]j[/math] — меняется в диапазоне от [math]1[/math] до [math]m[/math], принимая все целочисленные значения;
• [math]k[/math] — меняется в диапазоне от [math]1[/math] до [math]m[/math], принимая все целочисленные значения.

Аргументы операции следующие:

• [math]k = 1[/math]:
  • [math]c = 0[/math];
  • [math]a[/math]: элемент входных данных, а именно блок матрицы [math]A[/math] с координатами [math]i, j[/math];
  • [math]b[/math] - элемент входных данных, а именно блок матрицы [math]B[/math] с координатами [math]i, j[/math];
• [math]k \gt 1[/math]:
  • [math]c[/math] - результат срабатывания операции, соответствующей вершине с координатами [math]i, j, k-1[/math];
  • [math]a[/math]: элемент, переданный из вершины [math]i, j+1, k-1[/math], являющийся элементом(блоком) матрицы [math]A[/math];
  • [math]b[/math]: элемент, переданный из вершины [math]i+1, j, k-1[/math], являющийся элементом(блоком) матрицы [math]B[/math];

При [math]k \lt m[/math] - результатом выполнения операции является промежуточные данные алгоритма; При [math]k = m[/math] - выходными данными алгоритма([math]C_{ij}[/math]) будут являться результаты выполнения операции в узлах.

Описанный граф можно посмотреть на рис.1 и рис.2, выполненных для случая [math]m = 3[/math]([math]m [/math] - количество блоков, на которые разбиты исходные матрицы [math]A[/math] и [math]B[/math] ).Здесь красными стрелками указана циклическая передача данных, соответствующих блоку матрицы [math]A[/math], а зелеными стрелками - матрицы [math]B[/math]. На рис.1 показан граф алгоритма согласно классическому определению , на рис.2 к графу алгоритма добавлены вершины , соответствующие входным (обозначены синим цветом) и выходным (обозначены розовым цветом) данным.

Рисунок 1. Умножение квадратных матриц методом Кеннона

Рисунок 2. Умножение квадратных матриц методом Кеннона с входными и выходными параметрами

1.8 Ресурс параллелизма алгоритма

Для алгоритма умножения квадратных матриц методом Кеннона размера [math]n \times n[/math] в параллельном варианте требуется последовательно выполнить следующие ярусы:

• по [math]m/k[/math] ярусов умножений и сложений (в каждом из ярусов — [math](m/k)^2[/math] операций, где [math]m/k[/math] - количество элементов в блоке).

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

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

1.9 Входные и выходные данные алгоритма

Входные данные: матрица [math]A[/math], матрица [math]B[/math].

Объём входных данных: [math]n \times n + n \times n[/math]

Выходные данные: матрица [math]C[/math] .

Объём выходных данных: [math]n \times n[/math]

2 Программная реализация алгоритма

2.4 Масштабируемость алгоритма и его реализации

Проведём исследование масштабируемости параллельной реализации перемножения матриц методом Кеннона. Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.

Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессоров [4:128];
• размер матрицы [500:5000].

В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:

• минимальная эффективность реализации 0.18%;
• максимальная эффективность реализации 99.9831%.

Ниже приведены графики зависимости вычислительного времени алгоритма и его эффективности от изменяемых параметров запуска — размера данных и числа процессоров:

Рисунок 3. Параллельная реализация перемножения матриц методом Кеннона. Зависимость времени, затраченного на счетную часть от числа процессоров и размера матриц.

Рисунок 4. Параллельная реализация перемножения матриц методом Кеннона. Изменение эффективности в зависимости от числа процессоров и размера матриц.

Проведем оценки масштабируемости:

• По числу процессов: при увеличении числа процессов на всей рассмотренной области изменений параметров запуска эффективность убывает достаточно интенсивно. Уменьшение эффективности на рассмотренной области работы параллельной программы связано с увеличением числа пересылок, с ростом числа процессов и как следствие ростом накладных расходов на организацию вычислений. Присутствует область, на которой при увеличении числа процессов эффективность возрастает, но при дальнейшем росте продолжает снижаться. Это объясняется декомпозицей данных, при которой наступает момент, когда размер матрицы позволяет блокам укладываться в КЭШ-память.
• По размеру задачи: при увеличении размера задачи эффективность в целом уменьшается по рассматриваемой области, хотя и менее интенсивно, чем при увеличении числа процессов. Снижение эффективности объясняется тем, что при росте вычислительной сложности существенно возрастают объемы передаваемых данных. Присутствует область возрастания эффективности, на всех рассмотренных размерах матрицы. Это объясняется тем, что при малом размере задачи данные хорошо укладываются в КЭШ память, что приводит к высокой эффективности работы приложения при малом размере задачи. При дальнейшем увеличении размера эффективность уменьшается при выходе за границы КЭШ-памяти.
• По двум направлениям: при рассмотрении увеличения, как вычислительной сложности, так и числа процессов по всей рассмотренной области значений уменьшается, интенсивность уменьшения эффективности не очень высока. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров составляет около 99% говорит о том, что уменьшение эффективности по всей области довольно интенсивно. На остальной области значений параметров изменения эффективности не столь значительны и находятся на приблизительно одном и том же уровне.