Участник:Kisel dv/DNS алгоритм умножения матриц: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
 
(не показано 28 промежуточных версий этого же участника)
Строка 4: Строка 4:
 
== Общее описание алгоритма ==
 
== Общее описание алгоритма ==
 
Алгоритм DNS(Dekel, Nassimi, Sahni - назван по фамилиям создателей) является одним из блочных алгоритмов решения задачи <math>C = AB</math>&nbsp; перемножения двух матриц. Для данного алгоритма мы не используем какие-либо свойства матриц <math>A</math>&nbsp; и <math>B</math>&nbsp;.
 
Алгоритм DNS(Dekel, Nassimi, Sahni - назван по фамилиям создателей) является одним из блочных алгоритмов решения задачи <math>C = AB</math>&nbsp; перемножения двух матриц. Для данного алгоритма мы не используем какие-либо свойства матриц <math>A</math>&nbsp; и <math>B</math>&nbsp;.
−
DNS основан на разделении промежуточных данных, его преимуществом является временная сложность <math>O(log(n))</math>&nbsp; при вычислительной сложности <math>O(\frac{n^3}{log(n)})</math>&nbsp;. Достигается это за счет 3d-секционирования(англ. partitioning), в отличие от альтернатив, использующих 2d-секционирование(например, алгоритм Кэннона). Тем самым, алгоритм DNS представим в виде куба, где матрицы <math>A</math>&nbsp;, <math>B</math>&nbsp; и матрица <math>C</math>&nbsp; ортогональны друг другу<ref>E. Dekel, D. Nassimi, and S. Sahni, “Parallel Matrix and Graph Algorithms,” SIAM, Journal on Computing, vol. 10, no. 4, Nov. 1981, pp. 657-675.</ref>. Далее данное описание будет рассмотрено подробнее.
+
DNS основан на блочном разделении данных, его преимуществом является временная сложность <math>O(log(n))</math>&nbsp; при вычислительной сложности <math>O(\frac{n^3}{log(n)})</math>&nbsp;. Достигается это за счет 3d-секционирования(англ. partitioning), в отличие от альтернатив, использующих 2d-секционирование(например, алгоритм Кэннона). Тем самым, алгоритм DNS представим в виде куба, где матрицы <math>A</math>&nbsp;, <math>B</math>&nbsp; и матрица <math>C</math>&nbsp; ортогональны друг другу<ref>E. Dekel, D. Nassimi, and S. Sahni, “Parallel Matrix and Graph Algorithms,” SIAM, Journal on Computing, vol. 10, no. 4, Nov. 1981, pp. 657-675.</ref>. [[#Ресурс параллелизма алгоритма|Далее]] данное описание будет рассмотрено подробнее.
  
 
== Математическое описание алгоритма ==
 
== Математическое описание алгоритма ==
  
−
Исходные данные: матрицы <math>A</math>&nbsp; и <math>B</math>&nbsp; с элементами <math>a_{ij}</math>&nbsp; и <math>b_{ij}</math>&nbsp;, соответственно.
+
Исходные данные: матрицы <math>A</math>&nbsp; и <math>B</math>&nbsp; с блоками <math>A_{ij}</math>&nbsp; и <math>B_{ij}</math>&nbsp;, соответственно.
  
 
Вычисляемые данные: матрица <math>C</math>&nbsp; с блоками <math>C_{ij}</math>&nbsp;
 
Вычисляемые данные: матрица <math>C</math>&nbsp; с блоками <math>C_{ij}</math>&nbsp;
Строка 14: Строка 14:
 
Используемые формулы:
 
Используемые формулы:
  
−
<math>\sum_{k=0}^{n-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1]  </math>&nbsp;, где  <math> m \times m </math>*nbsp; - количество блоков матриц.
+
<math>C_{ij} = \sum_{k=0}^{m-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1]  </math>&nbsp;,
 +
где  <math> m \times m </math>&nbsp; - количество блоков матрицы.
  
 
== Вычислительное ядро алгоритма ==
 
== Вычислительное ядро алгоритма ==
  
−
Вычислительное ядро перемножения матриц методом DNS можно составить из множественных скалярных произведений строк матрицы <math> A </math>&nbsp; на столбцы матрицы <math> B </math>&nbsp;
+
Вычислительное ядро перемножения матриц методом DNS состоит из вычислений всех элементов блоков матрицы-результата: процедур вычислений умножения блоков матрицы <math> A </math>&nbsp; на блоки матрицы <math> B </math>&nbsp;
  
−
<math>\sum_{k=1}^{n} a_{ik} b_{kj} \quad i \in [1, n], \quad i \in [1, n]  </math>&nbsp;
+
<math>\sum_{k=0}^{m-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad i \in [0, m-1]  </math>&nbsp;
  
  
Строка 27: Строка 28:
 
В алгоритме используется:
 
В алгоритме используется:
  
−
<math> \cdot </math>&nbsp; скалярное произведение векторов(строк матрицы <math> A </math>&nbsp; на столбцы матрицы <math> B </math>&nbsp;) <math>\sum_{k=0}^{n-1} a_{ik} b_{kj}</math>&nbsp;
+
<math> \cdot </math>&nbsp; произведение блоков матриц <math> A </math>&nbsp; и <math> B </math>&nbsp;
 +
 
 +
<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math>&nbsp;
  
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
−
Обнулим матрицу <math>C</math>&nbsp;, предназначенную для записи полученного результата произведения <math>C = AB</math>&nbsp;. Далее в цикле выполняется последовательное умножение элементов матриц операндов и суммирование результатов.
+
Обнулим матрицу <math>C</math>&nbsp;, предназначенную для записи полученного результата произведения <math>C = AB</math>&nbsp;. Рассмотрим блоки матриц: <math>A_{ij}, B_{ij},
 +
C_{ij}</math>&nbsp;. В цикле выполним последовательное умножение блоков матриц операндов и суммирование результатов.
  
−
<math>c_{ij} = \sum_{k=0}^{n-1} a_{ik} b_{kj} \quad i \in [0, n-1], \quad j \in [0, n-1]  </math>&nbsp;
+
<math>C_{ij} = \sum_{k=0}^{m-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1]  </math>&nbsp;
  
 
В результате получаем матрицу <math>C</math>&nbsp;, равную произведению матриц <math>A</math>&nbsp; и <math>B</math>&nbsp;.
 
В результате получаем матрицу <math>C</math>&nbsp;, равную произведению матриц <math>A</math>&nbsp; и <math>B</math>&nbsp;.
Строка 38: Строка 42:
 
== Последовательная сложность алгоритма ==
 
== Последовательная сложность алгоритма ==
  
 +
Рассматриваем матрицы размером <math>n \times n</math>&nbsp;, разбитые на <math>m \times m</math>&nbsp; блоков размера <math>\frac{n}{m}</math>&nbsp;.
 +
 +
Для умножение данных матриц в последовательном варианте требуется по <math> n^3 </math>&nbsp; умножений и сложений.
 +
 +
При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам ''с кубической сложностью''.
  
 
== Информационный граф ==
 
== Информационный граф ==
  
 +
 +
[[File:InfographDNS.png|thumb|center|500px|]]
 +
 +
Серым на графе помечен этап, в котором происходит считывание матриц <math>A</math> и <math>B</math> и их запись в "смежные грани куба".
 +
 +
Далее как бы проецируем каждый блок матрицы на каждую плоскость куба из процессов(на каждую плоскость, параллельную рассматриваемой матрице, см.рисунок выше), таким образом в каждом из них будет выполняться свое умножение уникальной комбинации блоков("синий" этап).
 +
 +
Зеленым обозначен этап суммирования и вывода результата - матрицы <math>C</math>.
  
 
== Ресурс параллелизма алгоритма ==
 
== Ресурс параллелизма алгоритма ==
  
−
<math> \cdot </math>&nbsp; Рассмотрим <math>n^3</math>&nbsp; процессов, доступных для умножения двух матриц размером <math>n \times n</math>&nbsp;. Представим их в виде трехмерного массива  
+
<math> \cdot </math>&nbsp; Рассмотрим <math>m^3</math>&nbsp; процессов, доступных для умножения двух матриц размером <math>n \times n</math>&nbsp;, разбитых на <math>m \times m</math>&nbsp; блоков. Представим их в виде трехмерного массива  
−
<math> n \times n \times n</math>&nbsp;.
+
<math> m \times m \times m</math>&nbsp;.
 +
 
 +
<math> \cdot </math>&nbsp; Процессы именованы согласно их расположению в массиве, соответственно, вычисление произведения <math> A_{ik}B_{kj} </math>&nbsp; присвоено процессу с координатами <math> [i, j, k] (0 \leq i,j,k < m) </math>&nbsp;.
 +
 
 +
<math> \cdot </math>&nbsp; После того, как каждый процесс завершил умножение, результаты процессов <math> [i, j, 0], [i, j, 1], ..., [i, j, m-1] </math>&nbsp; суммируются в <math> C_{ij} </math>&nbsp;. Суммирование всех <math> C_{ij} </math>&nbsp; может выполняться одновременно за <math> log(m) </math>&nbsp; шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>
  
−
<math> \cdot </math>&nbsp; Процессы именованы согласно их расположению в массиве, соответственно, вычисление произведения <math> a_{ik}b_{kj} </math>&nbsp; присвоено процессу с координатами <math> [i, j, k] (0 \leq i,j,k < n) </math>&nbsp;.
 
  
−
<math> \cdot </math>&nbsp; После того, как каждый процесс завершил умножение, результаты процессов <math> [i, j, 0], [i, j, 1], ..., [i, j, n-1] </math>&nbsp; суммируются в <math> c_{ij} </math>&nbsp;. Суммирование всех <math> c_{ij} </math>&nbsp; может выполняться одновременно за <math> log(n) </math>&nbsp; шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>
+
[[File:DNS1.PNG|thumb|center|500px|]]
  
 +
[[File:DNS2.PNG|thumb|center|500px|]]
  
 
== Входные и выходные данные алгоритма ==
 
== Входные и выходные данные алгоритма ==
  
 +
'''Входные данные''': матрица <math>A</math> (элементы <math>a_{ij}</math>), матрица <math>B</math> (элементы <math>b_{ij}</math>)).
 +
 +
'''Объём входных данных''': <math>2n^2</math>
 +
 +
'''Выходные данные''': матрица <math>C</math> (элементы <math>c_{ij}</math>).
 +
 +
'''Объём выходных данных''': <math>n^2</math>
  
 
== Свойства алгоритма ==
 
== Свойства алгоритма ==
−
 
  
 
= Программная реализация алгоритма =
 
= Программная реализация алгоритма =
  
 
== Особенности реализации последовательного алгоритма ==
 
== Особенности реализации последовательного алгоритма ==
 +
 +
== Локальность данных и вычислений ==
 +
 +
== Возможные способы и особенности параллельной реализации алгоритма ==
 +
 +
== Масштабируемость алгоритма и его реализации ==
 +
 +
=== Масштабируемость алгоритма ===
 +
 +
Рассматривались квадратные матрицы размерностью  <math>N</math>, где  <math>500\leqslant N \leqslant 2000</math>, а число процессов изменялось от  <math>2</math> до <math>128</math>. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера <math>N = 2000</math>)
 +
 +
Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: целая часть от <math>\frac{N}{q^{\frac{1}{3}}}</math>, где <math>N, q</math>, соответственно, размер матрицы и количество процессов.
 +
 +
{| class="wikitable"
 +
|-
 +
! Число процессов
 +
! Время (с)
 +
|-
 +
|128
 +
|0.976
 +
|-
 +
|64
 +
|2.245
 +
|-
 +
|32
 +
|6.012
 +
|-
 +
|16
 +
|18.012
 +
|-
 +
|8
 +
|18.153
 +
|-
 +
|4
 +
|162.214
 +
|-
 +
|}
 +
 +
Приблизительно одинаковые результаты по времени на количестве процессов, равном 8 и 16, обусловлены равным числом по факту используемых процессов в программе, поскольку деление в данных двух случаях будет происходить на равные блоки(выше указана оптимальная формула для количества блоков).
 +
 +
Проиллюстрируем данные графиком:
 +
 +
[[File: DNS_graph2.jpg|thumb|center|500px|]]
 +
 +
 +
А теперь посмотрим на зависимость времени выполнения программы от размера матриц. Число процессов зафиксируем равным <math>64</math>.
  
  
−
== Локальность данных и вычислений ==
+
{| class="wikitable"
 +
|-
 +
! Размер матриц
 +
! Время (с)
 +
|-
 +
|2000
 +
|2.245
 +
|-
 +
|1500
 +
|0.814
 +
|-
 +
|1000
 +
|0.232
 +
|-
 +
|750
 +
|0.094
 +
|-
 +
|500
 +
|0.027
 +
|-
 +
|}
 +
 
 +
Проиллюстрируем данные графиком:
 +
 
 +
[[File: DNS_graph1.jpg|thumb|center|500px|]]
 +
 
 +
3d-график:
 +
 
 +
[[File: DNS_graph3.jpg|thumb|center|500px|]]
  
 +
Очевидно, что система хорошо масштабируема.
  
−
== Возможные способы и особенности параллельной реализации алгоритма ==
+
=== Характеристики программно-аппаратной среды ===
  
 +
Все вычисления были произведены на суперкомпьютере "Ломоносов".
  
−
== Масштабируемость алгоритма и его реализации ==
+
Для компиляции был использован компилятор языка C++ GNU 4.4.6, реализация MPI: Intel MPI 4.0.3.
 +
При компиляции использована опция -lm (подключение библиотеки math).
  
 +
Вычисления производились в очереди test. Ограничений на лимит времени на узел наложено не было.
  
 
== Динамические характеристики и эффективность реализации алгоритма ==
 
== Динамические характеристики и эффективность реализации алгоритма ==
−
 
  
 
== Выводы для классов архитектур ==
 
== Выводы для классов архитектур ==
Строка 79: Строка 183:
 
== Существующие реализации алгоритма ==
 
== Существующие реализации алгоритма ==
  
 +
DNS алгоритм не очень распространен в Интернете, сравнительно просто отыскать лишь текстовое описание данного способа умножения матриц. Чуть более трудной, однако выполнимой задачей будет нахождение его реализации, например, на [https://github.com/ github].
  
 
= Литература =
 
= Литература =

Текущая версия на 01:42, 17 ноября 2017

Автор: Д.В.Кисель

Содержание

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

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

Алгоритм DNS(Dekel, Nassimi, Sahni - назван по фамилиям создателей) является одним из блочных алгоритмов решения задачи [math]C = AB[/math]  перемножения двух матриц. Для данного алгоритма мы не используем какие-либо свойства матриц [math]A[/math]  и [math]B[/math] . DNS основан на блочном разделении данных, его преимуществом является временная сложность [math]O(log(n))[/math]  при вычислительной сложности [math]O(\frac{n^3}{log(n)})[/math] . Достигается это за счет 3d-секционирования(англ. partitioning), в отличие от альтернатив, использующих 2d-секционирование(например, алгоритм Кэннона). Тем самым, алгоритм DNS представим в виде куба, где матрицы [math]A[/math] , [math]B[/math]  и матрица [math]C[/math]  ортогональны друг другу[1]. Далее данное описание будет рассмотрено подробнее.

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

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

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

Используемые формулы:

[math]C_{ij} = \sum_{k=0}^{m-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1] [/math] , где [math] m \times m [/math]  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом DNS состоит из вычислений всех элементов блоков матрицы-результата: процедур вычислений умножения блоков матрицы [math] A [/math]  на блоки матрицы [math] B [/math] 

[math]\sum_{k=0}^{m-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad i \in [0, m-1] [/math] 


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

В алгоритме используется:

[math] \cdot [/math]  произведение блоков матриц [math] A [/math]  и [math] B [/math] 

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

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

Обнулим матрицу [math]C[/math] , предназначенную для записи полученного результата произведения [math]C = AB[/math] . Рассмотрим блоки матриц: [math]A_{ij}, B_{ij}, C_{ij}[/math] . В цикле выполним последовательное умножение блоков матриц операндов и суммирование результатов.

[math]C_{ij} = \sum_{k=0}^{m-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1] [/math] 

В результате получаем матрицу [math]C[/math] , равную произведению матриц [math]A[/math]  и [math]B[/math] .

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

Рассматриваем матрицы размером [math]n \times n[/math] , разбитые на [math]m \times m[/math]  блоков размера [math]\frac{n}{m}[/math] .

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

При классификации по последовательной сложности, таким образом, алгоритм умножения матриц относится к алгоритмам с кубической сложностью.

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

InfographDNS.png

Серым на графе помечен этап, в котором происходит считывание матриц [math]A[/math] и [math]B[/math] и их запись в "смежные грани куба".

Далее как бы проецируем каждый блок матрицы на каждую плоскость куба из процессов(на каждую плоскость, параллельную рассматриваемой матрице, см.рисунок выше), таким образом в каждом из них будет выполняться свое умножение уникальной комбинации блоков("синий" этап).

Зеленым обозначен этап суммирования и вывода результата - матрицы [math]C[/math].

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

[math] \cdot [/math]  Рассмотрим [math]m^3[/math]  процессов, доступных для умножения двух матриц размером [math]n \times n[/math] , разбитых на [math]m \times m[/math]  блоков. Представим их в виде трехмерного массива [math] m \times m \times m[/math] .

[math] \cdot [/math]  Процессы именованы согласно их расположению в массиве, соответственно, вычисление произведения [math] A_{ik}B_{kj} [/math]  присвоено процессу с координатами [math] [i, j, k] (0 \leq i,j,k \lt m) [/math] .

[math] \cdot [/math]  После того, как каждый процесс завершил умножение, результаты процессов [math] [i, j, 0], [i, j, 1], ..., [i, j, m-1] [/math]  суммируются в [math] C_{ij} [/math] . Суммирование всех [math] C_{ij} [/math]  может выполняться одновременно за [math] log(m) [/math]  шагов. [2]


DNS1.PNG
DNS2.PNG

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

Входные данные: матрица [math]A[/math] (элементы [math]a_{ij}[/math]), матрица [math]B[/math] (элементы [math]b_{ij}[/math])).

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

Выходные данные: матрица [math]C[/math] (элементы [math]c_{ij}[/math]).

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

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

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

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

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

2.4.1 Масштабируемость алгоритма

Рассматривались квадратные матрицы размерностью [math]N[/math], где [math]500\leqslant N \leqslant 2000[/math], а число процессов изменялось от [math]2[/math] до [math]128[/math]. Для примера посмотрим как изменялось время выполнения программы в зависимости от числа процессов (здесь берутся матрицы размера [math]N = 2000[/math])

Размер блоков, на которые разбивается матрица, выбирается по оптимальному принципу: целая часть от [math]\frac{N}{q^{\frac{1}{3}}}[/math], где [math]N, q[/math], соответственно, размер матрицы и количество процессов.

Число процессов Время (с)
128 0.976
64 2.245
32 6.012
16 18.012
8 18.153
4 162.214

Приблизительно одинаковые результаты по времени на количестве процессов, равном 8 и 16, обусловлены равным числом по факту используемых процессов в программе, поскольку деление в данных двух случаях будет происходить на равные блоки(выше указана оптимальная формула для количества блоков).

Проиллюстрируем данные графиком:

DNS graph2.jpg


А теперь посмотрим на зависимость времени выполнения программы от размера матриц. Число процессов зафиксируем равным [math]64[/math].


Размер матриц Время (с)
2000 2.245
1500 0.814
1000 0.232
750 0.094
500 0.027

Проиллюстрируем данные графиком:

DNS graph1.jpg

3d-график:

DNS graph3.jpg

Очевидно, что система хорошо масштабируема.

2.4.2 Характеристики программно-аппаратной среды

Все вычисления были произведены на суперкомпьютере "Ломоносов".

Для компиляции был использован компилятор языка C++ GNU 4.4.6, реализация MPI: Intel MPI 4.0.3. При компиляции использована опция -lm (подключение библиотеки math).

Вычисления производились в очереди test. Ограничений на лимит времени на узел наложено не было.

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

DNS алгоритм не очень распространен в Интернете, сравнительно просто отыскать лишь текстовое описание данного способа умножения матриц. Чуть более трудной, однако выполнимой задачей будет нахождение его реализации, например, на github.

3 Литература

  1. ↑ E. Dekel, D. Nassimi, and S. Sahni, “Parallel Matrix and Graph Algorithms,” SIAM, Journal on Computing, vol. 10, no. 4, Nov. 1981, pp. 657-675.
  2. ↑ http://parallelcomp.uw.hu/ch08lev1sec2.html
Источник — https://algowiki-project.org/w/ru/index.php?title=Участник:Kisel_dv/DNS_алгоритм_умножения_матриц&oldid=24002