Участник:Alexander34396/Обобщенный метод минимальных невязок - История изменений

Kpetrov: /* Свойства алгоритма */

2016-12-19T08:09:32Z

Свойства алгоритма

← Предыдущая версия		Версия от 08:09, 19 декабря 2016
Строка 201:		Строка 201:
	Если используется неперезапускаемый метод, GMRES будет сходиться за не более <math> n </math> шагов. Но это не имеет практического применения, когда <math> n </math> велико. Кроме того, требования к памяти и вычислениям при отсутствии перезапусков являются очень высокими. Важнейшим элементом для успешного применения <math> GMRES(m)</math> являются перезапуски; то есть выбор <math> m </math>. Существуют примеры, для которых метод застаивается и сходимость есть только на <math>m</math>-м шаге. Для таких систем, любой выбор <math> m </math> меньше, чем <math> n </math> - не сходится.		Если используется неперезапускаемый метод, GMRES будет сходиться за не более <math> n </math> шагов. Но это не имеет практического применения, когда <math> n </math> велико. Кроме того, требования к памяти и вычислениям при отсутствии перезапусков являются очень высокими. Важнейшим элементом для успешного применения <math> GMRES(m)</math> являются перезапуски; то есть выбор <math> m </math>. Существуют примеры, для которых метод застаивается и сходимость есть только на <math>m</math>-м шаге. Для таких систем, любой выбор <math> m </math> меньше, чем <math> n </math> - не сходится.

	Основным недостатком GMRES является то, что объемы работ и ресурсы памяти, требуемые для итерации, линейно возрастают с увеличением числа итераций. Если не удалось получить чрезвычайно быструю сходимость - затраты будут очень высокими. Основной способ преодолеть это ограничение - это перезапуск итерации. После выбранного числа итераций <math> m </math> накопленные данные будут очищены и промежуточные результаты используются в качестве входных данных для последующих итераций. Эта процедура повторяется до тех пор, пока сходимость не будет достигнута. Трудность заключается в выборе подходящего значения <math> m </math>. Если <math> m </math> слишком мало, <math>GMRES(m)</math> может быть медленно сходиться, или не сойтись совсем. Значение <math> m </math>, большее, чем это необходимо, включает в себя чрезмерную ~~работы~~ и использует больше памяти. К сожалению, нет определенных правил, регулирующих выбор <math> m </math>; выбирая , когда делать перезапуск - это вопрос опыта.		Основным недостатком GMRES является то, что объемы работ и ресурсы памяти, требуемые для итерации, линейно возрастают с увеличением числа итераций. Если не удалось получить чрезвычайно быструю сходимость - затраты будут очень высокими. Основной способ преодолеть это ограничение - это перезапуск итерации. После выбранного числа итераций <math> m </math> накопленные данные будут очищены и промежуточные результаты используются в качестве входных данных для последующих итераций. Эта процедура повторяется до тех пор, пока сходимость не будет достигнута. Трудность заключается в выборе подходящего значения <math> m </math>. Если <math> m </math> слишком мало, <math>GMRES(m)</math> может быть медленно сходиться, или не сойтись совсем. Значение <math> m </math>, большее, чем это необходимо, включает в себя чрезмерную работу и использует больше памяти. К сожалению, нет определенных правил, регулирующих выбор <math> m </math>; выбирая , когда делать перезапуск - это вопрос опыта.

	= Программная реализация алгоритма =		= Программная реализация алгоритма =

Kpetrov: /* Ресурс параллелизма алгоритма */

