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

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:50:46Z

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

← Предыдущая версия		Версия от 18:50, 20 ноября 2016
Строка 302:		Строка 302:
	Построим оценки масштабируемости выбранной реализации:		Построим оценки масштабируемости выбранной реализации:
	* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.		* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.
	* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени <math>n</math> размера матрицы <math>N=2^{n}</math>. При увеличении размера матрицы эффективность также увеличивается~~. Это подтверждает предположение о том~~, что размер задачи влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска увеличивается незначительно.		* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени <math>n</math> размера матрицы <math>N=2^{n}</math>. При увеличении размера матрицы эффективность также увеличивается, но скорость возрастания уменьшается.
	По двум направлениям: При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая.		По двум направлениям: При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая.

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:48:26Z

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

← Предыдущая версия		Версия от 18:48, 20 ноября 2016
Строка 302:		Строка 302:
	Построим оценки масштабируемости выбранной реализации:		Построим оценки масштабируемости выбранной реализации:
	* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.		* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.
	* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени <math>n</math> размера матрицы <math>N</math>. ~~Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения~~. Это подтверждает предположение о том, что размер задачи ~~сильно~~ влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска ~~сильно~~ увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.		* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени <math>n</math> размера матрицы <math>N=2^{n}</math>. При увеличении размера матрицы эффективность также увеличивается. Это подтверждает предположение о том, что размер задачи влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска увеличивается незначительно.
	По двум направлениям: ~~0,000403.~~ При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.		По двум направлениям: При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая.

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

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:38:51Z

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

← Предыдущая версия		Версия от 18:38, 20 ноября 2016
Строка 302:		Строка 302:
	Построим оценки масштабируемости выбранной реализации:		Построим оценки масштабируемости выбранной реализации:
	* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.		* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.
	* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок n ~~степени~~ размера матрицы. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.		* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок степени <math>n</math> размера матрицы <math>N</math>. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.
	По двум направлениям: 0,000403. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.		По двум направлениям: 0,000403. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:37:31Z

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

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

	Построим оценки масштабируемости выбранной реализации:		Построим оценки масштабируемости выбранной реализации:
	* При увеличении числа процессов ~~эффективность~~ на рассмотренной области изменений параметров запуска ~~уменьшается, однако в целом уменьшение не очень быстрое~~. Малая интенсивность изменения объясняется крайне низкой общей эффективностью работы приложения с максимумом в 2,~~65%~~, и значение эффективности на рассмотренной области значений быстро доходит до десятых долей процента. Это свидетельствует о том, ~~что на большей части области значений нет интенсивного снижения эффективности~~. Это объясняется также тем, что с ростом вычислительной сложности падение эффективности становится не таким быстрым. Уменьшение эффективности на рассмотренной области работы параллельной программы объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. С ростом вычислительной сложности задачи эффективность снижается так же быстро, но при больших значениях числа процессов. Это ~~подтверждает предположение о том~~, что ~~накладные расходы начинают сильно превалировать над вычислениями~~.		* При увеличении числа процессов производительность на рассмотренной области изменений параметров запуска увеличивается практически линейно. В следствии этого эффективность реализации, как видно по графику, перестает изменяться при увеличении числа процессоров и равна примерно 1,7%.
	~~По размеру задачи: 0,06017. При увеличении~~ размера ~~задачи эффективность возрастает~~. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.		* При увеличении размера матрицы производительность на рассмотренной области изменений параметров запуска увеличивается логарифмически. Это связанно с тем, что количество операций зависит от количества единиц после бинарного произведения. Поэтому наиболее влияет порядок n степени размера матрицы. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.
	По двум направлениям: 0,000403. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.		По двум направлениям: 0,000403. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:15:04Z

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

