Участник:Y.ryabkova/Умножение матриц методом Штрассена - История изменений

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

2017-12-01T15:20:41Z

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

← Предыдущая версия		Версия от 15:20, 1 декабря 2017
Строка 227:		Строка 227:
	* число процессоров: 1, 7, 49, 343,		* число процессоров: 1, 7, 49, 343,
	* размер матрицы: 14, 28, 56, 112, 224, 392, 448, 784, 896, 1568, 1792, 3136, 3584, 6272, 7168, 12544, 14336.		* размер матрицы: 14, 28, 56, 112, 224, 392, 448, 784, 896, 1568, 1792, 3136, 3584, 6272, 7168, 12544, 14336.
	На следующем рисунке приведен график производительности реализованного алгоритма ~~в зависимости от числа процессоров~~ при фиксированной вычислительной сложности задачи.		На следующем рисунке приведен график производительности реализованного алгоритма при фиксированной вычислительной сложности задачи.

	[[File:2nd.png\|center\|thumb\|800px\|Рисунок 2. График ~~сильной масштабируемости~~ алгоритма Штрассена]]		[[File:2nd.png\|center\|thumb\|800px\|Рисунок 2. График производительности алгоритма Штрассена]]

			Видно, что с увеличением числа процессоров производительность растет, однако отношение ее прироста к увеличению числа процессоров значительно меньше единицы.

	* '''Сильная масштабируемость:~~'''~~		Следующий график показывает время работы алгоритма для различных входных параметров.

			[[File:Screenshot from 2017-11-30 23-04-13.png\|center\|thumb\|800px\|Рисунок 3. График времени работы алгоритма Штрассена]]

			Время работы программы резко возрастает на больших матрицах при малом числе процессоров.

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

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

2017-12-01T00:12:13Z

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

← Предыдущая версия		Версия от 00:12, 1 декабря 2017
Строка 227:		Строка 227:
	* число процессоров: 1, 7, 49, 343,		* число процессоров: 1, 7, 49, 343,
	* размер матрицы: 14, 28, 56, 112, 224, 392, 448, 784, 896, 1568, 1792, 3136, 3584, 6272, 7168, 12544, 14336.		* размер матрицы: 14, 28, 56, 112, 224, 392, 448, 784, 896, 1568, 1792, 3136, 3584, 6272, 7168, 12544, 14336.
	На ~~следующих рисунках~~ приведен график ~~времени работы~~ реализованного алгоритма в зависимости от ~~изменяемых параметров~~.		На следующем рисунке приведен график производительности реализованного алгоритма в зависимости от числа процессоров при фиксированной вычислительной сложности задачи.

	[[File:~~Screenshot_from_2017-11-30_23-04-13~~.png\|center\|thumb\|800px\|Рисунок 2. ]]		[[File:2nd.png\|center\|thumb\|800px\|Рисунок 2. График сильной масштабируемости алгоритма Штрассена]]
	~~[[File:Screenshot_from_2017-11-30_23-07-00.png\|center\|thumb\|800px\|Рисунок 3. ]]~~
	~~[[File:Screenshot_from_2017-11-30_23-05-23.png\|center\|thumb\|800px\|Рисунок 4.~~ ]]

	На графике видно, что при маленьком числе процессов алгоритм сильно теряет эффективность на больших матрицах.

	~~Исследуем сильную и слабую масштабируемость алгоритма.~~		* '''Сильная масштабируемость:'''

	* '''Сильная масштабируемость.''':

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

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

2017-11-30T21:25:21Z

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

← Предыдущая версия		Версия от 21:25, 30 ноября 2017
Строка 222:		Строка 222:

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

			Проведём исследование масштабируемости параллельной реализации алгоритма Штрассена. Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета.
			Изменяемые параметры запуска реализации:
			* число процессоров: 1, 7, 49, 343,
			* размер матрицы: 14, 28, 56, 112, 224, 392, 448, 784, 896, 1568, 1792, 3136, 3584, 6272, 7168, 12544, 14336.
			На следующих рисунках приведен график времени работы реализованного алгоритма в зависимости от изменяемых параметров.

			[[File:Screenshot_from_2017-11-30_23-04-13.png\|center\|thumb\|800px\|Рисунок 2. ]]
			[[File:Screenshot_from_2017-11-30_23-07-00.png\|center\|thumb\|800px\|Рисунок 3. ]]
			[[File:Screenshot_from_2017-11-30_23-05-23.png\|center\|thumb\|800px\|Рисунок 4. ]]

			На графике видно, что при маленьком числе процессов алгоритм сильно теряет эффективность на больших матрицах.

			Исследуем сильную и слабую масштабируемость алгоритма.

			* '''Сильная масштабируемость.''':

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

Y.ryabkova: /* Свойства и структура алгоритмов */

2017-11-30T17:54:37Z

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

@@ Строка 189: / Строка 189: @@
 == Ресурс параллелизма алгоритма ==
 == Входные и выходные данные алгоритма ==
 == Свойства алгоритма ==

Y.ryabkova: /* Свойства и структура алгоритмов */

2017-11-30T16:17:14Z

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