2016-12-19T07:35:24Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 07:35, 19 декабря 2016
Строка 168:		Строка 168:
	В ходе анализа перезапускаемого метода обобщенных минимальных невязок был выявлен ряд подзадач, выполняющихся неоднократно: умножение матрицы на вектор, вычисление скалярного произведения векторов, нахождение нормы вектора, нормирование вектора, нахождение взвешенной суммы векторов. Наиболее трудоемкой среди перечисленных операций является умножение матрицы на вектор.		В ходе анализа перезапускаемого метода обобщенных минимальных невязок был выявлен ряд подзадач, выполняющихся неоднократно: умножение матрицы на вектор, вычисление скалярного произведения векторов, нахождение нормы вектора, нормирование вектора, нахождение взвешенной суммы векторов. Наиболее трудоемкой среди перечисленных операций является умножение матрицы на вектор.

	Выполнение перечисленных операций занимает большую часть времени работы алгоритма GMRES. Поэтому ~~при увеличении эффективности~~ использования ~~вычислительных ресурсов и~~ ресурсов памяти вычислительной машины ~~при выполнении этих операций повышается эффективность~~ метода в целом~~. Достигается это применением при выполнении перечисленных операций аппарата параллельных вычислений~~.		Выполнение перечисленных операций занимает большую часть времени работы алгоритма GMRES. Поэтому здесь применяется аппарат параллельных вычислений для более эффективного использования ресурсов памяти вычислительной машины и для повышения эффективности метода в целом.

	При выполнении параллельного алгоритма решения систем линейных алгебраических уравнений необходимо распределить входные данные наиболее рациональным способом. Матрица коэффициентов разбивается на непрерывные горизонтальные полосы. Распределение вектора правой части и начального приближения выполнено по принципу дублирования, т.е. все элементы векторов скопированы на все процессоры. Для рассматриваемой задачи решения СЛАУ такой подход распределения допустим, т.к. векторы содержат столько же элементов, сколько и одна строка или один столбец матрицы коэффициентов.		При выполнении параллельного алгоритма решения систем линейных алгебраических уравнений необходимо распределить входные данные наиболее рациональным способом. Матрица коэффициентов разбивается на непрерывные горизонтальные полосы. Распределение вектора правой части и начального приближения выполнено по принципу дублирования, т.е. все элементы векторов скопированы на все процессоры. Для рассматриваемой задачи решения СЛАУ такой подход распределения допустим, т.к. векторы содержат столько же элементов, сколько и одна строка или один столбец матрицы коэффициентов.
Строка 174:		Строка 174:
	Подзадачи можно разделить на 2 группы: операции между матрицей и вектором (например, умножение матрицы на вектор) и операции между двумя векторами (например, скалярное умножение). Подзадачи умножения константы на вектор и определение нормы вектора можно относить ко второй группе, так как их трудоемкость одного порядка.		Подзадачи можно разделить на 2 группы: операции между матрицей и вектором (например, умножение матрицы на вектор) и операции между двумя векторами (например, скалярное умножение). Подзадачи умножения константы на вектор и определение нормы вектора можно относить ко второй группе, так как их трудоемкость одного порядка.

	Результатом выполнения рассматриваемых операций является, вектор, части которого расположены на участвовавших в вычислениях процессорах. Для объединения результатов расчета и получения полного вектора на каждом процессоре вычислительной системы необходимо выполнить операцию сбора данных.		Результатом выполнения рассматриваемых операций является вектор, части которого расположены на участвовавших в вычислениях процессорах. Для объединения результатов расчета и получения полного вектора на каждом процессоре вычислительной системы необходимо выполнить операцию сбора данных.

	== Входные и выходные данные алгоритма ==		== Входные и выходные данные алгоритма ==

Alexander34396 в 12:20, 4 декабря 2016

2016-12-04T12:20:19Z

← Предыдущая версия		Версия от 12:20, 4 декабря 2016
Строка 110:		Строка 110:
	* Вычисление скалярного произведения векторов;		* Вычисление скалярного произведения векторов;
	* Вычисление Евклидовой нормы вектора;		* Вычисление Евклидовой нормы вектора;
	* Умножение ~~вектора на скаляр;~~		* Умножение вектора на скаляр.
	* Деление вектора на скаляр.

	== Схема реализации последовательного алгоритма ==		== Схема реализации последовательного алгоритма ==

Evgeny Mortikov в 02:47, 2 декабря 2016

2016-12-02T02:47:53Z

← Предыдущая версия		Версия от 02:47, 2 декабря 2016
Строка 1:		Строка 1:
	~~{{Assignment\|Dan}}~~

	Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).		Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).

ASA в 07:46, 1 декабря 2016

2016-12-01T07:46:08Z

← Предыдущая версия		Версия от 07:46, 1 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|Dan}}		{{Assignment\|Dan}}
	~~{{Assignment}}~~

	Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).		Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).

Alexander34396 в 18:20, 30 ноября 2016

2016-11-30T18:20:17Z

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

	Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).		Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).

Dan в 16:10, 30 ноября 2016

2016-11-30T16:10:08Z

← Предыдущая версия		Версия от 16:10, 30 ноября 2016
Строка 1:		Строка 1:
			{{Assignment\|Dan}}

	Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).		Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).

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

2016-11-30T15:34:56Z

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

