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

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-26T15:58:01Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i (i = 0, …, q)</math> блок <math>A_{ij}</math> одного из процессов пересылается во все процессы этой же строки.
* Полученный в результате подобной пересылки блок матрицы <math>A</math> и содержащийся в процессе <math>(i, j)</math>
блок матрицы <math>B</math> перемножаются, и результат прибавляется к матрице <math>С_{ij}</math>.
* Для каждого столбца <math>j (j = 0, …, q)</math> выполняется циклическая пересылка блоков матрицы <math>B</math>, содер-
жащихся в каждом процессе <math>(i, j)</math> этого столбца, в направлении убывания номеров строк.

Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.
[[File: fox.jpg|thumb|center|400px|]]

Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные(на картинках в начале статьи более подробно нарисовано, какие блоки передаются).Желтым цветом обозначен уже вывод результата соответствующего блока.

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-26T15:51:44Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.
[[File: fox.jpg|thumb|center|400px|]]

Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные(на картинках в начале статьи более подробно нарисовано, какие блоки передаются).Желтым цветом обозначен уже вывод результата соответствующего блока.

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T20:08:36Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.
[[File: Foxgraph.png|thumb|center|400px|]]

Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные(на картинках в начале статьи более подробно нарисовано, какие блоки передаются).Желтым цветом обозначен уже вывод результата соответствующего блока.

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T20:05:16Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

Число блоков определяется как округление снизу корня квадратного из числа доступных процессов.
[[File: Foxgraph.png|thumb|center|400px|]]

Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные.Желтым цветом обозначен уже вывод результата соответствующего блока.

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T20:04:18Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File: Foxgraph.png|thumb|center|400px|]]

Синим цветом на информационном графе отмечен этап инициализации результирующей матрицы, то есть заполнение всех блоков нулями. Красным цветом обозначен этап, на котором происходит умножение подматриц, хранящихся в этом процессе, а также обмен подматрицами с другими процессами и прибавление произведения переданных подматриц на сохраненные.Желтым цветом обозначен уже вывод результата соответствующего блока.

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T19:48:30Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File: Foxgraph.png|thumb|center|400px|]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T19:48:16Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File: Foxgraph.png|thumb|center|600px|]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T19:46:57Z

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

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

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

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

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T19:46:29Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T19:28:27Z

Diana Pimenova: /* Характеристики программно-аппаратной среды */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

Для компиляции был использован компилятор языка C++ GNU 4.4.6. Использованная реализация MPI: Intel MPI 4.0.3. Опции компилятора: -lm.

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T19:22:26Z

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

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

[[File: Fox1.jpg|thumb|center|600px|]]

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

[[File: Fox2.jpg|thumb|center|600px|]]

[[File: Fox3.jpg|thumb|center|600px|]]

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-16T06:17:41Z

Diana Pimenova:

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Динамические характеристики и эффективность реализации алгоритма ==
== Выводы для классов архитектур ==
== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-15T18:19:17Z

Diana Pimenova: /* Существующие реализации алгоритма */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

