Участница:Larisayaryzheva/Программная реализация метода сопряжённых градиентов: различия между версиями
| (не показано 12 промежуточных версий этой же участницы) | |||
| Строка 2: | Строка 2: | ||
== Локальность данных и вычислений == | == Локальность данных и вычислений == | ||
== Масштабируемость алгоритма и его реализации == | == Масштабируемость алгоритма и его реализации == | ||
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N | Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности <math> N \in \{2000, 5000\}.</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 = 48</math> в случае <math>N=5000</math>) время выполнения перестаёт уменьшаться и даже слегка возрастает. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе. | |||
Реализация демонстрирует хорошую масштабируемость вплоть до десятков процессов, а наблюдаемые ограничения соответствуют теоретическим особенностям параллельного метода сопряжённых градиентов. | |||
[[Файл: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. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях | |||
P в сравнении с задачей меньшей размерности. | |||
[[Файл:Cg eff surface new.png|thumb|Рис. | [[Файл:Cg eff surface new.png|thumb|center|700px|Рис.2 Эффективность распараллеливания МСГ E(N,P) от числа процессов P и размера матрицы N.]] | ||
== Динамические характеристики и эффективность реализации алгоритма == | == Динамические характеристики и эффективность реализации алгоритма == | ||
== Результаты прогонов == | == Результаты прогонов == | ||
Текущая версия от 20:15, 8 декабря 2025
Ссылки
Локальность данных и вычислений
Масштабируемость алгоритма и его реализации
Исследование масштабируемости реализации метода сопряжённых градиентов проводилось на суперкомпьютере "Ломоносов-2" для задач размерности [math]\displaystyle{ N \in \{2000, 5000\}. }[/math]
Число процессов изменялось в диапазоне [math]\displaystyle{ P \in \{ 1, 2, 4, 8, 16, 32, 48, 56\} }[/math].
На рис.1 представлен график зависимости времени работы алгоритма [math]\displaystyle{ T(N,P) }[/math] от числа процессов и размеров матрицы. По результатам при увеличении числа процессов с 1 до 8 время уменьшается почти линейно, что соответствует сильной масштабируемости реализации. При увеличении числа процессов с 16 до 56 эффективность масштабирования постепенно снижается:ускорение остаётся заметным, но уже не таким выраженным. Для большого числа процессов (начиная с [math]\displaystyle{ P = 48 }[/math] в случае [math]\displaystyle{ N=5000 }[/math]) время выполнения перестаёт уменьшаться и даже слегка возрастает. Это связано с тем, что накладные расходы на коммуникации и глобальные редукции начинают преобладать над вычислительной работой на каждом процессе.
Реализация демонстрирует хорошую масштабируемость вплоть до десятков процессов, а наблюдаемые ограничения соответствуют теоретическим особенностям параллельного метода сопряжённых градиентов.
На рис.2 показана эффективность распараллеливания [math]\displaystyle{ E(N,P) }[/math] в зависимости от числа процессов и размеров матрицы. При увеличении числа процессов эффективность распараллеливания для обеих матриц монотонно уменьшается, однако характер этого снижения различается. Для [math]\displaystyle{ N=2000 }[/math] эффективность падает относительно медленно, тогда как для [math]\displaystyle{ N=5000 }[/math] спад происходит заметно быстрее при больших P. Это связано с тем, что для более крупной задачи выполняется больше итераций метода и, соответственно, больше глобальных операций редукции. Накопление задержек на этих коммуникациях приводит к ускоренному снижению эффективности при больших значениях P в сравнении с задачей меньшей размерности.
