Алговики - Вклад [ru]

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

2017-11-16T22:42:00Z

Kisel dv: /* Информационный граф */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

[[File:InfographDNS.png|thumb|center|500px|]]

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

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

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

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

<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 < 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>  шагов. <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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T20:04:13Z

Kisel dv: /* Масштабируемость алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T20:03:23Z

Kisel dv: /* Масштабируемость алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <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>.

{| 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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T20:02:16Z

Kisel dv: /* Масштабируемость алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <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>\left[\frac{N}{q^{\frac{1}{3}}\right]}</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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T20:01:57Z

Kisel dv: /* Масштабируемость алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <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>.

{| 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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T19:49:45Z

Kisel dv: /* Ресурс параллелизма алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T19:49:25Z

Kisel dv: /* Информационный граф */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T19:10:21Z

Kisel dv: /* Масштабируемость алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG|thumb|center|500px|]]

[[File:DNS2.PNG|thumb|center|500px|]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[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. Ограничений на лимит времени на узел наложено не было.

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

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

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

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

= Литература =

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

2017-11-16T18:06:11Z

Kisel dv: /* Информационный граф */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG|thumb|center|500px|]]

[[File:DNS2.PNG|thumb|center|500px|]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[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|]]

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

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

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

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

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

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

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

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

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

= Литература =

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

2017-11-16T17:46:35Z

Kisel dv: /* Информационный граф */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG|thumb|center|1000px|]]

[[File:DNS2.PNG|thumb|center|1000px|]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[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|]]

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

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

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

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

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

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

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

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

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

= Литература =

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

2017-11-16T17:46:21Z

Kisel dv: /* Масштабируемость алгоритма и его реализации */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG]]

[[File:DNS2.PNG]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[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|]]

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

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

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

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

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

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

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

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

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

= Литература =

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

2017-11-16T17:28:15Z

Kisel dv:

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG]]

[[File:DNS2.PNG]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

[[File: DNS_graph2.jpg]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|2.245
|-
|1500
|0.814
|-
|1000
|0.232
|-
|750
|0.094
|-
|500
|0.027
|-
|}

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

[[File: DNS_graph1.jpg]]

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

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

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

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

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

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

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

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

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

= Литература =

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

2017-11-16T17:17:25Z

Kisel dv:

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG]]

[[File:DNS2.PNG]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|2.245
|-
|1500
|0.814
|-
|1000
|0.232
|-
|750
|0.094
|-
|500
|0.027
|-
|}

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

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6.

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

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

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

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

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

= Литература =

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

2017-11-14T22:24:17Z

Kisel dv: /* Информационный граф */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

На представленных ниже рисунках изображена иллюстрация работы алгоритма.

[[File:DNS1.PNG]]

[[File:DNS2.PNG]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|2.245
|-
|1500
|0.814
|-
|1000
|0.232
|-
|750
|0.094
|-
|500
|0.027
|-
|}

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

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6.

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

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

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

= Литература =

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

2017-11-14T22:14:15Z

Kisel dv: /* Информационный граф */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

[[File:DNS1.PNG]]

[[File:DNS2.PNG]]

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|2.245
|-
|1500
|0.814
|-
|1000
|0.232
|-
|750
|0.094
|-
|500
|0.027
|-
|}

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

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6.

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

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

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

= Литература =

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

2017-11-14T22:11:49Z

Kisel dv:

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|2.245
|-
|1500
|0.814
|-
|1000
|0.232
|-
|750
|0.094
|-
|500
|0.027
|-
|}

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

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6.

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

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

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

= Литература =

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

2017-11-14T21:30:46Z

Kisel dv: /* Масштабируемость алгоритма */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.976
|-
|64
|2.245
|-
|32
|6.012
|-
|16
|18.012
|-
|8
|18.153
|-
|4
|162.214
|-
|2
|495.675
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|2.245
|-
|1500
|0.814
|-
|1000
|0.232
|-
|750
|0.094
|-
|500
|0.027
|-
|}

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

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6.

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

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

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

= Литература =

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

2017-11-14T20:22:01Z

Kisel dv: /* Масштабируемость алгоритма и его реализации */

Автор: [[Участник:Kisel dv|Д.В.Кисель]]

= Свойства и структура алгоритма =
== Общее описание алгоритма ==
Алгоритм 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>  ортогональны друг другу<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>  и <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>  - количество блоков матрицы.

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

Вычислительное ядро перемножения матриц методом 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> 

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

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

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

<math>\sum_{k=1}^{n} a_{ik} b_{kj}</math> 

== Схема реализации последовательного алгоритма ==
Обнулим матрицу <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> .

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

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

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

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

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

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

<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 < 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>  шагов. <ref>http://parallelcomp.uw.hu/ch08lev1sec2.html</ref>

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

'''Входные данные''': матрица <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 = 1000</math>)

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.234
|-
|64
|0.24
|-
|32
|0.248
|-
|16
|0.254
|-
|8
|0.272
|-
|4
|0.29
|-
|2
|0.323
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|0.248
|-
|1500
|0.254
|-
|1000
|0.272
|-
|750
|0.29
|-
|500
|0.323
|-
|}

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

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6.

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

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

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

= Литература =

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

2017-11-14T20:09:20Z

Kisel dv: /* Свойства и структура алгоритма */

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

2017-11-14T20:08:35Z

Kisel dv: /* Программная реализация алгоритма */

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

2017-11-04T13:48:45Z

Kisel dv: /* Входные и выходные данные алгоритма */

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

2017-11-01T12:26:59Z

Kisel dv: /* Общее описание алгоритма */

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

2017-10-31T04:46:51Z

Kisel dv: /* Математическое описание алгоритма */

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

2017-10-24T17:32:35Z

Kisel dv: /* Последовательная сложность алгоритма */

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

2017-10-24T15:56:28Z

Kisel dv:

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

2017-10-24T14:19:29Z

Kisel dv:

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

2017-10-24T14:05:24Z

Kisel dv:

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

2017-10-24T13:17:01Z

Kisel dv:

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

2017-10-24T13:15:16Z

Kisel dv:

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

2017-10-24T13:01:55Z

Kisel dv:

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

2017-10-24T12:53:07Z

Kisel dv:

Участник:Kisel dv

2017-10-23T19:26:52Z

Kisel dv:

Кисель Дмитрий Владимирович, студент 4 курса ВМК МГУ, кафедры системного анализа.

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

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

2017-10-23T19:25:35Z

Kisel dv: Новая страница: «Автор: Д.В.Кисель = Свойства и структура алгоритма = == Общее описание алг…»

Участник:Kisel dv

2017-10-23T15:13:14Z

Kisel dv: Новая страница: «Кисель Дмитрий Владимирович, студент 4 курса ВМК МГУ, кафедры системного анализа.»

Кисель Дмитрий Владимирович, студент 4 курса ВМК МГУ, кафедры системного анализа.