← Предыдущая версия		Версия от 16:17, 30 ноября 2017
Строка 181:		Строка 181:

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

			Граф алгоритма зависит от параметра <math> m </math>, то есть от заданного числа рекурсивных шагов. На рисунке изображен граф при <math> m = 1 </math>, отражающий макроструктуру алгоритма (первая схема реализации последовательного алгоритма).

			[[File:Diagram.png\|center\|thumb\|800px\|Рисунок 1. Операции в последовательном алгоритме Штрассена при ''m = 1''. Вершина ''mul()'' означает вызов классического метода умножения матриц.]]

			Как видно, на каждом уровне все операции могут выполняться параллельно и независимо друг от друга. При увеличении <math> m </math> на единицу, число уровней будет увеличиваться на два. Например, на данном графе это означает, что после вычисления всех <math> S_{i}, T_{i} </math> из входных данных <math> A, B</math> будут производиться аналогичные вычисления для каждой пары <math> S_{i}, T_{i} </math>. Таким образом, новый уровень графа будет содержать <math>2 \cdot 49</math> макроопераций. Из аналогичных соображений после вызовов ''mul()'' из возвращаемых значений надо будет сначала вычислить <math> \alpha_{i} </math> (семь независимых макроопераций), а уже из этих значений получить матрицу <math> С </math>.

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

Y.ryabkova: /* Свойства и структура алгоритмов */

2017-11-30T08:05:57Z

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

← Предыдущая версия		Версия от 08:05, 30 ноября 2017
Строка 167:		Строка 167:
	Получена сложность первого этапа алгоритма.		Получена сложность первого этапа алгоритма.

	'''Второй этап''' включает в себя решение <math>7^m</math> задач перемножения матриц порядка <math> \frac{n}{2^{m}} </math> по классическому алгоритму, что требует <math>7^m \left(\frac{n}{2^{m}}\right)^3</math> умножений и <math>7^m \left(\frac{n}{2^{m}}\right)^2\left(\frac{n}{2^{m}}-1\right)</math> сложений, всего <math>O\left(\frac{n^3}{2^{3m}}\right)</math> арифметических операций.		'''Второй этап''' включает в себя решение <math>7^m</math> задач перемножения матриц порядка <math> \frac{n}{2^{m}} </math> по классическому алгоритму, что требует <math>7^m \left(\frac{n}{2^{m}}\right)^3</math> умножений и <math>7^m \left(\frac{n}{2^{m}}\right)^2\left(\frac{n}{2^{m}}-1\right)</math> сложений, всего <math>O\left(\frac{n^3}{2^{3m}}\right)</math> арифметических операций.<br>

	'''Всего''' последовательный алгоритм Штрассена требует:		'''Всего''' последовательный алгоритм Штрассена требует:
Строка 178:		Строка 178:
	Таким образом, получена оценка сложности последовательного алгоритма Штрассена с максимально возможным числом <math>m = L</math> рекурсивных шагов, соответствующая максимальной оценке сложности первого этапа алгоритма для произвольного <math>m</math>. Эта оценка асимптотически лучше оценки для классического метода перемножения матриц, требующего <math>O(n^3)</math> операций.		Таким образом, получена оценка сложности последовательного алгоритма Штрассена с максимально возможным числом <math>m = L</math> рекурсивных шагов, соответствующая максимальной оценке сложности первого этапа алгоритма для произвольного <math>m</math>. Эта оценка асимптотически лучше оценки для классического метода перемножения матриц, требующего <math>O(n^3)</math> операций.

	Стоит отметить роль правильного выбора параметра <math> m </math>. Из полученных оценок видно, что при малых <math> m </math> сложность алгоритма с уменьшением этого параметра будет стремиться к кубической сложности классического метода, ~~однако~~ при <math> m </math>, очень близких к <math> L </math>, алгоритм будет требовать большего числа сложений, чем классический метод, ~~которое~~ будет увеличиваться с ~~ростом~~ <math> m </math>. Отсюда следует, что существует некоторое оптимальное значение <math> m \in [1, L] </math>, которое минимизирует число арифметических операций всего алгоритма. Также при выборе <math> m </math> стоит учитывать роль накладных расходов на реализацию рекурсии при малых размерах матриц.		Стоит отметить роль правильного выбора параметра <math> m </math>. Из полученных оценок видно, что при малых <math> m </math> сложность алгоритма с уменьшением этого параметра будет стремиться к кубической сложности классического метода, а значит <math> m </math> стоит выбирать относительно близким к <math> L </math>. Однако, при <math> m </math>, очень близких к <math> L </math>, алгоритм на последних рекурсивных шагах будет применяться на матрицах малых размеров и требовать большего числа сложений, чем классический метод, и эта разница будет увеличиваться с уменьшением размера матрицы, что соответствует увеличению <math> m </math>. Отсюда следует, что существует некоторое оптимальное значение <math> m \in [1, L] </math>, которое минимизирует число арифметических операций всего алгоритма и выбирается исходя из минимального размера матрицы, на которой описанный в первом этапе рекурсивный алгоритм будет эффективнее классического. Также при выборе <math> m </math> стоит учитывать роль накладных расходов на реализацию рекурсии при малых размерах матриц.

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

