Cooley-Tukey, scalability - История изменений

ASA в 12:09, 1 июля 2022

2022-07-01T12:09:53Z

← Предыдущая версия		Версия от 12:09, 1 июля 2022
Строка 1:		Строка 1:
			{{level-i}}

	Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации\|3]], [[#Динамические характеристики и эффективность реализации алгоритма\|4]])		Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации\|3]], [[#Динамические характеристики и эффективность реализации алгоритма\|4]])

ASA в 11:42, 1 июля 2022

2022-07-01T11:42:32Z

← Предыдущая версия		Версия от 11:42, 1 июля 2022
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (~~раздел~~ [[#Масштабируемость алгоритма и его реализации\|3]])		Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (разделы [[#Масштабируемость алгоритма и его реализации\|3]], [[#Динамические характеристики и эффективность реализации алгоритма\|4]])

	= Ссылки =		= Ссылки =

ASA в 09:32, 1 июля 2022

2022-07-01T09:32:17Z

← Предыдущая версия		Версия от 09:32, 1 июля 2022
Строка 31:		Строка 31:

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

			Все результаты получены на суперкомпьютере "ГрафИТ!". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор Gnu 4.4.7.
			На рисунках показана эффективность реализации алгоритма Кули-Тьюки на 64 процессах.

			[[file:Cooley-Tukey CPU USER.png\|thumb\|center\|700px\|Рисунок 3. График загрузки CPU при выполнении алгоритма Кули-Тьюки]]

			На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 20%. Это указывает на существенную недозагруженность вычислениями процессора.

			[[file:Cooley-Tukey CPU FLOPS.png\|thumb\|center\|700px\|Рисунок 4. График операций с плавающей точкой в секунду при выполнении алгоритма Кули-Тьюки]]

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

			На графике кэш-промахов первого уровня видно, что число промахов достаточно большое для нескольких ядер и находится на уровне 25 млн/сек. В среднем по всем узлам значения значительно ниже. Это указывает на неравномерное распределение вычислений.
			[[file:Cooley-Tukey L3.png\|thumb\|center\|700px\|Рисунок 6. График кэш-промахов L3 в секунду при работе алгоритма Кули-Тьюки]]

			На графике кэш-промахов третьего уровня видно, что число промахов все еще достаточно большое для небольшого числа процессов и находится на уровне 1,5 млн/сек, однако в среднем по всем узлам значения низкие.
			[[file:Cooley-Tukey MEM LOAD.png\|thumb\|center\|700px\|Рисунок 7. График количества чтений из оперативной памяти при работе алгоритма Кули-Тьюки]]

			На графике чтений из памяти на наблюдается неравномерная активность чтения из памяти процессами: несколько читают очень активно, остальные используют значительно менее эффективно. Однако активность тех нескольких процессов чтения из памяти достаточно высока, что в сочетании с показаниями достаточно высокого уровня кэш-промахов указывает на достаточно большой процент промахов из кэш в оперативную память.
			[[file:Cooley-Tukey MEM STORE.png\|thumb\|center\|700px\|Рисунок 8. График количества записей в оперативную память при работе алгоритма Кули-Тьюки]]

			На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения и указывает на низкую эффективность данной реализации.
			[[file:Cooley-Tukey INF DATA.png\|thumb\|center\|700px\|Рисунок 9. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Кули-Тьюки]]

			На графике скорости передачи данных по сети Infiniband наблюдается достаточно низкая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются небольшими порциями данных.
			[[file:Cooley-Tukey INF PCKTS.png\|thumb\|center\|700px\|Рисунок 10. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Кули-Тьюки]]

			На графике скорости передачи данных в пакетах в секунду наблюдается очень высокая интенсивность передачи данных выраженная в пакетах в секунду. Это говорит о том, что, вероятно, процессы обмениваются сообщениями очень низкой длины, но очень интенсивно. Так же наблюдается меньший дизбаланс между процессами чем наблюдаемый в графиках использования памяти и вычислений. Это указывает на то, что при поступлении необходимых данных часть процессов начинает интенсивные вычисления, хотя другие продолжают простаивать.
			[[file:Cooley-Tukey LOADAVG.png\|thumb\|center\|700px\|Рисунок 17. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Кули-Тьюки]]
			На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 3. Это свидетельствует о стабильной работе программы с загруженной только частью вычислительных узлов. Это указывает на очень нерациональную и статичную загрузку аппаратных ресурсов процессами. И показывает низкую эффективность выполняемой реализации.
			В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала неэффективно, но стабильно. Использование памяти и коммуникационной среды достаточно интенсивное, при этом объемы передаваемых данных являются крайне малыми. Это указывает на необходимость использования оптимизаций алгоритмической части программы.
			Низкая эффективность связана судя по всему с недостаточным объемом вычислений на каждом процессе, интенсивными обменами малой длины сообщений. Это приводит к постоянному ожиданию процессами данных для вычислений и простою даже в рамках одного вычислительного узла.

	= Результаты прогонов =		= Результаты прогонов =

ASA в 09:29, 1 июля 2022

2022-07-01T09:29:52Z

← Предыдущая версия		Версия от 09:29, 1 июля 2022
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|~~1.2~~]])		Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|3]])

	= Ссылки =		= Ссылки =

