Участник:Евгений Раев/Построение матрицы Адамара произвольного размера - История изменений

Sleo в 10:56, 1 декабря 2016

2016-12-01T10:56:55Z

← Предыдущая версия		Версия от 10:56, 1 декабря 2016
Строка 1:		Строка 1:
	{{Assignment}}		{{Assignment\|Sleo}}
	{{algorithm		{{algorithm
	\| name = Построение матрицы Адамара произвольного размера		\| name = Построение матрицы Адамара произвольного размера

Евгений Раев: /* Масштабируемость алгоритма и его реализации */

2016-11-21T09:21:17Z

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

← Предыдущая версия		Версия от 09:21, 21 ноября 2016
Строка 255:		Строка 255:
	*число процессоров: [2,32] с шагом 2;		*число процессоров: [2,32] с шагом 2;
	*размер матрицы: степени двойки в диапазоне [2, 16] с шагом 1, то есть, реальная размерность матрицы была в диапазоне [4, 65536].		*размер матрицы: степени двойки в диапазоне [2, 16] с шагом 1, то есть, реальная размерность матрицы была в диапазоне [4, 65536].

	~~В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:~~
	*минимальная эффективность реализации
	*максимальная эффективность реализации

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

Евгений Раев: /* Литература */

2016-11-21T09:19:40Z

Литература

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

	== Литература ==		== Литература ==
	~~[1] Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — Алгебраический аппарат квантовой информатики 2~~

	[2] Википедия – свободная энциклопедия [Электронный ресурс]. - https://en.wikipedia.org/wiki/Hadamard_transform. - (дата обращения: 15.10.2016).

Евгений Раев: /* Масштабируемость алгоритма и его реализации */

2016-11-21T09:19:15Z

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

← Предыдущая версия		Версия от 09:19, 21 ноября 2016
Строка 263:		Строка 263:
	[[Файл:raev_time.png\|500px\|thumb\|center\|Время работы параллельного алгоритма в зависимости от размерности системы и числа процессоров.]]		[[Файл:raev_time.png\|500px\|thumb\|center\|Время работы параллельного алгоритма в зависимости от размерности системы и числа процессоров.]]

	~~Также представлен график~~ производительности:		Так как в нашем алгоритме существенно мало операция с плавающей точкой, в качестве альтернативы Flops использовалось значение [https://en.wikipedia.org/wiki/Instructions_per_second#Millions_of_instructions_per_second MIPS] . График производительности:
	[[Файл:raev_perfomance.png\|500px\|thumb\|center\|Изменение производительности параллельного алгоритма в зависимости от размерности системы и числа процессоров.]]		[[Файл:raev_perfomance.png\|500px\|thumb\|center\|Изменение производительности параллельного алгоритма в зависимости от размерности системы и числа процессоров.]]

Евгений Раев: /* Масштабируемость алгоритма и его реализации */

2016-11-21T09:14:00Z

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

← Предыдущая версия		Версия от 09:14, 21 ноября 2016
Строка 254:		Строка 254:
	Набор и границы значений изменяемых параметров запуска реализации алгоритма:		Набор и границы значений изменяемых параметров запуска реализации алгоритма:
	*число процессоров: [2,32] с шагом 2;		*число процессоров: [2,32] с шагом 2;
	*размер матрицы: степени двойки в диапазоне [2, 16], то есть, реальная размерность матрицы была в диапазоне [4, 65536].		*размер матрицы: степени двойки в диапазоне [2, 16] с шагом 1, то есть, реальная размерность матрицы была в диапазоне [4, 65536].

	В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:		В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
Строка 272:		Строка 272:

	Построим оценки масштабируемости, используя полученные результаты:		Построим оценки масштабируемости, используя полученные результаты:
	*По размерности задачи. ~~Увеличение размерности задачи приводит к увеличению~~ производительности.		*По размерности задачи. При увеличении размера матрицы, производительность также увеличивается. При этом, интересен тот факт, что пиковое значение производительности приходится не на максимальное возможную размерность.
	*По числу процессоров. С ростом числа процессоров растет производительность~~, но при~~ малых размерностях ~~задачи~~ этот рост незначителен. Это связано с дополнительными издержками по записи в участок памяти каждого процессора вспомогательного массива вычетов, ~~а также с обменом информации между процессорами~~.		*По числу процессоров. С ростом числа процессоров растет производительность. На малых размерностях матрицы этот рост не очень заметен, но для больших порядков количество процессоров оказывает ключевую роль на производительность.
	*По двум направлениям. При увеличении ~~как~~ числа процессоров~~, так~~ и размерности ~~задачи~~, производительность увеличивается. Причем чем больше используется процессоров, тем сильнее увеличивается производительность при увеличении размерности.		*По двум направлениям. При одноврменном увеличении числа процессоров и размерности матрицы, производительность растет.

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

Евгений Раев: /* Масштабируемость алгоритма и его реализации */

2016-11-21T09:02:20Z

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

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

	==== Масштабируемость алгоритма и его реализации ====		==== Масштабируемость алгоритма и его реализации ====
	Исследование масштабируемости параллельной реализации алгоритма построения матрицы Адамара проводилось на суперкомпьютере «Ломоносов»<ref>http://parallel.ru/cluster</ref>. ~~Для этого была исследована~~ собственная реализация алгоритма с использованием средств MPI.		Исследование масштабируемости параллельной реализации алгоритма построения матрицы Адамара проводилось на суперкомпьютере «Ломоносов»<ref>http://parallel.ru/cluster</ref>. Объектом исследования стала собственная реализация алгоритма с использованием средств MPI.
	Наблюдались две переменные - время выполнения алгоритма и количество выполненных операций. Паратметры запуска - это размерность <math>2^N</math> матрицы Адамара и количество процессоров.		Наблюдались две переменные - время выполнения алгоритма и количество выполненных операций. Паратметры запуска - это размерность <math>2^N</math> матрицы Адамара и количество процессоров.

Строка 269:		Строка 269:


	[https://github.com/analyzehim/parallel/blob/master/task.cpp Исследованная параллельная реализация на языке C++]		[https://github.com/analyzehim/parallel/blob/master/Task%201/task.cpp Исследованная параллельная реализация на языке C++]

	Построим оценки масштабируемости, используя полученные результаты:		Построим оценки масштабируемости, используя полученные результаты:

Евгений Раев: /* Масштабируемость алгоритма и его реализации */

2016-11-21T09:01:07Z

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

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

	==== Масштабируемость алгоритма и его реализации ====		==== Масштабируемость алгоритма и его реализации ====
	Исследование масштабируемости параллельной реализации алгоритма построения матрицы Адамара проводилось на суперкомпьютере «Ломоносов». Для этого была исследована собственная реализация алгоритма с использованием средств MPI.		Исследование масштабируемости параллельной реализации алгоритма построения матрицы Адамара проводилось на суперкомпьютере «Ломоносов»<ref>http://parallel.ru/cluster</ref>. Для этого была исследована собственная реализация алгоритма с использованием средств MPI.
	Наблюдались две переменные - время выполнения алгоритма и количество выполненных операций. Паратметры запуска - это размерность <math>2^N</math> матрицы Адамара и количество процессоров.		Наблюдались две переменные - время выполнения алгоритма и количество выполненных операций. Паратметры запуска - это размерность <math>2^N</math> матрицы Адамара и количество процессоров.

Евгений Раев: /* Математическое описание алгоритма */

2016-11-21T08:15:26Z

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

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

	Тензорное произведение довольно затратно для реализации на вычислительной технике (необходимо хранить в памяти матрицу предыдущего порядка), поэтому существует формула для определения элемента матрицы Адамара по его индексам:		Тензорное произведение довольно затратно для реализации на вычислительной технике (необходимо хранить в памяти матрицу предыдущего порядка), поэтому существует формула для определения элемента матрицы Адамара по его индексам:
	:<math>H_{i,j} = (-1)^{\sum ij}</math>, где <math>i</math> и <math>j</math> - битовые представляения значений индексов, а <math>i j</math> - побитовое умножение. (Описано в ~~[1]~~)		:<math>H_{i,j} = (-1)^{\sum ij}</math>, где <math>i</math> и <math>j</math> - битовые представляения значений индексов, а <math>i j</math> - побитовое умножение. (Описано в <ref>Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — Алгебраический аппарат квантовой информатики 2</ref>)
	То есть, знак элемента матрицы Адамара зависит от количества едининц в побитовом произведении индексов - если это число чётное - то знак положительный, если нечётное - отрицательный.		То есть, знак элемента матрицы Адамара зависит от количества едининц в побитовом произведении индексов - если это число чётное - то знак положительный, если нечётное - отрицательный.

Евгений Раев: /* Общее описание алгоритма */

2016-11-21T08:14:27Z

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

← Предыдущая версия		Версия от 08:14, 21 ноября 2016
Строка 93:		Строка 93:
	Таким образом, получаем последовательность матриц Адамамра размерностью <math>2^n</math>		Таким образом, получаем последовательность матриц Адамамра размерностью <math>2^n</math>

	<math>H^{\otimes n} = H_1 \otimes ... \otimes H_1</math> (Описано в [2]).		<math>H^{\otimes n} = H_1 \otimes ... \otimes H_1</math> (Описано в<ref>Википедия – свободная энциклопедия [Электронный ресурс]. - https://en.wikipedia.org/wiki/Hadamard_transform. - (дата обращения: 15.10.2016).</ref>).

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

Евгений Раев: /* Масштабируемость алгоритма и его реализации */

2016-11-20T13:20:46Z

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

← Предыдущая версия		Версия от 13:20, 20 ноября 2016
Строка 257:		Строка 257:

	В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:		В результате проведённых экспериментов был получен следующий диапазон эффективности реализации алгоритма:
	*минимальная эффективность реализации ~~0.0000029% при n=4, p=2;~~		*минимальная эффективность реализации
	*максимальная эффективность реализации ~~0.323409% при n=908, p=2.~~		*максимальная эффективность реализации

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