Участник:DVIN/Ортогонализация Грамма-Шмидта - История изменений

ASA в 12:52, 23 ноября 2016

2016-11-23T12:52:00Z

← Предыдущая версия		Версия от 12:52, 23 ноября 2016
Строка 1:		Строка 1:
			{{Assignment\|ASA}}
	{{Assignment}}

	{{algorithm		{{algorithm

DVIN в 13:22, 21 ноября 2016

2016-11-21T13:22:01Z

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

			{{Assignment}}

	{{algorithm		{{algorithm
	\| name = Ортогонализация Грама-Шмидта		\| name = Ортогонализация Грама-Шмидта

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

2016-11-21T13:07:46Z

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

ASA в 11:21, 21 ноября 2016

2016-11-21T11:21:05Z

← Предыдущая версия		Версия от 11:21, 21 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment}}~~

	{{algorithm		{{algorithm
	\| name = Ортогонализация Грама-Шмидта		\| name = Ортогонализация Грама-Шмидта

DVIN в 17:20, 18 ноября 2016

2016-11-18T17:20:28Z

← Предыдущая версия		Версия от 17:20, 18 ноября 2016
Строка 1:		Строка 1:
			{{Assignment}}

	{{algorithm		{{algorithm
	\| name = Ортогонализация Грама-Шмидта		\| name = Ортогонализация Грама-Шмидта

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

2016-11-18T17:18:12Z

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

← Предыдущая версия		Версия от 17:18, 18 ноября 2016
Строка 317:		Строка 317:
	Общей оценкой масштабируемости будем называть средний размер вклада каждого элемента рассматриваемой области значений в общую оценку по всем элементам рассматриваемой области параметров запуска.		Общей оценкой масштабируемости будем называть средний размер вклада каждого элемента рассматриваемой области значений в общую оценку по всем элементам рассматриваемой области параметров запуска.
	* По двум направлениям: 0.002079.		* По двум направлениям: 0.002079.
			[https://bitbucket.org/d_2007_90/gram-schmidt-process/src Реализация алгоритма]

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

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

2016-11-18T16:11:18Z

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

← Предыдущая версия		Версия от 16:11, 18 ноября 2016
Строка 282:		Строка 282:
	=== Возможные способы и особенности параллельной реализации алгоритма===		=== Возможные способы и особенности параллельной реализации алгоритма===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проведём исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI.		Проведём исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась собственная параллельная реализация алгоритма, написанная на языке C++ с использованием стандарта MPI.

	Версия MPI - intel opemmpi/1.8.4-icc		Версия MPI - intel opemmpi/1.8.4-icc

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

2016-11-18T16:02:54Z

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

← Предыдущая версия		Версия от 16:02, 18 ноября 2016
Строка 283:		Строка 283:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проведём исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI.		Проведём исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI.

	Версия MPI - intel opemmpi/1.8.4-icc		Версия MPI - intel opemmpi/1.8.4-icc

	Модель используемого CPU - Intel Xeon X5570 2.93GHz		Модель используемого CPU - Intel Xeon X5570 2.93GHz

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

2016-11-18T16:01:37Z

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

← Предыдущая версия		Версия от 16:01, 18 ноября 2016
Строка 283:		Строка 283:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===
	Проведём исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI.		Проведём исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI.
			Версия MPI - intel opemmpi/1.8.4-icc
			Модель используемого CPU - Intel Xeon X5570 2.93GHz

	Набор и границы значений изменяемых реализации алгоритма:		Набор и границы значений изменяемых реализации алгоритма:

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

2016-11-17T18:22:56Z

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

@@ Строка 294: / Строка 294: @@
 Так как алгоритм не поддается полному распараллеливанию, то при увеличении числа процессоров не происходит значительного ускорения. Это связано с тем, что параллельно можно вычислить лишь <math>b_j</math>. То есть после каждого вычисления <math>b_j</math> можно запускать параллельное вычисление <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Кроме того можно параллельно производить вычитание соответствующего <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Но после этого все процессоры должны синхронизоваться и дождаться когда получат следующий вектор <math>b_j</math>.
-[[File:GramTime.jpg|мини|upright=3|centre|framecentre|frame]]
+Проведём еще одно исследование исследование масштабируемости параллельной реализации процесса ортогонализации Грама-Шмидта для меньшего числа процессоров. Исследование проводилось на суперкомпьютере "Ломоносов" [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета]. Исследовалась параллельная реализация алгоритма, написанная с использованием стандарта MPI.
-[[File:GramPerf.jpg|мини|upright=3|centre|framecentre|frame]]
-[[File:GramParEffi.jpg|мини|upright=3|centre|framecentre|frame]]
+Набор и границы значений изменяемых реализации алгоритма:
 === Динамические характеристики и эффективность реализации алгоритма ===

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

	На следующем рисунке приведен график времени работы алгоритма в зависимости от числа процессов и размерности векторов.		На следующем рисунке приведен график времени работы алгоритма в зависимости от числа процессов и размерности векторов.
	[[File:gram-schmidt.jpg\|мини\|upright=3\|centre\|framecentre\|~~frame~~]]		[[File:gram-schmidt.jpg\|мини\|upright=3\|centre\|framecentre\|Рис. 6 Время работы алгоритма в зависимости от числа процессоров и размерности задачи]]

	Так как алгоритм не поддается полному распараллеливанию, то при увеличении числа процессоров не происходит значительного ускорения. Это связано с тем, что параллельно можно вычислить лишь <math>b_j</math>. То есть после каждого вычисления <math>b_j</math> можно запускать параллельное вычисление <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Кроме того можно параллельно производить вычитание соответствующего <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Но после этого все процессоры должны синхронизоваться и дождаться когда получат следующий вектор <math>b_j</math>.		Так как алгоритм не поддается полному распараллеливанию, то при увеличении числа процессоров не происходит значительного ускорения. Это связано с тем, что параллельно можно вычислить лишь <math>b_j</math>. То есть после каждого вычисления <math>b_j</math> можно запускать параллельное вычисление <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Кроме того можно параллельно производить вычитание соответствующего <math>\mathbf{proj}_{\mathbf{b_j}}\,\mathbf{a_i}</math> для всех <math>i=j+1..N</math>. Но после этого все процессоры должны синхронизоваться и дождаться когда получат следующий вектор <math>b_j</math>.
Строка 305:		Строка 305:
	* размерность векторов [20 : 400] с шагом 20.		* размерность векторов [20 : 400] с шагом 20.
	На графике 1 приведено время работы программы для разных значений размерности матрицы и числа процессоров.		На графике 1 приведено время работы программы для разных значений размерности матрицы и числа процессоров.
	[[File:GramTime.jpg\|мини\|upright=3\|centre\|framecentre\|1]]		[[File:GramTime.jpg\|мини\|upright=3\|centre\|framecentre\|1\|Рис. 7 Время работы программы в зависимости от числа процессоров и размерности задачи]]
	На графике 2 приведена производительность работы программы для разных значений размерности матрицы и числа процессоров.		На графике 2 приведена производительность работы программы для разных значений размерности матрицы и числа процессоров.
	[[File:GramPerf.jpg\|мини\|upright=3\|centre\|framecentre\|2]]		[[File:GramPerf.jpg\|мини\|upright=3\|centre\|framecentre\|2\|Рис. 8 Производительность программы в зависимости от количество процессоров и размерности задачи]]
	На графике 3 приведена эффективность распараллеливания работы программы для разных значений размерности матрицы и числа процессоров.		На графике 3 приведена эффективность распараллеливания работы программы для разных значений размерности матрицы и числа процессоров.
	[[File:GramParEffi.jpg\|мини\|upright=3\|centre\|framecentre\|3]]		[[File:GramParEffi.jpg\|мини\|upright=3\|centre\|framecentre\|3\|Рис. 9 Эффективность распараллеливания алгоритма]]
	Оценим значения масштабируемости данной реализации:		Оценим значения масштабируемости данной реализации:
	Общей оценкой масштабируемости по числу процессов будем называть среднее значение вклада каждого элемента рассматриваемой области значений в общую оценку по числу процессов по всем элементам рассматриваемой области параметров запуска.		Общей оценкой масштабируемости по числу процессов будем называть среднее значение вклада каждого элемента рассматриваемой области значений в общую оценку по числу процессов по всем элементам рассматриваемой области параметров запуска.