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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 33: Строка 33:
  
 
== Схема реализации последовательного алгоритма ==
 
== Схема реализации последовательного алгоритма ==
Обнулим матрицу <math>C</math>&nbsp;, предназначенную для записи полученного результата произведения <math>C = AB</math>&nbsp;. Далее в цикле выполняется последовательное умножение блоков матриц операндов и суммирование результатов.
+
Обнулим матрицу <math>C</math>&nbsp;, предназначенную для записи полученного результата произведения <math>C = AB</math>&nbsp;. Рассмотрим блоки матриц: <math>A_{ij}, B_{ij},
 +
C_{ij}</math>&nbsp;. В цикле выполним последовательное умножение блоков матриц операндов и суммирование результатов.
  
 
<math>C_{ij} = \sum_{m=0}^{n-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1]  </math>&nbsp;
 
<math>C_{ij} = \sum_{m=0}^{n-1} A_{ik} B_{kj} \quad i \in [0, m-1], \quad j \in [0, m-1]  </math>&nbsp;

Версия 16:17, 24 октября 2017

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

3 Литература

  1. E. Dekel, D. Nassimi, and S. Sahni, “Parallel Matrix and Graph Algorithms,” SIAM, Journal on Computing, vol. 10, no. 4, Nov. 1981, pp. 657-675.
  2. http://parallelcomp.uw.hu/ch08lev1sec2.html