[http://www.opennet.ru/docs/RUS/linux_parallel/node164.html] - OpenNET

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-15T18:17:52Z

Diana Pimenova: /* Существующие реализации алгоритма */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Существующие реализации алгоритма ==
Ссылки на некоторые существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-15T18:17:41Z

Diana Pimenova: /* Существующие реализации алгоритма */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Существующие реализации алгоритма ==
Ссылки на существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-15T18:17:24Z

Diana Pimenova: /* Существующие реализации алгоритма */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Существующие реализации алгоритма ==
Ссылки на существующие реализации этого алгоритма:

[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.

[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-15T18:17:07Z

Diana Pimenova: /* Существующие реализации алгоритма */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

== Существующие реализации алгоритма ==
Ссылки на существующие реализации этого алгоритма:
[http://www.hpcc.unn.ru/?dir=889] - центр суперкомпьютерных технологий Нижегородского Государственного Университета.
[http://www.intuit.ru/studies/courses/1156/190/lecture/4954?page=4] - ИНТУИТ

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-14T22:07:10Z

Diana Pimenova: /* Информационный граф */

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

[[File:Fox1.png]]

[[File:Fox2.png]]

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

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

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-14T21:58:39Z

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

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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 \times n</math>, где <math>500\leqslant n \leqslant 2000</math>, а число процессов будем изменять от <math>2</math> до <math>128</math>. В качестве примера приведем время выполнения программы в зависимости от числа процессов при фиксированном размере матриц <math>n = 2000</math>.

{| class="wikitable"
|-
! Число процессов
! Время (с)
|-
|128
|0.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

Из приведенных результатов исследования видно, что система хорошо масштабируема.

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

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

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

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

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

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-14T21:53:33Z

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

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

'''Входные данные''': матрица <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.510
|-
|64
|1.038
|-
|32
|2.556
|-
|16
|5.121
|-
|8
|20.844
|-
|4
|20.952
|-
|2
|92.919
|-
|}

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

{| class="wikitable"
|-
! Размер матриц
! Время (с)
|-
|2000
|1.038
|-
|1500
|0.409
|-
|1000
|0.115
|-
|750
|0.049
|-
|500
|0.015
|-
|}

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

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

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

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

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

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

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-04T10:07:51Z

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

Автор: [[Участник:Diana Pimenova|Д.В.Пименова]]

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

== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

Рассмотрим квадратные матрицы размером <math>n \times n</math> , разбитые на блоки размера <math>\frac{n}{q}</math> . Итого у нас получается <math>q \times q</math>  блоков.

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

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

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

Сначала опишем идею параллельного умножения матриц методом Фокса:

* Каждой подзадаче <math>(i,j)</math> передаются блоки <math>A_{ij}</math>, <math>B_{ij}</math> и обнуляются блоки <math>C_{ij}</math> на всех подзадачах.
* Для каждой строки <math>i</math> блок <math>A_{ij}</math> подзадачи <math>(i,j)</math> пересылается на все подзадачи той же строки <math>i</math> решетки.
* Полученные в результаты пересылок блоки <math>A'_{ij}</math>, <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> перемножаются и прибавляются к блоку <math>C_{ij}</math><math>: C_{ij} = C_{ij} + A'_{ij}B'_{ij} </math>.
* блоки <math>B'_{ij}</math> каждой подзадачи <math>(i,j)</math> пересылаются подзадачам, являющимися соседями сверху в столбцах решетки подзадач (блоки подзадач из первой строки решетки пересылаются подзадачам последней строки решетки).

== Ресурс параллелизма алгоритма ==
Определим вычислительную сложность данного алгоритма. Пусть все матрицы являются квадратными размера <math>n \times n</math> , количество блоков по горизонтали и вертикали являются одинаковым и равным <math> q </math>  (т.е. размер всех блоков равен <math>k \times k</math> , где <math>k = \frac{n}{q}</math> ), процессоры образуют квадратную решетку и их количество равно <math>p = q^{2}</math> .

Алгоритм Фокса требует для своего выполнения <math>q</math>  итераций, в ходе которых каждый процессор перемножает свои текущие блоки матриц <math>A</math>  и <math>B</math>  и прибавляет результаты умножения к текущему значению блока матрицы <math>C</math> . С учетом выдвинутых предположений общее количество выполняемых при этом операций будет иметь порядок <math>\frac{n^{3}}{p}</math> .

Определим количество вычислительных операций. Сложность выполнения скалярного умножения строки блока матрицы <math>A</math> на столбец блока матрицы <math>B</math> можно оценить как<math>2\frac{n}{q} - 1</math> . Количество строк и столбцов в блоках равно <math>\frac{n}{q}</math> и, как результат, трудоемкость операции блочного умножения оказывается равной <math>\frac{\frac{n^2}{p}}{\frac{2n}{q} - 1}</math>. Для сложения блоков требуется<math>\frac{n^{2}}{p}</math> операций.

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

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

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

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

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

= Литература =
<references />

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-04T10:07:00Z

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

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-04T09:26:59Z

Diana Pimenova: /* Информационный граф */

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-04T08:53:27Z

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

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-11-04T08:40:56Z

Diana Pimenova:

Алгоритм Фокса умножения матриц

2017-10-23T19:29:18Z

Diana Pimenova: Полностью удалено содержимое страницы

Участник:Diana Pimenova

2017-10-23T19:29:04Z

Diana Pimenova:

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

[[Участник:Diana Pimenova/Алгоритм Фокса умножения матриц]]

Участник:Diana Pimenova/Алгоритм Фокса умножения матриц

2017-10-23T19:28:52Z

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

Участник:Diana Pimenova

2017-10-23T15:12:48Z

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

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

Алгоритм Фокса умножения матриц

2017-10-23T15:11:13Z

Diana Pimenova:

Алгоритм Фокса умножения матриц

2017-10-09T17:44:12Z

Diana Pimenova: /* Вычислительное ядро алгоритма */

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>
<ref>http://it.kgsu.ru/ParalAlg/palg046.html</ref>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

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

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

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

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

= Литература =
<references />

Алгоритм Фокса умножения матриц

2017-10-09T17:43:06Z

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

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.<ref>Лекции по высокопроизводительным вычислительным системам СПбГПУ, 2016.</ref>

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

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

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

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

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

= Литература =
<references />

Алгоритм Фокса умножения матриц

2017-10-09T17:39:16Z

Diana Pimenova: /* Литература */

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

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

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

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

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

= Литература =
<references />

Алгоритм Фокса умножения матриц

2017-10-09T17:39:02Z

Diana Pimenova: /* Схема реализации последовательного алгоритма */

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.<ref>Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016.</ref>

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

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

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

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

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

= Литература =
<references />
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007

Алгоритм Фокса умножения матриц

2017-10-09T17:32:54Z

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

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти, что дает нам уменьшение времени работы программы.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.

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

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

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

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

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

= Литература =
<references />
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007

Алгоритм Фокса умножения матриц

2017-10-09T17:31:08Z

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

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход хранения позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.

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

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

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

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

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

= Литература =
<references />
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007

Алгоритм Фокса умножения матриц

2017-10-09T17:16:32Z

Diana Pimenova: /* Схема реализации последовательного алгоритма */

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
С_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.

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

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

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

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

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

= Литература =
<references />
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007

Алгоритм Фокса умножения матриц

2017-10-09T17:13:42Z

Diana Pimenova: /* Схема реализации последовательного алгоритма */

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

== Схема реализации последовательного алгоритма ==
Разобьем исходные матрицы на блоки <math>A_{ij}</math>,<math>B_{ij}</math> и <math>C_{ij}</math> соответственно.
Обнулим блоки матрицы <math>C</math>, предназначенной для хранения соответствующего результирующего произведения <math>AB</math>.
Затем запускается цикл, в ходе которого выполняется последовательное умножение блоков матриц операндов и суммирование полученных результатов.

:<math>
\begin{align}
S_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

После завершения цикла мы получим матрицу с блоками <math>C_{ij}</math>, соответствующую произведению <math>AB</math>.

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

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

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

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

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

= Литература =
<references />
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007

Алгоритм Фокса умножения матриц

2017-10-09T12:46:42Z

Diana Pimenova: Новая страница: « = Свойства и структура алгоритмов = == Общее описание алгоритма == Метод Фокса - это блочны…»

= Свойства и структура алгоритмов =
== Общее описание алгоритма ==
Метод Фокса - это блочный алгоритм умножения квадратных матриц. Основная его идея заключается в том, что матрицы разбиваются на части, представляющие собой подматрицы исходных матриц (разделяются как матрицы-операнды, так и результирующая). При таком разбиении данных для определения базовых подзадач за основу берутся вычисления, выполняемые над блоками. А базовой подзадачей является процедура вычисления всех элементов одного из блоков результирующей матрицы. В отличие от стандартного ленточного алгоритма, когда мы рассматриваем матрицы в виде набора строк и столбцов, такой подход позволяет добиться большей локализации данных и повысить эффективность использования кэш-памяти.

== Математическое описание алгоритма ==
Исходные данные: квадратная матрица <math>A</math> (состоит из блоков <math>A_{ij}</math>), квадратная матрица <math>B</math> (состоит из блоков <math>B_{ij}</math>).

Вычисляемые данные: квадратная матрица <math>C</math> (состоит из блоков <math>C_{ij}</math>).

При этом каждый блок <math>C_{ij}</math> определяется как произведение соответствующих блоков матриц <math>A</math> и <math>B</math> :
:<math>
\begin{align}
C_{ij} = \sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

== Вычислительное ядро алгоритма ==
Вычислительное ядро перемножения квадратных матриц методом Фокса можно составить из процедур вычисления всех элементов одного из блоков результирующей матрицы, т.е. из процедур множественных вычислений умножения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>
:<math>
\begin{align}
\sum_{s = 0}^{q-1} A_{is} B_{sj}, \quad i \in [0, q-1],\quad j \in [0, q-1].
\end{align}
</math>

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

Как уже записано в [[#Вычислительное ядро алгоритма|описании ядра алгоритма]], основную часть умножения матриц составляют множественные вычисления произведения блоков матрицы <math>A</math> на блоки матрицы <math>B</math>. Перемножать блоки будем стандартным методом, используя определение произведения матриц:
:<math>
\begin{align}
\sum_{k = 1}^{n} a_{ik} b_{kj}
\end{align}
</math>

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

Вначале производится рассылка в процесс с координатами (i, j) блоков Aij, Bij исходных матриц.
Кроме того, выполняется обнуление матрицы Cij, предназначенной для хранения соответствующего блока
результирующего произведения AB.
Затем запускается цикл по m (m = 0, …, q), в ходе которого выполняются три действия:
* для каждой строки i (i = 0, …, q) блок Aij одного из процессов пересылается во все процессы этой
же строки; при этом индекс j пересылаемого блока определяется по формуле j = (i + m) mod q;
* полученный в результате подобной пересылки блок матрицы A и содержащийся в процессе (i, j)
блок матрицы B перемножаются, и результат прибавляется к матрице Сij;
* для каждого столбца j (j = 0, …, q) выполняется циклическая пересылка блоков матрицы B, содержащихся в каждом процессе (i, j) этого столбца, в направлении убывания номеров строк.

После завершения цикла в каждом процессе будет содержаться матрица Cij, равная соответствующему блоку произведения AB. Останется переслать эти блоки главному процессу.

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

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

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

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

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

= Литература =
<references />
1. Абрамян М.Э. Лекции по основам параллельного программирования, ЮФУ, 2016

2. Гергель В. П. Теория и практика параллельных вычислений: учебное пособие, ИНТУИТ, 2007