Обратная подстановка (вещественный вариант) - История изменений

ASA в 11:33, 18 июля 2022

2022-07-18T11:33:21Z

← Предыдущая версия		Версия от 11:33, 18 июля 2022
Строка 173:		Строка 173:
	При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.		При этом для реализации режима накопления переменная <math>S</math> должна быть двойной точности.

	== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===

	Вариантов параллельной реализации алгоритма не так уж и много, если не использовать то, что оба главных цикла можно развернуть, перейдя, таким образом, к блочной версии. Версии без развёртывания циклов возможны как с полностью параллельными циклами по I:		Вариантов параллельной реализации алгоритма не так уж и много, если не использовать то, что оба главных цикла можно развернуть, перейдя, таким образом, к блочной версии. Версии без развёртывания циклов возможны как с полностью параллельными циклами по I:
Строка 197:		Строка 197:
	Для большинства современных пакетов имеется также блочный вариант алгоритма обратной подстановки, в том числе и тот, граф которого топологически тождествен графу точечного варианта. Из-за того, что количество читаемых данных примерно равно количеству операций, блочность может дать некоторое ускорение работы благодаря лучшему использованию кэшей процессоров. Именно в направлении оптимизации кэширования и следует сосредоточить основные усилия при оптимизации работы программы.		Для большинства современных пакетов имеется также блочный вариант алгоритма обратной подстановки, в том числе и тот, граф которого топологически тождествен графу точечного варианта. Из-за того, что количество читаемых данных примерно равно количеству операций, блочность может дать некоторое ускорение работы благодаря лучшему использованию кэшей процессоров. Именно в направлении оптимизации кэширования и следует сосредоточить основные усилия при оптимизации работы программы.

			=== Результаты прогонов ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

ASA в 11:29, 18 июля 2022

2022-07-18T11:29:59Z

Внесённые изменения

ASA: /* Количественная оценка локальности */

2022-04-28T13:32:26Z

Количественная оценка локальности