← Предыдущая версия		Версия от 18:15, 20 ноября 2016
Строка 297:		Строка 297:
	На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.

	[[file:~~Prois~~.jpg\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:Prois1.jpg\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:~~Effec~~.jpg\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:Effec1.jpg\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

			Построим оценки масштабируемости выбранной реализации:
			* При увеличении числа процессов эффективность на рассмотренной области изменений параметров запуска уменьшается, однако в целом уменьшение не очень быстрое. Малая интенсивность изменения объясняется крайне низкой общей эффективностью работы приложения с максимумом в 2,65%, и значение эффективности на рассмотренной области значений быстро доходит до десятых долей процента. Это свидетельствует о том, что на большей части области значений нет интенсивного снижения эффективности. Это объясняется также тем, что с ростом вычислительной сложности падение эффективности становится не таким быстрым. Уменьшение эффективности на рассмотренной области работы параллельной программы объясняется быстрым ростом накладных расходов на организацию параллельного выполнения. С ростом вычислительной сложности задачи эффективность снижается так же быстро, но при больших значениях числа процессов. Это подтверждает предположение о том, что накладные расходы начинают сильно превалировать над вычислениями.
			По размеру задачи: 0,06017. При увеличении размера задачи эффективность возрастает. Эффективность возрастает тем быстрее, чем большее число процессов используется для выполнения. Это подтверждает предположение о том, что размер задачи сильно влияет на эффективность выполнения приложения. Оценка показывает, что с ростом размера задачи эффективность на рассмотренной области значений параметров запуска сильно увеличивается. Также, учитывая разницу максимальной и минимальной эффективности в 2,5%, можно сделать вывод, что рост эффективности при увеличении размера задачи наблюдается на большей части рассмотренной области значений.
			По двум направлениям: 0,000403. При рассмотрении увеличения как вычислительной сложности, так и числа процессов на всей рассмотренной области значений эффективность увеличивается, однако скорость увеличения эффективности небольшая. В совокупности с тем фактом, что разница между максимальной и минимальной эффективностью на рассмотренной области значений параметров небольшая, эффективность с увеличением масштабов возрастает, но медленно и с небольшими перепадами.

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

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:03:50Z

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

← Предыдущая версия		Версия от 18:03, 20 ноября 2016
Строка 297:		Строка 297:
	На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.

	[[file:Pr.jpg\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:Prois.jpg\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:Ef.jpg\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:Effec.jpg\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

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

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:03:23Z

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

← Предыдущая версия		Версия от 18:03, 20 ноября 2016
Строка 297:		Строка 297:
	На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.

	[[file:Pr.~~png~~\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:Pr.jpg\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:Ef.~~png~~\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:Ef.jpg\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

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

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:02:23Z

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

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

	На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.
	Задача данного раздела - показать пределы [[глоссарий#Масштабируемость\|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость\|''сильной'']] и [[глоссарий#Слабая масштабируемость\|''слабой'']] масштабируемости алгоритма и его реализаций.

	Масштабируемость алгоритма определяет свойства самого алгоритма безотносительно конкретных особенностей используемого компьютера. Она показывает, насколько параллельные свойства алгоритма позволяют использовать возможности растущего числа процессорных элементов. Масштабируемость параллельных программ определяется как относительно конкретного компьютера, так и относительно используемой технологии программирования, и в этом случае она показывает, насколько может вырасти реальная производительность данного компьютера на данной программе, записанной с помощью данной технологии программирования, при использовании бóльших вычислительных ресурсов (ядер, процессоров, вычислительных узлов).		[[file:Pr.png\|thumb\|center\|700px\|Рис.5 Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
			[[file:Ef.png\|thumb\|center\|700px\|Рис.5 Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]
	Ключевой момент данного раздела заключается в том, чтобы показать ''реальные параметры масштабируемости программы'' для данного алгоритма на различных вычислительных платформах в зависимости от числа процессоров и размера задачи [4]. При этом важно подобрать такое соотношение между числом процессоров и размером задачи, чтобы отразить все характерные точки в поведении параллельной программы, в частности, достижение максимальной производительности, а также тонкие эффекты, возникающие, например, из-за блочной структуры алгоритма или иерархии памяти.

	~~На рис~~.5~~. показана масштабируемость классического алгоритма умножения плотных матриц~~ в зависимости от числа процессоров и размера ~~задачи. На графике хорошо видны области с большей производительностью, отвечающие уровням кэш-памяти~~.
	[[file:~~Масштабируемость перемножения матриц производительность~~.png\|thumb\|center\|700px\|Рис.5 ~~Масштабируемость классического алгоритма умножения плотных матриц~~ в зависимости от числа процессоров и размера ~~задачи~~]]

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

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T18:00:34Z

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

← Предыдущая версия		Версия от 18:00, 20 ноября 2016
Строка 295:		Строка 295:
	* максимальная эффективность реализации 3.3003%.		* максимальная эффективность реализации 3.3003%.

	На следующих рисунках приведены графики производительности и эффективности выбранной реализации ~~разложения Холецкого~~ в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики производительности и эффективности выбранной реализации построение матрицы Адамара в зависимости от изменяемых параметров запуска.
	Задача данного раздела - показать пределы [[глоссарий#Масштабируемость\|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость\|''сильной'']] и [[глоссарий#Слабая масштабируемость\|''слабой'']] масштабируемости алгоритма и его реализаций.		Задача данного раздела - показать пределы [[глоссарий#Масштабируемость\|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость\|''сильной'']] и [[глоссарий#Слабая масштабируемость\|''слабой'']] масштабируемости алгоритма и его реализаций.

Бугаков Юрий: /* Масштабируемость алгоритма и его реализации */

2016-11-20T17:59:57Z

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

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

	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==
			Исследование проводилось на суперкомпьютере "Blue Gene".

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

			* число процессоров [1, 2, 4, 8,..., 1024] ;
			* размер матрицы [2, 4, 8,..., 2048].

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

			* минимальная эффективность реализации 0.0121%;
			* максимальная эффективность реализации 3.3003%.

			На следующих рисунках приведены графики производительности и эффективности выбранной реализации разложения Холецкого в зависимости от изменяемых параметров запуска.
	Задача данного раздела - показать пределы [[глоссарий#Масштабируемость\|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость\|''сильной'']] и [[глоссарий#Слабая масштабируемость\|''слабой'']] масштабируемости алгоритма и его реализаций.		Задача данного раздела - показать пределы [[глоссарий#Масштабируемость\|''масштабируемости'']] алгоритма на различных платформах. Очень важный раздел. Нужно выделить, описать и оценить влияние точек барьерной синхронизации, глобальных операций, операций сборки/разборки данных, привести оценки или провести исследование [[глоссарий#Сильная масштабируемость\|''сильной'']] и [[глоссарий#Слабая масштабируемость\|''слабой'']] масштабируемости алгоритма и его реализаций.