Участник:NataliaPolienko/Блочное умножение матриц по методу Кеннона: различия между версиями
| Строка 65: | Строка 65: | ||
=== Схема реализации последовательного алгоритма === | === Схема реализации последовательного алгоритма === | ||
| − | + | Алгоритм осуществляет последовательное вычисление блоков результирующей матрицы <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> | ||
=== Последовательная сложность алгоритма === | === Последовательная сложность алгоритма === | ||
| + | Для перемножения матриц размера <math>n \times n</math> в последовательной реализации алгоритма требуется <math>n^3</math> умножений и сложений. | ||
=== Информационный граф === | === Информационный граф === | ||
=== Ресурс параллелизма алгоритма === | === Ресурс параллелизма алгоритма === | ||
| + | Для алгоритма умножения квадратных матриц методом Кеннона размера <math>n \times n</math> в параллельном варианте требуется последовательно выполнить следующие ярусы: | ||
| + | |||
| + | * по <math>m/k</math> ярусов умножений и сложений (в каждом из ярусов — <math>(m/k)^2</math> операций, где <math>m/k<math> - количество элементов в блоке). | ||
| + | |||
| + | При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти. | ||
| + | |||
| + | При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида). | ||
=== Входные и выходные данные алгоритма === | === Входные и выходные данные алгоритма === | ||
| − | Входные данные: | + | '''Входные данные''': матрица <math>A</math>, матрица <math>B</math>. |
| + | |||
| + | '''Объём входных данных''': <math>n \times n + n \times n</math> | ||
| + | |||
| + | '''Выходные данные''': матрица <math>C</math> . | ||
| − | + | '''Объём выходных данных''': <math>n \times n</math> | |
=== Свойства алгоритма === | === Свойства алгоритма === | ||
Версия 12:21, 24 ноября 2017
Автор: Полиенко Н.А.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Одной из основных операций над матрицами является их перемножение. Данная операция широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение C = AB квадратных матриц с помощью алгоритма Кеннона. Его суть заключается в том, что матрицы разбиваются на блоки, представляющие собой подматрицы исходных матриц. В следствии чего в качестве базовой подзадачи можно выбрать вычисления, связанные с определением одного из блоков результирующей матрицы C [1].
1.2 Математическое описание алгоритма
Исходные данные: матрица A размера n \times n, матрица B размера n \times n.
Вычисляемые данные: матрица C размера n \times n.
Исходные и результирующая матрицы представляются в виде наборов блоков. Операцию матричного умножения матриц A и B в блочном виде можно представить следующим образом [2]: \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},
где каждый блок C_{ij} матрицы C определяется в соответствии с выражением:
- \begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}
Полученные блоки C_{ij} являются независимыми.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро перемножения матриц(квадратных) методом Кеннона можно составить из множественных вычислений умножения блоков матрицы A на блоки матрицы B, таким образом получая блок результирующей матрицы C:
- \begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}
1.4 Макроструктура алгоритма
Как записано в описании ядра алгоритма, основную часть метода составляют множественные вычисления умножений блоков матрицы A на блоки матрицы B:
- \begin{align} \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}
1.5 Схема реализации последовательного алгоритма
Алгоритм осуществляет последовательное вычисление блоков результирующей матрицы C: 1. Матрицы A, B разбиваются на блоки фиксированного размера(будем предполагать, что блоки квадратные и порядок матрицы делится на размер блока без остатка). 2. На одной итерации цикла по переменной i используется первая строка, состоящая из блоков матрицы A и все столбцы, состоящие из блоков матрицы B: \begin{align} C_{ij} = \sum_{l = 1}^{k} A_{il} B_{lj}, \quad i \in [1, k], \quad j \in [1, k]. \end{align}
1.6 Последовательная сложность алгоритма
Для перемножения матриц размера n \times n в последовательной реализации алгоритма требуется n^3 умножений и сложений.
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Для алгоритма умножения квадратных матриц методом Кеннона размера n \times n в параллельном варианте требуется последовательно выполнить следующие ярусы:
- по m/k ярусов умножений и сложений (в каждом из ярусов — (m/k)^2 операций, где m/k\lt math\gt - количество элементов в блоке). При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти. При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида). === Входные и выходные данные алгоритма === '''Входные данные''': матрица \lt math\gt A, матрица B.
Объём входных данных: n \times n + n \times n
Выходные данные: матрица C .
Объём выходных данных: n \times n