ASA в 09:20, 1 июля 2022

2022-07-01T09:20:25Z

ASA в 09:16, 1 июля 2022

2022-07-01T09:16:19Z

ASA в 09:15, 1 июля 2022

2022-07-01T09:15:00Z

← Предыдущая версия		Версия от 09:15, 1 июля 2022
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|2.1]])		Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|1.2]])

	== Программная реализация алгоритма: Cooley-Tukey, scalability ==		== Программная реализация алгоритма: Cooley-Tukey, scalability ==

ASA: Новая страница: «Основные авторы описания: А.М.Теплов (раздел #Масштабируемость алгоритм...»

2022-07-01T09:14:07Z

Новая страница: «Основные авторы описания: А.М.Теплов (раздел #Масштабируемость алгоритм...»

Новая страница

Основные авторы описания: [[Участник:Teplov|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации|2.1]])

== Программная реализация алгоритма: Cooley-Tukey, scalability ==

Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].

=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====

=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
Набор и границы значений изменяемых [[Глоссарий#Параметры запуска|параметров запуска]] реализации алгоритма:

* число процессоров [4, 8 : 64] с шагом 8;
* размер вектора [128 : 32768] с шагом равным степени двойки.

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

* минимальная эффективность реализации 0.000000002% (1.85994069951e-09%);
* максимальная эффективность реализации 0.00002% (2.07351573426e-05%).

На следующих рисунках приведены графики [[Глоссарий#Производительность|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

[[file:Cooley perf.png|thumb|center|700px|Рисунок 1. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера области.]]
[[file:Cooley eff.png|thumb|center|700px|Рисунок 2. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.

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

[[Категория:Статьи в работе]]

[[En:Cooley-Tukey, scalability]]

← Предыдущая версия		Версия от 09:20, 1 июля 2022
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|1.2]])		Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|1.2]])

	= ~~Программная реализация алгоритма: Cooley-Tukey, scalability~~ =		= Ссылки =

	Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].		Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].

	== Локальность данных и вычислений ==		= Локальность данных и вычислений =
	=== Локальность реализации алгоритма ===		== Локальность реализации алгоритма ==
	==== Структура обращений в память и качественная оценка локальности ====		=== Структура обращений в память и качественная оценка локальности ===
	==== Количественная оценка локальности ====		=== Количественная оценка локальности ===

	== Масштабируемость алгоритма и его реализации ==		= Масштабируемость алгоритма и его реализации =
	=== Масштабируемость алгоритма ===		== Масштабируемость алгоритма ==
	=== Масштабируемость реализации алгоритма ===		== Масштабируемость реализации алгоритма ==
	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Строка 30:		Строка 30:
	Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.		Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.

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

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[En:Cooley-Tukey, scalability]]		[[En:Cooley-Tukey, scalability]]

← Предыдущая версия		Версия от 09:16, 1 июля 2022
Строка 1:		Строка 1:
	Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|1.2]])		Основные авторы описания: [[Участник:Teplov\|А.М.Теплов]] (раздел [[#Масштабируемость алгоритма и его реализации\|1.2]])

	== Программная реализация алгоритма: Cooley-Tukey, scalability ==		= Программная реализация алгоритма: Cooley-Tukey, scalability =

	Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].		Исследованная [https://gitlab.srcc.msu.ru/alex-teplov/Scalability/blob/master/Cooley-Tukey/fft.c параллельная реализация алгоритма].

	=== Локальность данных и вычислений ===		== Локальность данных и вычислений ==
	==== Локальность реализации алгоритма ====		=== Локальность реализации алгоритма ===
	===== Структура обращений в память и качественная оценка локальности =====		==== Структура обращений в память и качественная оценка локальности ====
	===== Количественная оценка локальности =====		==== Количественная оценка локальности ====

	=== Масштабируемость алгоритма и его реализации ===		== Масштабируемость алгоритма и его реализации ==
	==== Масштабируемость алгоритма ====		=== Масштабируемость алгоритма ===
	==== Масштабируемость реализации алгоритма ====		=== Масштабируемость реализации алгоритма ===
	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Строка 30:		Строка 30:
	Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.		Алгоритм в силу своих особенностей имеет крайне низкую эффективность параллельного выполнения, связанную с крайне малым объемом вычислений на каждый процесс. Из-за этого накладные расходы на организацию параллельного выполнения становятся доминирующими при выполнении алгоритма.

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

	[[Категория:Статьи в работе]]		[[Категория:Статьи в работе]]

	[[En:Cooley-Tukey, scalability]]		[[En:Cooley-Tukey, scalability]]