Перемножение плотных неособенных матриц (последовательный вещественный вариант): различия между версиями
(Добавление категории.) |
ASA (обсуждение | вклад) |
||
(не показано 25 промежуточных версий 6 участников) | |||
Строка 1: | Строка 1: | ||
− | + | {{level-a}} | |
− | == | + | Основные авторы описания: [[Участник:Frolov|А.В.Фролов]]. |
+ | |||
+ | == Свойства и структура алгоритма == | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
'''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. | '''Перемножение матриц''' - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. | ||
− | Здесь мы рассмотрим умножение <math> | + | Здесь мы рассмотрим умножение <math>C = AB</math> плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>. |
− | === Математическое описание === | + | === Математическое описание алгоритма === |
Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), плотная матрица <math>B</math> (элементы <math>b_{ij}</math>). | Исходные данные: плотная матрица <math>A</math> (элементы <math>a_{ij}</math>), плотная матрица <math>B</math> (элементы <math>b_{ij}</math>). | ||
Строка 17: | Строка 19: | ||
:<math> | :<math> | ||
\begin{align} | \begin{align} | ||
− | c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad | + | c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l]. |
\end{align} | \end{align} | ||
</math> | </math> | ||
Строка 33: | Строка 35: | ||
=== Макроструктура алгоритма === | === Макроструктура алгоритма === | ||
− | Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения | + | Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные (всего <math>ml</math>) вычисления скалярных произведений строк матрицы <math>A</math> на столбцы матрицы <math>B</math> |
:<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math> | :<math>\sum_{k = 1}^{n} a_{ik} b_{kj}</math> | ||
Строка 39: | Строка 41: | ||
в режиме накопления или без него. | в режиме накопления или без него. | ||
− | === | + | === Схема реализации последовательного алгоритма === |
Для всех <math>i</math> от <math>1</math> до <math>m</math> и для всех <math>j</math> от <math>1</math> до <math>l</math> выполняются | Для всех <math>i</math> от <math>1</math> до <math>m</math> и для всех <math>j</math> от <math>1</math> до <math>l</math> выполняются | ||
Строка 57: | Строка 59: | ||
* по <math>mnl</math> умножений и сложений. | * по <math>mnl</math> умножений и сложений. | ||
− | При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения | + | При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матриц. |
При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам ''с кубической сложностью'' (в случае неквадратных матриц - с ''трилинейной''). | При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам ''с кубической сложностью'' (в случае неквадратных матриц - с ''трилинейной''). | ||
Строка 74: | Строка 76: | ||
Аргументы операции следующие: | Аргументы операции следующие: | ||
*<math>a</math>: | *<math>a</math>: | ||
− | ** при <math>k = 1</math> константа <math>0 | + | ** при <math>k = 1</math> константа <math>0</math>; |
** при <math>k > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j, k-1</math>; | ** при <math>k > 1</math> — результат срабатывания операции, соответствующей вершине с координатами <math>i, j, k-1</math>; | ||
*<math>b</math> — элемент ''входных данных'', а именно <math>a_{ik}</math>; | *<math>b</math> — элемент ''входных данных'', а именно <math>a_{ik}</math>; | ||
Строка 80: | Строка 82: | ||
Результат срабатывания операции является: | Результат срабатывания операции является: | ||
− | + | * при <math>k < n</math> - ''промежуточным данным'' алгоритма; | |
− | + | * при <math>k = n</math> - выходным данным <math>c_{ij}</math>. | |
+ | |||
+ | [[file:Dense mtrx product.png|thumb|center|800px|Рисунок 1. Умножение плотных матриц с отображением выходных данных]] | ||
+ | <br/> | ||
+ | |||
+ | <center> | ||
+ | Интерактивное изображение графа алгоритма без входных и выходных данных для случая перемножения двух квадратных матриц порядка 3 и 4 | ||
+ | </center> | ||
+ | |||
+ | {{#widget:Algoviewer | ||
+ | |url=mat_mul/mat_mul_3/Algo_view_matrix3.html | ||
+ | |width=600 | ||
+ | |height=400 | ||
+ | |border=1 | ||
+ | }} | ||
− | + | {{#widget:Algoviewer | |
+ | |url=mat_mul/mat_mul_4/Algo_view_matrix4.html | ||
+ | |width=600 | ||
+ | |height=400 | ||
+ | |border=1 | ||
+ | }} | ||
− | === | + | === Ресурс параллелизма алгоритма === |
Для алгоритма умножения квадратных матриц порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы: | Для алгоритма умножения квадратных матриц порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы: | ||
Строка 97: | Строка 118: | ||
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти. | При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти. | ||
− | При классификации по высоте ЯПФ, таким образом, алгоритм умножения | + | При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам ''с линейной сложностью''. При классификации по ширине ЯПФ его сложность также будет ''квадратичной'' (для квадратных матриц) или ''билинейной'' (для матриц общего вида). |
− | === | + | === Входные и выходные данные алгоритма === |
'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), матрица <math>B</math> (элементы <math>b_{ij}</math>)). | '''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), матрица <math>B</math> (элементы <math>b_{ij}</math>)). | ||
Строка 115: | Строка 136: | ||
При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – ''линейно''. | При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – ''линейно''. | ||
− | При этом алгоритм умножения | + | При этом алгоритм умножения матриц полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается. |
− | == Программная реализация == | + | == Программная реализация алгоритма == |
=== Особенности реализации последовательного алгоритма === | === Особенности реализации последовательного алгоритма === | ||
Строка 137: | Строка 158: | ||
При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности. | При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности. | ||
− | + | === Возможные способы и особенности параллельной реализации алгоритма === | |
− | + | === Результаты прогонов === | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | === Возможные способы и особенности | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | === | ||
=== Выводы для классов архитектур === | === Выводы для классов архитектур === | ||
− | |||
== Литература == | == Литература == | ||
− | + | <references /> | |
+ | [[Категория:Законченные статьи]] | ||
+ | [[Категория:Матричные операции]] | ||
− | [[ | + | [[En:Dense matrix multiplication (serial version for real matrices)]] |
Текущая версия на 10:53, 8 июля 2022
Основные авторы описания: А.В.Фролов.
Содержание
- 1 Свойства и структура алгоритма
- 1.1 Общее описание алгоритма
- 1.2 Математическое описание алгоритма
- 1.3 Вычислительное ядро алгоритма
- 1.4 Макроструктура алгоритма
- 1.5 Схема реализации последовательного алгоритма
- 1.6 Последовательная сложность алгоритма
- 1.7 Информационный граф
- 1.8 Ресурс параллелизма алгоритма
- 1.9 Входные и выходные данные алгоритма
- 1.10 Свойства алгоритма
- 2 Программная реализация алгоритма
- 3 Литература
1 Свойства и структура алгоритма
1.1 Общее описание алгоритма
Перемножение матриц - одна из базовых задач в алгоритмах линейной алгебры, широко применяется в большом количестве разных методов. Здесь мы рассмотрим умножение [math]C = AB[/math] плотных неособенных матриц (последовательный вещественный вариант), то есть тот вариант, где никак не используются ни специальный вид матрицы, ни ассоциативные свойства операции сложения[1].
1.2 Математическое описание алгоритма
Исходные данные: плотная матрица [math]A[/math] (элементы [math]a_{ij}[/math]), плотная матрица [math]B[/math] (элементы [math]b_{ij}[/math]).
Вычисляемые данные: плотная матрица [math]C[/math] (элементы [math]c_{ij}[/math]).
Формулы метода:
- [math] \begin{align} c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}, \quad i \in [1, m], \quad j \in [1, l]. \end{align} [/math]
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
1.3 Вычислительное ядро алгоритма
Вычислительное ядро перемножения плотных неособенных матриц можно составить из множественных (всего их [math]l[/math]) вычислений умножения матрицы [math]A[/math] на столбцы матрицы [math]B[/math], или (при более детальном рассмотрении), из множественных (всего их [math]ml[/math]) скалярных произведений строк матрицы [math]A[/math] на столбцы матрицы [math]B[/math]:
- [math]\sum_{k = 1}^{n} a_{ik} b_{kj}[/math]
в режиме накопления или без него, в зависимости от требований задачи.
1.4 Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть умножения матриц составляют множественные (всего [math]ml[/math]) вычисления скалярных произведений строк матрицы [math]A[/math] на столбцы матрицы [math]B[/math]
- [math]\sum_{k = 1}^{n} a_{ik} b_{kj}[/math]
в режиме накопления или без него.
1.5 Схема реализации последовательного алгоритма
Для всех [math]i[/math] от [math]1[/math] до [math]m[/math] и для всех [math]j[/math] от [math]1[/math] до [math]l[/math] выполняются
- [math]c_{ij} = \sum_{k = 1}^{n} a_{ik} b_{kj}[/math]
Особо отметим, что вычисления сумм вида [math]\sum_{k = 1}^{n} a_{ik} b_{kj}[/math] производят в режиме накопления прибавлением к текущему (временному) значению вычисляемого элемента матрицы [math]c_{ij}[/math] произведений [math]a_{ik} b_{kj}[/math] для [math]k[/math] от [math]1[/math] до [math]n[/math], c возрастанием [math]k[/math], вначале все элементы инициализируются нулями. При суммировании "по убыванию" общая схема принципиально не отличается и потому нами не рассматривается. Другие порядки выполнения суммирования приводят к изменению параллельных свойств алгоритма и будут рассматриваться нами в отдельных описаниях.
1.6 Последовательная сложность алгоритма
Для умножения двух квадратных матриц порядка [math]n[/math] (т.е. при [math]m=n=l[/math]) в последовательном (наиболее быстром) варианте требуется:
- по [math]n^3[/math] умножений и сложений.
Для умножения матрицы размером [math]m[/math] строк на [math]n[/math] столбцов на матрицу размером [math]m[/math] строк на [math]n[/math] столбцов в последовательном (наиболее быстром) варианте требуется:
- по [math]mnl[/math] умножений и сложений.
При этом использование режима накопления требует совершения умножений и сложений в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает затраты во времени, требуемом для выполнения умножения матриц.
При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам с кубической сложностью (в случае неквадратных матриц - с трилинейной).
1.7 Информационный граф
Опишем граф алгоритма как аналитически, так и в виде рисунка.
Граф алгоритма умножения плотных матриц состоит из одной группы вершин, расположенной в целочисленных узлах трёхмерной области, соответствующая ей операция [math]a+bc[/math].
Естественно введённые координаты области таковы:
- [math]i[/math] — меняется в диапазоне от [math]1[/math] до [math]m[/math], принимая все целочисленные значения;
- [math]j[/math] — меняется в диапазоне от [math]1[/math] до [math]l[/math], принимая все целочисленные значения;
- [math]k[/math] — меняется в диапазоне от [math]1[/math] до [math]n[/math], принимая все целочисленные значения.
Аргументы операции следующие:
- [math]a[/math]:
- при [math]k = 1[/math] константа [math]0[/math];
- при [math]k \gt 1[/math] — результат срабатывания операции, соответствующей вершине с координатами [math]i, j, k-1[/math];
- [math]b[/math] — элемент входных данных, а именно [math]a_{ik}[/math];
- [math]c[/math] - элемент входных данных [math]b_{kj}[/math];
Результат срабатывания операции является:
- при [math]k \lt n[/math] - промежуточным данным алгоритма;
- при [math]k = n[/math] - выходным данным [math]c_{ij}[/math].
Интерактивное изображение графа алгоритма без входных и выходных данных для случая перемножения двух квадратных матриц порядка 3 и 4
1.8 Ресурс параллелизма алгоритма
Для алгоритма умножения квадратных матриц порядка n в параллельном варианте требуется последовательно выполнить следующие ярусы:
- по [math]n[/math] ярусов умножений и сложений (в каждом из ярусов — [math]n^2[/math] операций).
Для умножения матрицы размером [math]m[/math] строк на [math]n[/math] столбцов на матрицу размером [math]n[/math] строк на [math]l[/math] столбцов в последовательном (наиболее быстром) варианте требуется:
- по [math]n[/math] ярусов умножений и сложений (в каждом из ярусов — [math]ml[/math] операций).
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
При классификации по высоте ЯПФ, таким образом, алгоритм умножения матриц относится к алгоритмам с линейной сложностью. При классификации по ширине ЯПФ его сложность также будет квадратичной (для квадратных матриц) или билинейной (для матриц общего вида).
1.9 Входные и выходные данные алгоритма
Входные данные: матрица [math]A[/math] (элементы [math]a_{ij}[/math]), матрица [math]B[/math] (элементы [math]b_{ij}[/math])).
Объём входных данных: [math]mn+nl[/math]
Выходные данные: матрица [math]C[/math] (элементы [math]c_{ij}[/math]).
Объём выходных данных: [math]ml[/math]
1.10 Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является квадратичным или билинейным (отношение кубической или трилинейной к линейной).
При этом вычислительная мощность алгоритма умножения матриц, как отношение числа операций к суммарному объему входных и выходных данных – линейно.
При этом алгоритм умножения матриц полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается.
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
В простейшем варианте алгоритм умножения матриц на Фортране можно записать так:
DO I = 1, M
DO J = 1, L
S = 0.
DO K = 1, N
S = S + DPROD(A(I,K), B(K,J))
END DO
C(I, J) = S
END DO
END DO
При этом для реализации режима накопления переменная [math]S[/math] должна быть двойной точности.
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.