← Предыдущая версия		Версия от 15:34, 30 ноября 2016
Строка 213:		Строка 213:
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==

	В статье <ref> M. Sosonkina, Donald C. S. Allison, Layne T. Watson: Scalability analysis of parallel GMRES implementations </ref> анализируется параллельная реализация <math>GMRES(k)</math> на Intel Paragon, IBM SP2 и Cray T3E.
	Системы Intel Paragon и IBM SP2 не имеют двухуровневого кэша, что значительно сказывается на времени работы из-за больших потерь скорости и частых обращений к памяти.
	В Cray T3E каждый процессор соединен с 8-килобайтовым кэшем данных и 96-килобайтовым двухуровневым кэшем данных. Также имеется дополнительный кэш объемом 4 мегабайта. Это достаточная емкость кэш-памяти для хранения всех данных с плавающей точкой с высоким коэффициентом попаданий кэша.

	Ниже представлены графики экспериментальных результатов, где штриховыми линиями указывается теоретическая связь между коэффициентом масштабируемости <~~math~~>K</~~math~~> и ~~числом процессоров~~ <~~math~~>p</~~math~~> ~~для фиксированного значения эффективности~~. ~~Сплошная линия является аппроксимацией экспериментальных~~ данных ~~методом наименьших квадратов. На всех графиках вертикальная ось представляет~~ <~~math~~>K</~~math>, а горизонтальная ось~~ - ~~<math>p~~</~~math~~>.		Масштабируемость рассматривалась в работах <ref>https://arxiv.org/pdf/1606.08740.pdf</ref> и <ref>https://smartech.gatech.edu/bitstream/handle/1853/55635/PRATAPA-DISSERTATION-2016.pdf</ref>.
			Для исследования масштабируемости была использована параллельная реализация с использованием объекта KSP(решатель СЛАУ) бибилиотеки PETSc(содержащей структуры, типы данных и подпрограммы для параллельной реализации методов на подпространствах Крылова), найденная на GitHub <ref>https://github.com/erdc-cm/petsc-dev/tree/master/src/ksp/ksp/impls/gmres</ref>.

			Вычисления проводились на вычислительном кластере, состоящем из 16 узлов, со следующей конфигурацией:
			Altus 1804i Server - 4P Interlagos Node, Quad AMD Opteron 6276, 16C,
			2.3 GHz, 128GB, DDR3-1333 ECC, 80GB SSD, MLC, 2.5" HCA, Mellanox ConnectX 2, 1-port QSFP, QDR, memfree, CentOS, Version 5.

	~~[[File:Intel paragon.JPG\|thumb\|center\|800px\|'''Рис~~. 2~~''' Intel Paragon]]~~		На рис. 2 представлен график сильной масштабируемости.
	~~[[File:Ibm sp2.JPG\|thumb\|center\|800px\|'''Рис. 3''' IBM SP2]]~~
	~~[[File:Cray t3e.JPG\|thumb\|center\|800px\|'''Рис~~. ~~4''' Cray T3E]]~~

			[[File:scaling.JPG\|thumb\|center\|500px\|'''Рис. 2''' Зависимость производительности от числа процессоров (запуск производился на 1, 8, 27, 64, 216, 512, 1000 процессорах)]]
	~~Теоретические и экспериментальные результаты показывают~~, ~~что параллельные реализации <math>GMRES(k~~)~~</math> являются достаточно масштабируемыми.~~

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

Alexander34396: /* Минимизация функционала невязки */

2016-11-17T17:03:12Z

Минимизация функционала невязки

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

	Невязка исходной системы имеет вид:		Невязка исходной системы имеет вид:
	: <math> r_m = b - A(x_0 + z_m) = r_0 - AV_my_m = \beta v_1 - V_{m+1}H_{m+1k}y_m</math>, где <math> \beta = \\|r_0\\|_2</math>.		: <math> r_m = b - A(x_0 + z_m) = r_0 - AV_my_m = \beta v_1 - V_{m+1}H_{m+1m}y_m</math>, где <math> \beta = \\|r_0\\|_2</math>.

	C учетом того, что матрица <math> V_{k+1} </math> составлена из ортонормированных векторов:		C учетом того, что матрица <math> V_{k+1} </math> составлена из ортонормированных векторов:

Dan в 11:25, 17 ноября 2016

2016-11-17T11:25:26Z

← Предыдущая версия		Версия от 11:25, 17 ноября 2016
Строка 1:		Строка 1:
	~~{{Assignment\|Dan}}~~
	Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).		Основные авторы описания: [[#Участник:Alexander34396\|А.А.Ульянов]] (разделы [[#Общее описание алгоритма\|1.1]], [[#Математическое описание алгоритма\|1.2]], [[#Вычислительное ядро алгоритма\|1.3]], [[#Макроструктура алгоритма\|1.4]], [[#Схема реализации последовательного алгоритма\|1.5]], [[#Последовательная сложность алгоритма\|1.6]], [[#Входные и выходные данные алгоритма\|1.9]], [[#Существующие реализации алгоритма\|2.7]]), [[#Участник:Kpetrov\|К.Петров]] (разделы [[#Информационный граф\|1.7]], [[#Ресурс параллелизма алгоритма\|1.8]], [[#Свойства алгоритма\|1.10]], [[#Масштабируемость алгоритма и его реализации\|2.4]]).