← Предыдущая версия		Версия от 13:32, 28 апреля 2022
Строка 213:		Строка 213:
	===== Количественная оценка локальности =====		===== Количественная оценка локальности =====

	Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Voevodin~~/locality/blob/master/benchmarks/gauss_back/gauss_back.h здесь] (функция Kernel2). Условия запуска описаны [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Voevodin~~/locality/blob/master/README.md здесь].		Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/benchmarks/gauss_back/gauss_back.h здесь] (функция Kernel2). Условия запуска описаны [https://gitlab.srcc.msu.ru/vadim/locality/blob/master/README.md здесь].

	Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.		Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.

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

2016-02-16T10:52:08Z

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

← Предыдущая версия		Версия от 10:52, 16 февраля 2016
Строка 270:		Строка 270:

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
			Для проведения экспериментов использовалась реализация алгоритма обратной подстановки. Все результаты получены на суперкомпьютере "Ломоносов". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0.
			На рисунках показана эффективность реализации алгоритма обратной подстановки на 32 процессах.

			[[file:BS CPU USER.png\|thumb\|center\|700px\|Рисунок 9. График загрузки CPU при выполнении алгоритма обратной подстановки]]

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

			[[file:BS FLOPS.png\|thumb\|center\|700px\|Рисунок 10. График операций с плавающей точкой в секунду при выполнении алгоритма обратной подстановки]]

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

			На графике кэш-промахов первого уровня видно, что число промахов не очень большое для нескольких ядер и находится на уровне 3,5 млн/сек в среднем (в пике до 8,5 млн/сек), что указывает на не очень интенсивные вычисления в большей части процессов. Это указывает на неравномерное распределение вычислений и не очень высокую производительность приложения.
			[[file:BS L3.png\|thumb\|center\|700px\|Рисунок 12. График кэш-промахов L3 в секунду при работе алгоритма обратной подстановки]]

			На графике кэш-промахов третьего уровня видно, что число промахов очень немного и находится на уровне 1,2 млн/сек в среднем, однако в пике по всем узлам значения доходят до 3 млн/сек. Соотношение кэш промахов L1\|L3 для процессов с доходит до 3, однако в среднем около 2,5. Это указывает на очень плохую локальность вычислений как у части процессов, так и для всех в среднем, и это является признаком низкой производительности.
			[[file:BS MEM LOAD.png\|thumb\|center\|700px\|Рисунок 13. График количества чтений из оперативной памяти при работе алгоритма обратной подстановки]]

			На графике обращений в память видна достаточно типичная картина для таких приложений. Активность чтения достаточно низкая, что в совокупности с низкими значениями кэш-промахов L3 указывает на хорошую локальность. Хорошая локальность приложения так же указывает на то, что значения около 1 млн/сек для задачи является результатом высокой производительности вычислений, хотя и присутствует неравномерность между процессами.
			[[file:BS MEM STORE.png\|thumb\|center\|700px\|Рисунок 14. График количества записей в оперативную память при работе алгоритма обратной подстановки]]

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

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

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

	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

ASA в 11:15, 10 февраля 2016

2016-02-10T11:15:41Z

← Предыдущая версия		Версия от 11:15, 10 февраля 2016
Строка 288:		Строка 288:
	[[En:Backward substitution]]		[[En:Backward substitution]]

	[[Категория:~~Статьи в работе~~]]		[[Категория:Законченные статьи]]

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

2015-12-25T14:45:57Z

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

← Предыдущая версия		Версия от 14:45, 25 декабря 2015
Строка 264:		Строка 264:
	[[file:BS perf.png\|thumb\|center\|700px\|Рисунок 10. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS perf.png\|thumb\|center\|700px\|Рисунок 10. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

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

	Исследованная [https://code.google.com/p/febretpository/source/browse/parallel_GE/parallel_GE_alessandro.c реализация алгоритма]		Исследованная [https://code.google.com/p/febretpository/source/browse/parallel_GE/parallel_GE_alessandro.c реализация алгоритма]

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

2015-12-25T14:20:33Z

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

← Предыдущая версия		Версия от 14:20, 25 декабря 2015
Строка 265:		Строка 265:
	[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

	Исследованная [~~http~~://~~git~~.~~algowiki-project~~.~~org~~/~~Teplov~~/~~Scalability~~/~~blob~~/~~master~~/~~tridiag~~/~~tridiagonal~~.h реализация алгоритма]		Исследованная [https://code.google.com/p/febretpository/source/browse/parallel_GE/parallel_GE_alessandro.c реализация алгоритма]

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

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

2015-12-25T13:04:31Z

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

← Предыдущая версия		Версия от 13:04, 25 декабря 2015
Строка 264:		Строка 264:
	[[file:BS perf.png\|thumb\|center\|700px\|Рисунок 10. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS perf.png\|thumb\|center\|700px\|Рисунок 10. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

			Исследованная [http://git.algowiki-project.org/Teplov/Scalability/blob/master/tridiag/tridiagonal.h реализация алгоритма]

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

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

2015-12-25T12:21:59Z

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

← Предыдущая версия		Версия от 12:21, 25 декабря 2015
Строка 248:		Строка 248:

	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====
			==== Масштабируемость реализации алгоритма ====
			Проведём исследование масштабируемости параллельной реализации алгоритма согласно [[Scalability methodology\|методике]]. Исследование проводилось на суперкомпьютере "Ломоносов"<ref name="Lom">Воеводин Вл., Жуматий С., Соболев С., Антонов А., Брызгалов П., Никитенко Д., Стефанов К., Воеводин Вад. Практика суперкомпьютера «Ломоносов» // Открытые системы, 2012, N 7, С. 36-39.</ref> [http://parallel.ru/cluster Суперкомпьютерного комплекса Московского университета].
	Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:		Набор и границы значений изменяемых [[Глоссарий#Параметры запуска\|параметров запуска]] реализации алгоритма:

Строка 262:		Строка 264:
	[[file:BS perf.png\|thumb\|center\|700px\|Рисунок 10. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS perf.png\|thumb\|center\|700px\|Рисунок 10. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера матрицы.]]
	[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]		[[file:BS eff.png\|thumb\|center\|700px\|Рисунок 11. Параллельная реализация алгоритма. Изменение эффективности в зависимости от числа процессоров и размера матрицы.]]

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

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

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

2015-12-17T11:00:39Z

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

← Предыдущая версия		Версия от 11:00, 17 декабря 2015
Строка 260:		Строка 260:
	На следующих рисунках приведены графики [[Глоссарий#Производительность\|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.		На следующих рисунках приведены графики [[Глоссарий#Производительность\|производительности]] и эффективности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.

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

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