Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов - История изменений

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

2025-12-08T20:15:16Z

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

← Предыдущая версия		Версия от 20:15, 8 декабря 2025
Строка 12:		Строка 12:


	[[Файл:Cg time surface new.png\|~~700px~~\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg time surface new.png\|thumb\|center\|800px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

	На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях		На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
Строка 18:		Строка 18:


	[[Файл:Cg eff surface new.png\|700px\|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg eff surface new.png\|thumb\|center\|700px\|Рис.2 Эффективность распараллеливания МСГ E(N,P) от числа процессов P и размера матрицы N.]]

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

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

2025-12-08T20:09:46Z

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

← Предыдущая версия		Версия от 20:09, 8 декабря 2025
Строка 7:		Строка 7:

	На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.		На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
	По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 ~~время уменьшается~~ не ~~так эффективно, а~~ начиная с <math>P = 48</math> (в случае <math>N=5000</math>) время ~~работы алгоритма начинает возрастать~~. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.		По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 эффективность масштабирования постепенно снижается:ускорение остаётся заметным, но уже не таким выраженным. Для большого числа процессов (начиная с <math>P = 48</math> в случае <math>N=5000</math>) время выполнения перестаёт уменьшаться и даже слегка возрастает. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.

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

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

2025-12-08T20:01:35Z

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

← Предыдущая версия		Версия от 20:01, 8 декабря 2025
Строка 13:		Строка 13:

	На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях		На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
	P в сравнении с задачей ~~меньшего~~ размерности.		P в сравнении с задачей меньшей размерности.

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

2025-12-08T20:00:32Z

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

← Предыдущая версия		Версия от 20:00, 8 декабря 2025
Строка 12:		Строка 12:
	[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

	На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. ~~Эффективность~~ распараллеливания для <math>N=2000</math> ~~снижается медленнее~~, ~~чем~~ для <math>N=5000</math>. Это ~~объясняется меньшим объемом вычислений на процесс~~ и ~~более ранним влиянием~~ задержек на ~~коммуникацию~~.		На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для <math>N=2000</math> эффективность падает относительно медленно, тогда как для <math>N=5000</math> спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях
			P в сравнении с задачей меньшего размерности.

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

2025-12-08T19:45:48Z

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

← Предыдущая версия		Версия от 19:45, 8 декабря 2025
Строка 12:		Строка 12:
	[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

	На рис.2 показана эффективность <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. Эффективность для <math>N=2000</math> снижается медленнее, чем для <math>N=5000</math>. Это объясняется меньшим объемом вычислений на процесс и более ранним влиянием задержек на коммуникацию.		На рис.2 показана [[Глоссарий#Эффективность распараллеливания\|эффективность распараллеливания]] <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. Эффективность распараллеливания для <math>N=2000</math> снижается медленнее, чем для <math>N=5000</math>. Это объясняется меньшим объемом вычислений на процесс и более ранним влиянием задержек на коммуникацию.

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

2025-12-08T16:50:29Z

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

← Предыдущая версия		Версия от 16:50, 8 декабря 2025
Строка 2:		Строка 2:
	== Локальность данных и вычислений ==		== Локальность данных и вычислений ==
	== Масштабируемость алгоритма и его реализации ==		== Масштабируемость алгоритма и его реализации ==
	Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}<.</math>		Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}.</math>

	Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.		Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.

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

2025-12-08T16:50:05Z

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

← Предыдущая версия		Версия от 16:50, 8 декабря 2025
Строка 7:		Строка 7:

	На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.		На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
	По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а ~~при~~ <math>P = 48 ~~и P = 56~~</math> (в случае <math>N=5000</math>) время начинает возрастать. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.		По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а начиная с <math>P = 48</math> (в случае <math>N=5000</math>) время работы алгоритма начинает возрастать. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.

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

2025-12-08T16:48:26Z

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

← Предыдущая версия		Версия от 16:48, 8 декабря 2025
Строка 7:		Строка 7:

	На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.		На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
	По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а при <math>P = 48</math> время начинает возрастать ~~из-за роста коммуникационных затрат~~ и ~~стоимости глобальных редукций~~.		По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а при <math>P = 48 и P = 56</math> (в случае <math>N=5000</math>) время начинает возрастать. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.


	[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

			На рис.2 показана эффективность <math>E(N,P)</math> в зависимости от числа процессов и размеров матрицы. Эффективность для <math>N=2000</math> снижается медленнее, чем для <math>N=5000</math>. Это объясняется меньшим объемом вычислений на процесс и более ранним влиянием задержек на коммуникацию.


	[[Файл:Cg eff surface new.png\|700px\|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg eff surface new.png\|700px\|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]

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

2025-12-08T16:06:33Z

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

← Предыдущая версия		Версия от 16:06, 8 декабря 2025
Строка 7:		Строка 7:

	На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.		На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
	По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а при <math>P = 56</math> время начинает возрастать из-за роста коммуникационных затрат и стоимости глобальных редукций.		По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а при <math>P = 48</math> время начинает возрастать из-за роста коммуникационных затрат и стоимости глобальных редукций.
	[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]		[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

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

2025-12-08T15:53:02Z

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

← Предыдущая версия		Версия от 15:53, 8 декабря 2025
Строка 5:		Строка 5:

	Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.		Число процессов изменялось в диапазоне <math>P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\}</math>.

	На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.		На рис.1 представлен график зависимости времени работы алгоритма <math>T(N,P)</math> от числа процессов и размеров матрицы.
			По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 время уменьшается не так эффективно, а при <math>P = 56</math> время начинает возрастать из-за роста коммуникационных затрат и стоимости глобальных редукций.
			[[Файл:Cg time surface new.png\|700px\|Рис.1 Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]

	~~[[Файл:Cg time surface new.png\|700px\|Рис. 1. Зависимость времени работы МСГ T(N,P) от числа процессов P и размера матрицы N.]]~~		[[Файл:Cg eff surface new.png\|700px\|Рис.2 Эффективность МСГ E(N,P) от числа процессов P и размера матрицы N.]]

	[[Файл:Cg eff surface new.png\|700px\|Рис. 2~~. Зависимость времени работы~~ МСГ T(N,P) от числа процессов P и размера матрицы N.]]

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