Участник:DenisAnuprienko/Метод Штрассена - История изменений

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

2016-12-10T09:44:37Z

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

← Предыдущая версия		Версия от 09:44, 10 декабря 2016
Строка 91:		Строка 91:

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==
	Нет никаких предположений насчет структуры матриц. ~~Предполагается~~, что это обычные плотные матрицы. Они хранятся в виде одномерного массива, что позволяет легко выделять из них подматрицы.		Нет никаких предположений насчет структуры матриц. Считается, что это обычные плотные матрицы. Они хранятся в виде одномерного массива, что позволяет легко выделять из них подматрицы.

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

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

2016-12-10T09:44:05Z

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

← Предыдущая версия		Версия от 09:44, 10 декабря 2016
Строка 88:		Строка 88:

	== Ресурс параллелизма алгоритма ==		== Ресурс параллелизма алгоритма ==
	Умножения, которые необходимы для нахождения матриц <math>M_1, ..., M_7</math>, можно провести параллельно. Их можно предоставить 7 процессам (1 хозяин, который раздает задания 6 рабочим и получает результаты, а также работает вместе с ~~ними~~) или 8 процессам (1 хозяин, который раздает задания 7 рабочим и получает результаты).		Умножения, которые необходимы для нахождения матриц <math>M_1, ..., M_7</math>, можно провести параллельно. Их можно предоставить 7 процессам (1 хозяин, который раздает задания 6 рабочим и получает результаты, а также работает вместе с рабочими) или 8 процессам (1 хозяин, который раздает задания 7 рабочим и получает результаты).

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

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

2016-12-10T09:42:51Z

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

← Предыдущая версия		Версия от 09:42, 10 декабря 2016
Строка 77:		Строка 77:

	== Последовательная сложность алгоритма ==		== Последовательная сложность алгоритма ==
	Метод ~~Штрассен~~ позволяет сократить число умножений, поэтому оценивается именно оно. В методе Штрассена число умножений составляет <math>O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81})</math>.		Метод Штрассена позволяет сократить число умножений, поэтому оценивается именно оно. В методе Штрассена число умножений составляет <math>O(7^{log_2N}) = O(N^{log_27}) \approx O(N^{2.81})</math>.

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

DenisAnuprienko: /* Особенности реализации последовательного алгоритма */

2016-12-07T17:20:22Z

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

← Предыдущая версия		Версия от 17:20, 7 декабря 2016
Строка 105:		Строка 105:
	== Особенности реализации последовательного алгоритма ==		== Особенности реализации последовательного алгоритма ==
	Матрицы хранятся как одномерные массивы. Благодаря этому в составе матрицы легко выделить подматрицу, зная размеры подматрицы и родительской матрицы, а также указатель на начало подматрицы.<br>		Матрицы хранятся как одномерные массивы. Благодаря этому в составе матрицы легко выделить подматрицу, зная размеры подматрицы и родительской матрицы, а также указатель на начало подматрицы.<br>
	В этом состоит выгодное отличие от некоторых существующих реализаций, где при использовании подматриц ~~выделялалась~~ отдельная память.		В этом состоит выгодное отличие от некоторых существующих реализаций, где при использовании подматриц выделяется отдельная память.

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

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

2016-12-07T14:34:07Z

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

← Предыдущая версия		Версия от 14:34, 7 декабря 2016
Строка 121:		Строка 121:
	По описанным в предыдущем пункте причинам предлагаемая реализация с распараллеливанием 1 уровня рекурсии может быть запущена только на определенном количестве процессов. Запуск на другом количестве процессов означает использование уже другой программы, поэтому оценить масшатбируемость в текущей реализации не представляется возможным.		По описанным в предыдущем пункте причинам предлагаемая реализация с распараллеливанием 1 уровня рекурсии может быть запущена только на определенном количестве процессов. Запуск на другом количестве процессов означает использование уже другой программы, поэтому оценить масшатбируемость в текущей реализации не представляется возможным.

			=== Сравнение работы последовательной и параллельной реализаций ===
			Эксперименты проводились на суперкомпьютере [http://users.parallel.ru/wiki/pages/22-config "Ломоносов"]. Использовались gcc и mpicc 4.4.7 с флагом компиляции -O3, а также OpenMPI 1.8.4. Параллельная версия задействовала 8 процессов.
	{\| class="wikitable"		{\| class="wikitable"
	\|+Результаты запусков на "Ломоносове"		\|+Результаты запусков на "Ломоносове"

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

2016-12-07T14:13:55Z

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

@@ Строка 120: / Строка 120: @@
 == Масштабируемость алгоритма и его реализации ==
 По описанным в предыдущем пункте причинам предлагаемая реализация с распараллеливанием 1 уровня рекурсии может быть запущена только на определенном количестве процессов. Запуск на другом количестве процессов означает использование уже другой программы, поэтому оценить масшатбируемость в текущей реализации не представляется возможным.
 == Динамические характеристики и эффективность реализации алгоритма ==

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

2016-11-29T21:18:42Z

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

← Предыдущая версия		Версия от 21:18, 29 ноября 2016
Строка 85:		Строка 85:
	Здесь 7 рекурсивных вызовов функции Strassen можно выполнять параллельно:		Здесь 7 рекурсивных вызовов функции Strassen можно выполнять параллельно:

	[[Файл:~~Strassen_Parallel_1~~.png\|600px\|center]]		[[Файл:Parallel_1.png\|600px\|center]]

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

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

2016-11-29T21:10:06Z

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

← Предыдущая версия		Версия от 21:10, 29 ноября 2016
Строка 80:		Строка 80:

	== Информационный граф ==		== Информационный граф ==
	Рассмотрим блок-схему для последовательной реализации рекурсивной функции Strassen для числа <math>N_{min}</math>, равного 512).		Рассмотрим блок-схему для последовательной реализации рекурсивной функции Strassen для числа <math>N_{min}</math>, равного 512.
	[[Файл:Serial.png\|300px\|center]]		[[Файл:Serial.png\|300px\|center]]

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

2016-11-29T17:01:22Z

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

← Предыдущая версия		Версия от 17:01, 29 ноября 2016
Строка 80:		Строка 80:

	== Информационный граф ==		== Информационный граф ==
	Рассмотрим блок-схему для последовательной реализации рекурсивной функции Strassen ~~(здесь число~~ <math>N_{min}</math> ~~равно~~ 512).		Рассмотрим блок-схему для последовательной реализации рекурсивной функции Strassen для числа <math>N_{min}</math>, равного 512).
	[[Файл:Serial.png\|300px\|center]]		[[Файл:Serial.png\|300px\|center]]

DenisAnuprienko: /* Особенности реализации последовательного алгоритма */

2016-11-29T16:52:04Z

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

← Предыдущая версия		Версия от 16:52, 29 ноября 2016
Строка 104:		Строка 104:

	== Особенности реализации последовательного алгоритма ==		== Особенности реализации последовательного алгоритма ==
			Матрицы хранятся как одномерные массивы. Благодаря этому в составе матрицы легко выделить подматрицу, зная размеры подматрицы и родительской матрицы, а также указатель на начало подматрицы.<br>
			В этом состоит выгодное отличие от некоторых существующих реализаций, где при использовании подматриц выделялалась отдельная память.

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