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

Frolov в 09:05, 20 декабря 2016

2016-12-20T09:05:25Z

← Предыдущая версия		Версия от 09:05, 20 декабря 2016
Строка 1:		Строка 1:
	{{Assignment\|ASA}}		{{Assignment\|ASA\|Frolov}}

	{{algorithm		{{algorithm

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

2016-11-21T11:22:14Z

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

	{{algorithm		{{algorithm

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

2016-11-19T22:37:18Z

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

← Предыдущая версия		Версия от 22:37, 19 ноября 2016
Строка 276:		Строка 276:
	\|		\|
	module add slurm		module add slurm

	module add openmpi/1.8.4-gcc		module add openmpi/1.8.4-gcc

	module add gcc/5.2.0		module add gcc/5.2.0

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

2016-11-19T22:37:07Z

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

← Предыдущая версия		Версия от 22:37, 19 ноября 2016
Строка 263:		Строка 263:
	В рамках статьи была написана своя параллельная реализация процесса ортогонализации Грама-Шмидта с использованием OpenMPI. Реализация вместе с данными и вспомогательными скриптами доступна в репозитории [https://github.com/zodinyac/GramSchmidt GramSchmidt].		В рамках статьи была написана своя параллельная реализация процесса ортогонализации Грама-Шмидта с использованием OpenMPI. Реализация вместе с данными и вспомогательными скриптами доступна в репозитории [https://github.com/zodinyac/GramSchmidt GramSchmidt].

	Основная идея реализации: ~~Нулевой~~ вычислительный узел является управляющим, остальные ― подчиненными. Подчиненные узлы запрашивают "задание" у управляющего узла ― номер вектора, который требуется расчитать. Когда подчиненный узел заканчивает расчет, то пересылает готовый вектор на управляющий узел и запрашивает следующее задание. Если заданий больше нет, то подчиненный узел заканчивает свою работу. Каждый узел имеет список уже готовых векторов. Если при расчете требуется вектор, которого нет в списке, то он запрашивается у управляющего узла.		'''Основная идея реализации''': нулевой вычислительный узел является управляющим, остальные ― подчиненными. Подчиненные узлы запрашивают "задание" у управляющего узла ― номер вектора, который требуется расчитать. Когда подчиненный узел заканчивает расчет, то пересылает готовый вектор на управляющий узел и запрашивает следующее задание. Если заданий больше нет, то подчиненный узел заканчивает свою работу. Каждый узел имеет список уже готовых векторов. Если при расчете требуется вектор, которого нет в списке, то он запрашивается у управляющего узла.

	Испытания реализованного алгоритма проводились на [http://parallel.ru/cluster/lomonosov.html суперкомпьютере "Ломоносов"] Суперкомпьютерного комплекса Московского университета со следующими значениями параметров:		Испытания реализованного алгоритма проводились на [http://parallel.ru/cluster/lomonosov.html суперкомпьютере "Ломоносов"] Суперкомпьютерного комплекса Московского университета со следующими значениями параметров:
	* размер матрицы по одному измерению: 100, 500 и далее с шагом 500 до 10000 элементов,		* размер матрицы по одному измерению: 100, 500 и далее с шагом 500 до 10000 элементов,
	* число процессов: 1, 2, 4, 8 и далее с шагом 8 до 128. Тестирование с использованием 1, 2, 4 и 8 процессов не использовалось для данных, где размер превышал 5000.		* число процессов: 1, 2, 4, 8 и далее с шагом 8 до 128. Тестирование с использованием 1, 2, 4 и 8 процессов не использовалось для данных, где размер превышал 5000.

			'''Основная идея тестирования''': для тестирования реализованного алгоритма были написаны генератор единичной матрицы и программа, проверяющая, что в поданном файле содержится корректная единичная матрица. Также для тестирования на "Ломоносове" был написан скрипт постановки задачи в очередь, поддерживающий в ней всегда три задачи с различными входными данными, то есть после завершения тестирования на одном наборе данных скрипт сразу же ставил в очередь очередной набор.

			{\| class="wikitable mw-collapsible mw-collapsed"
			! Использованные модули и компиляторы
			\|-
			\|
			module add slurm
			module add openmpi/1.8.4-gcc
			module add gcc/5.2.0

			Для самой программы был использован компилятор mpicxx, для генератора и тестера ― g++.
			\|}

	На следующем рисунке приведен график времени работы алгоритма в зависимости от числа процессов и размерности матриц.		На следующем рисунке приведен график времени работы алгоритма в зависимости от числа процессов и размерности матриц.

BDA: /* Свойства и структура алгоритма */

2016-11-19T14:44:58Z

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

← Предыдущая версия		Версия от 14:44, 19 ноября 2016
Строка 17:		Строка 17:
	Ортогонализация ― алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства V ортогональной системы ненулевых векторов, порождающих то же самое подпространство в V.		Ортогонализация ― алгоритм построения для данной линейно независимой системы векторов евклидова или эрмитова пространства V ортогональной системы ненулевых векторов, порождающих то же самое подпространство в V.

	Ортогонализация Грама–Шмидта<ref>Канатников А.Н., Крищенко А.П. "Линейная алгебра." ― 3-е изд., стер. ― М.: Изд-во МГТУ им. Н.Э. Баумана, 2002</ref> (процесс Грама–Шмидта) ― наиболее известный алгоритм ортогонализации. Назван в честь Йоргена Педерсена Грама<ref>O'Connor, John J.; Robertson, Edmund F.~~, "~~Jørgen Pedersen Gram", MacTutor History of Mathematics archive, University of St Andrews.</ref> и Эрхарда Шмидта<ref>O'Connor, John J.; Robertson, Edmund F.~~, "~~Erhard Schmidt", MacTutor History of Mathematics archive, University of St Andrews.</ref>, однако ранее уже появлялся в работах Лапласа и Коши. Является частным случаем разложения Ивасавы, так как может быть представлен как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами.		Ортогонализация Грама–Шмидта<ref>Канатников А.Н., Крищенко А.П. Линейная алгебра. ― 3-е изд., стер. ― М.: Изд-во МГТУ им. Н.Э. Баумана, 2002</ref> (процесс Грама–Шмидта) ― наиболее известный алгоритм ортогонализации. Назван в честь Йоргена Педерсена Грама<ref>O'Connor, John J., Robertson, Edmund F. Jørgen Pedersen Gram ― MacTutor History of Mathematics archive, University of St Andrews.</ref> и Эрхарда Шмидта<ref>O'Connor, John J., Robertson, Edmund F. Erhard Schmidt ― MacTutor History of Mathematics archive, University of St Andrews.</ref>, однако ранее уже появлялся в работах Лапласа и Коши. Является частным случаем разложения Ивасавы, так как может быть представлен как разложение невырожденной квадратной матрицы в произведение ортогональной (или унитарной матрицы в случае эрмитова пространства) и верхнетреугольной матрицы с положительными диагональными элементами.

	Рассматриваемый алгоритм применяется для борьбы с помехами в адаптивной системе селекции движущихся целей<ref>Орешкин Б.Н., Бакулев П.А. "Быстрая процедура ортогонализации ~~Грамма–Шмидта~~ и ее применение для борьбы с помехами в адаптивной системе селекции движущихся целей" ― Радиотехника / №12 за 2007 г.</ref>, в протоколах безопасности<ref>Пискова А.В., Менщиков А.А., Коробейников А.Г. "Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности" ― Вопросы кибербезопасности №1(14) 2016</ref>, для повышения экономичности алгоритмов оценивания параметров моделей объектов управления<ref>Карелин А.Е., Светлаков А.А. "Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления" ― Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 8. — [С. 15-19].</ref> и в других областях.		Рассматриваемый алгоритм применяется для борьбы с помехами в адаптивной системе селекции движущихся целей<ref>Орешкин Б.Н., Бакулев П.А. Быстрая процедура ортогонализации Грамма-Шмидта и ее применение для борьбы с помехами в адаптивной системе селекции движущихся целей ― Радиотехника / №12 за 2007 г.</ref>, в протоколах безопасности<ref>Пискова А.В., Менщиков А.А., Коробейников А.Г. Использование ортогонализации Грама-Шмидта в алгоритме приведения базиса решетки для протоколов безопасности ― Вопросы кибербезопасности №1(14) 2016</ref>, для повышения экономичности алгоритмов оценивания параметров моделей объектов управления<ref>Карелин А.Е., Светлаков А.А. Использование ортогонализации Грама-Шмидта для повышения экономичности многоточечных алгоритмов рекуррентного оценивания параметров моделей объектов управления ― Известия Томского политехнического университета [Известия ТПУ]. — 2006. — Т. 309, № 8. — [С. 15-19].</ref> и в других областях.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

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

2016-11-19T13:03:26Z

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

← Предыдущая версия		Версия от 13:03, 19 ноября 2016
Строка 275:		Строка 275:
	На следующем рисунке приведен график эффективности распараллеливания алгоритма в зависимости от числа процессов и размерности матриц.		На следующем рисунке приведен график эффективности распараллеливания алгоритма в зависимости от числа процессов и размерности матриц.
	[[File:Gs-parallel_efficiency.png\|thumb\|center\|720px\|Рисунок 4. График эффективности распараллеливания алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Gs-parallel_efficiency.png\|thumb\|center\|720px\|Рисунок 4. График эффективности распараллеливания алгоритма в зависимости от числа процессоров и размерности матриц.]]
			Минимальная эффективность распараллеливания 0.12%. Максимальная ― 95%.

	{\| class="wikitable"		{\| class="wikitable"

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

2016-11-19T03:05:35Z

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

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

	В рамках статьи была написана своя параллельная реализация процесса ортогонализации Грама-Шмидта с использованием OpenMPI. Реализация вместе с данными и вспомогательными скриптами доступна в репозитории [https://github.com/zodinyac/GramSchmidt GramSchmidt].		В рамках статьи была написана своя параллельная реализация процесса ортогонализации Грама-Шмидта с использованием OpenMPI. Реализация вместе с данными и вспомогательными скриптами доступна в репозитории [https://github.com/zodinyac/GramSchmidt GramSchmidt].

			Основная идея реализации: Нулевой вычислительный узел является управляющим, остальные ― подчиненными. Подчиненные узлы запрашивают "задание" у управляющего узла ― номер вектора, который требуется расчитать. Когда подчиненный узел заканчивает расчет, то пересылает готовый вектор на управляющий узел и запрашивает следующее задание. Если заданий больше нет, то подчиненный узел заканчивает свою работу. Каждый узел имеет список уже готовых векторов. Если при расчете требуется вектор, которого нет в списке, то он запрашивается у управляющего узла.

	Испытания реализованного алгоритма проводились на [http://parallel.ru/cluster/lomonosov.html суперкомпьютере "Ломоносов"] Суперкомпьютерного комплекса Московского университета со следующими значениями параметров:		Испытания реализованного алгоритма проводились на [http://parallel.ru/cluster/lomonosov.html суперкомпьютере "Ломоносов"] Суперкомпьютерного комплекса Московского университета со следующими значениями параметров:

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

2016-11-19T02:49:24Z

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

← Предыдущая версия		Версия от 02:49, 19 ноября 2016
Строка 267:		Строка 267:
	* число процессов: 1, 2, 4, 8 и далее с шагом 8 до 128. Тестирование с использованием 1, 2, 4 и 8 процессов не использовалось для данных, где размер превышал 5000.		* число процессов: 1, 2, 4, 8 и далее с шагом 8 до 128. Тестирование с использованием 1, 2, 4 и 8 процессов не использовалось для данных, где размер превышал 5000.

	На следующем рисунке приведен ~~графики~~ времени работы алгоритма в зависимости от числа процессов и размерности матриц.		На следующем рисунке приведен график времени работы алгоритма в зависимости от числа процессов и размерности матриц.
	[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
			На следующем рисунке приведен график времени работы алгоритма в зависимости от числа процессов и размерности матриц, при этом часть данных с самым долгим временем работы отброшена, чтобы более наглядно продемонстрировать зависимость.
	[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
			На следующем рисунке приведен график эффективности распараллеливания алгоритма в зависимости от числа процессов и размерности матриц.
	[[File:Gs-parallel_efficiency.png\|thumb\|center\|720px\|Рисунок 4. График эффективности распараллеливания алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Gs-parallel_efficiency.png\|thumb\|center\|720px\|Рисунок 4. График эффективности распараллеливания алгоритма в зависимости от числа процессоров и размерности матриц.]]

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

2016-11-19T02:46:54Z

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

← Предыдущая версия		Версия от 02:46, 19 ноября 2016
Строка 270:		Строка 270:
	[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
	[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
			[[File:Gs-parallel_efficiency.png\|thumb\|center\|720px\|Рисунок 4. График эффективности распараллеливания алгоритма в зависимости от числа процессоров и размерности матриц.]]

	{\| class="wikitable"		{\| class="wikitable"

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

2016-11-18T21:14:30Z

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

← Предыдущая версия		Версия от 21:14, 18 ноября 2016
Строка 267:		Строка 267:
	* число процессов: 1, 2, 4, 8 и далее с шагом 8 до 128. Тестирование с использованием 1, 2, 4 и 8 процессов не использовалось для данных, где размер превышал 5000.		* число процессов: 1, 2, 4, 8 и далее с шагом 8 до 128. Тестирование с использованием 1, 2, 4 и 8 процессов не использовалось для данных, где размер превышал 5000.

	На следующем рисунке приведен ~~график~~ времени работы алгоритма в зависимости от числа процессов и размерности матриц.		На следующем рисунке приведен графики времени работы алгоритма в зависимости от числа процессов и размерности матриц.
	[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
			[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]

	{\| class="wikitable"		{\| class="wikitable"

← Предыдущая версия		Версия от 02:46, 19 ноября 2016
Строка 270:		Строка 270:
	[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-1.png\|thumb\|center\|720px\|Рисунок 2. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
	[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]		[[File:Plot3d-gs-belov-bogomolov-2.png\|thumb\|center\|720px\|Рисунок 3. График производительности реализации алгоритма в зависимости от числа процессоров и размерности матриц.]]
			[[File:Gs-parallel_efficiency.png\|thumb\|center\|720px\|Рисунок 4. График эффективности распараллеливания алгоритма в зависимости от числа процессоров и размерности матриц.]]

	{\| class="wikitable"		{\| class="wikitable"