Y.ryabkova: /* Свойства и структура алгоритмов */

2017-11-30T07:52:36Z

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

Внесённые изменения

Y.ryabkova: /* Схема реализации последовательного алгоритма */

2017-11-30T04:50:59Z

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

← Предыдущая версия		Версия от 04:50, 30 ноября 2017
Строка 147:		Строка 147:
	3. Изменение значений блоков матрицы <math> С </math> в соответствии с формулами алгоритма в зависимости от номера полученной после рекурсивного вызова матрицы <math> \alpha_{i} </math>.		3. Изменение значений блоков матрицы <math> С </math> в соответствии с формулами алгоритма в зависимости от номера полученной после рекурсивного вызова матрицы <math> \alpha_{i} </math>.

	Порядок итераций такого цикла может быть произвольным, но они должны выполняться строго последовательно. ~~Такая структура~~ позволяет выделить память всего для трёх <math>\frac{k}{2}\times\frac{k}{2}</math>-матриц на каждом рекурсивном шаге: для одной пары <math> S_{i}, T_{i} </math> и результата их произведения <math> \alpha_{i} </math>, и на каждой итерации цикла использовать одни и те же области памяти для хранения соответствующей тройки матриц.		Порядок итераций такого цикла может быть произвольным, но они должны выполняться строго последовательно. Такое требование позволяет выделить память всего для трёх <math>\frac{k}{2}\times\frac{k}{2}</math>-матриц на каждом рекурсивном шаге: для одной пары <math> S_{i}, T_{i} </math> и результата их произведения <math> \alpha_{i} </math>, и на каждой итерации цикла использовать одни и те же области памяти для хранения соответствующей тройки матриц.

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

Y.ryabkova: /* Свойства и структура алгоритмов */

2017-11-30T04:47:23Z

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

@@ Строка 79: / Строка 79: @@
 == Вычислительное ядро алгоритма ==
-Вычислительное ядро последовательного варианта алгоритма Штрассена на каждом рекурсивном шаге, кроме последнего, представляет из себя вычисление матриц <math> S_{i}, \: T_{i}, i = \overline{1, 7} </math>, и блоков матрицы <math> C </math> из матриц <math> \alpha_{i}, i = \overline{1, 7} </math>. Все эти вычисления сводятся к <math> 18 </math> операциям сложения (вычитания) матриц порядка <math> k </math>, зависящего от номера шага <math> s_m </math> следующим образом: <math> k = \frac{n}{2^{s_m}} </math>. Операции выполняются поэлементно.
+Вычислительное ядро последовательного варианта алгоритма Штрассена на каждом рекурсивном шаге, кроме последнего, можно составить из вычисления матриц <math> S_{i}, T_{i}, \: i = \overline{1, 7} </math>, и блоков матрицы <math> C </math> из матриц <math> \alpha_{i}, \: i = \overline{1, 7} </math> по формулам, данным в математическом описании алгоритма. Все эти вычисления представляют из себя <math> 18 </math> операций сложения (вычитания) матриц порядка <math> k </math>, зависящего от номера шага <math> s_m </math> следующим образом: <math> k = \frac{n}{2^{s_m}} </math>. Операции выполняются поэлементно. Таким образом, вычислительное ядро алгоритма сводится к <math> 18 </math> операциям сложения (вычитания) матриц или к <math> 18 k^2 </math> операциям сложения (вычитания) чисел на каждом рекурсивном шаге.
 == Макроструктура алгоритма ==
 == Схема реализации последовательного алгоритма ==
 == Последовательная сложность алгоритма ==

Y.ryabkova: /* Вычислительное ядро алгоритма */

2017-11-30T01:25:57Z

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

← Предыдущая версия		Версия от 01:25, 30 ноября 2017
Строка 79:		Строка 79:
	== Вычислительное ядро алгоритма ==		== Вычислительное ядро алгоритма ==

	Вычислительное ядро последовательного варианта алгоритма Штрассена на каждом рекурсивном шаге, кроме последнего, представляет из себя вычисление матриц <math> S_{i}, \: T_{i}, i = \overline{1, 7} </math>, и блоков матрицы <math> C </math> из матриц <math> \alpha_{i}, i = \overline{1, 7} </math>. Все эти вычисления сводятся к <math> 18 </math> ~~поэлементным~~ операциям сложения (вычитания) матриц порядка <math> k </math>, зависящего от номера шага <math> s_m </math> следующим образом: <math> k = \frac{n}{2^{s_m}} </math>.		Вычислительное ядро последовательного варианта алгоритма Штрассена на каждом рекурсивном шаге, кроме последнего, представляет из себя вычисление матриц <math> S_{i}, \: T_{i}, i = \overline{1, 7} </math>, и блоков матрицы <math> C </math> из матриц <math> \alpha_{i}, i = \overline{1, 7} </math>. Все эти вычисления сводятся к <math> 18 </math> операциям сложения (вычитания) матриц порядка <math> k </math>, зависящего от номера шага <math> s_m </math> следующим образом: <math> k = \frac{n}{2^{s_m}} </math>. Операции выполняются поэлементно.

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