Участник:OscarFox/Обобщенный прокрустов анализ - История изменений

OscarFox: /* Описание подзадачи (CPA) */

2025-12-21T14:45:34Z

Описание подзадачи (CPA)

← Предыдущая версия		Версия от 14:45, 21 декабря 2025
Строка 123:		Строка 123:
	Далее для нахождения <math>R</math> требуется выполнить сингулярное разложение <math>M: M = U \Sigma V^T</math>.		Далее для нахождения <math>R</math> требуется выполнить сингулярное разложение <math>M: M = U \Sigma V^T</math>.

	Тогда искомая матрица поворота <math>R</math> выражается как <math>R = VU^T</math>.		Тогда искомая матрица поворота <math>R</math> выражается как <math>R = UV^T</math>.

	Если <math>det(R) < 0</math>, то преобразование выполняется с отражением. Чтобы исключить такие случаи, достаточно домножить последний столбец матрицы <math>V</math> на <math>-1</math>. Тогда для полученного <math>R</math> будет выполнено ограничение <math>det(R)=1</math> при сохранении оптимальности.		Если <math>det(R) < 0</math>, то преобразование выполняется с отражением. Чтобы исключить такие случаи, достаточно домножить последний столбец матрицы <math>V</math> на <math>-1</math>. Тогда для полученного <math>R</math> будет выполнено ограничение <math>det(R)=1</math> при сохранении оптимальности.

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

2025-12-11T10:21:11Z

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

← Предыдущая версия		Версия от 10:21, 11 декабря 2025
Строка 365:		Строка 365:
	* Число процессов: [1, 2, 4, 8, 16, 32, 64, 92].		* Число процессов: [1, 2, 4, 8, 16, 32, 64, 92].

	[[Файл:Time scaled.png\|700px\|left\|мини\|Рис.5. График зависимости времени выполнения нескольких алгоритма от объема входных данных и числа процессов (увеличенный масштаб)]]		[[Файл:Time scaled.png\|700px\|left\|мини\|Рис.5. График зависимости времени выполнения нескольких итераций алгоритма от объема входных данных и числа процессов (увеличенный масштаб)]]
	[[Файл:Time gpa corrected.png\|700px\|right\|мини\|Рис.6. График зависимости времени выполнения нескольких алгоритма от объема входных данных и числа процессов]]		[[Файл:Time gpa corrected.png\|700px\|right\|мини\|Рис.6. График зависимости времени выполнения нескольких итераций алгоритма от объема входных данных и числа процессов]]

	Из графиков видно, что при большом объеме входных данных имеется выигрыш по времени выполнения при росте числа процессоров, в то время как при небольших матрицах и небольшом числе форм выделение дополнительных процессоров лишь увеличивает накладные расходы, вследствие чего время выполнения растет. Также очевидна закономерность, при которой время выполнения в среднем растет с увеличением объема входных данных при неизменном числе процессоров. В условиях исследуемого алгоритма, конфигурации вычислительных узлов суперкомпьютера (многоядерные процессоры с подержкой гипертрединга) и реализации (используется библиотека Eigen<ref>''Eigen C++ library'' // https://libeigen.gitlab.io/</ref> с установленным ограничением на распараллеливание с помощью OpenMP в 3 нити - это значение было получено опытным путем как оптимальное) число процессоров можно смоделировать числом порожденных процессов MPI.		Из графиков видно, что при большом объеме входных данных имеется выигрыш по времени выполнения при росте числа процессоров, в то время как при небольших матрицах и небольшом числе форм выделение дополнительных процессоров лишь увеличивает накладные расходы, вследствие чего время выполнения растет. Также очевидна закономерность, при которой время выполнения в среднем растет с увеличением объема входных данных при неизменном числе процессоров. В условиях исследуемого алгоритма, конфигурации вычислительных узлов суперкомпьютера (многоядерные процессоры с подержкой гипертрединга) и реализации (используется библиотека Eigen<ref>''Eigen C++ library'' // https://libeigen.gitlab.io/</ref> с установленным ограничением на распараллеливание с помощью OpenMP в 3 нити - это значение было получено опытным путем как оптимальное) число процессоров можно смоделировать числом порожденных процессов MPI.

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

2025-12-11T10:18:45Z

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

← Предыдущая версия		Версия от 10:18, 11 декабря 2025
Строка 365:		Строка 365:
	* Число процессов: [1, 2, 4, 8, 16, 32, 64, 92].		* Число процессов: [1, 2, 4, 8, 16, 32, 64, 92].

	[[Файл:~~GPA Execution time 1~~.png\|700px\|left\|мини\|Рис.5. График зависимости времени выполнения нескольких алгоритма от объема входных данных и числа процессов (увеличенный масштаб)]]		[[Файл:Time scaled.png\|700px\|left\|мини\|Рис.5. График зависимости времени выполнения нескольких алгоритма от объема входных данных и числа процессов (увеличенный масштаб)]]
	[[Файл:~~GPA execution time 2~~.png\|700px\|right\|мини\|Рис.6. График зависимости времени выполнения нескольких алгоритма от объема входных данных и числа процессов]]		[[Файл:Time gpa corrected.png\|700px\|right\|мини\|Рис.6. График зависимости времени выполнения нескольких алгоритма от объема входных данных и числа процессов]]

	Из графиков видно, что при большом объеме входных данных имеется выигрыш по времени выполнения при росте числа процессоров, в то время как при небольших матрицах и небольшом числе форм выделение дополнительных процессоров лишь увеличивает накладные расходы, вследствие чего время выполнения растет. Также очевидна закономерность, при которой время выполнения в среднем растет с увеличением объема входных данных при неизменном числе процессоров. В условиях исследуемого алгоритма, конфигурации вычислительных узлов суперкомпьютера (многоядерные процессоры с подержкой гипертрединга) и реализации (используется библиотека Eigen<ref>''Eigen C++ library'' // https://libeigen.gitlab.io/</ref> с установленным ограничением на распараллеливание с помощью OpenMP в 3 нити - это значение было получено опытным путем как оптимальное) число процессоров можно смоделировать числом порожденных процессов MPI.		Из графиков видно, что при большом объеме входных данных имеется выигрыш по времени выполнения при росте числа процессоров, в то время как при небольших матрицах и небольшом числе форм выделение дополнительных процессоров лишь увеличивает накладные расходы, вследствие чего время выполнения растет. Также очевидна закономерность, при которой время выполнения в среднем растет с увеличением объема входных данных при неизменном числе процессоров. В условиях исследуемого алгоритма, конфигурации вычислительных узлов суперкомпьютера (многоядерные процессоры с подержкой гипертрединга) и реализации (используется библиотека Eigen<ref>''Eigen C++ library'' // https://libeigen.gitlab.io/</ref> с установленным ограничением на распараллеливание с помощью OpenMP в 3 нити - это значение было получено опытным путем как оптимальное) число процессоров можно смоделировать числом порожденных процессов MPI.
Строка 373:		Строка 373:

	[[Файл:Efficiency corrected.png\|700px\|left\|мини\|Рис.7. График зависимости эффективности распараллеливания от объема входных данных и числа процессов]]		[[Файл:Efficiency corrected.png\|700px\|left\|мини\|Рис.7. График зависимости эффективности распараллеливания от объема входных данных и числа процессов]]
	[[Файл:Speedup ~~gpa~~.png\|700px\|right\|мини\|Рис.8. График зависимости ускорения от объема входных данных и числа процессов]]		[[Файл:Speedup corrected.png\|700px\|right\|мини\|Рис.8. График зависимости ускорения от объема входных данных и числа процессов]]

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

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

2025-12-11T10:06:44Z

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

← Предыдущая версия		Версия от 10:06, 11 декабря 2025
Строка 372:		Строка 372:
	Эффективность распараллеливания есть величина <math>E = S/p</math>, где <math>S = \frac{T_1}{T_p}</math> - ускорение, <math>p</math> - число используемых процессоров, и <math>T_i</math> - время работы программы на <math>i</math> процессорах.		Эффективность распараллеливания есть величина <math>E = S/p</math>, где <math>S = \frac{T_1}{T_p}</math> - ускорение, <math>p</math> - число используемых процессоров, и <math>T_i</math> - время работы программы на <math>i</math> процессорах.

	[[Файл:~~Eff~~.png\|700px\|left\|мини\|Рис.7. График зависимости эффективности распараллеливания от объема входных данных и числа процессов]]		[[Файл:Efficiency corrected.png\|700px\|left\|мини\|Рис.7. График зависимости эффективности распараллеливания от объема входных данных и числа процессов]]
	[[Файл:Speedup gpa.png\|700px\|right\|мини\|Рис.8. График зависимости ускорения от объема входных данных и числа процессов]]		[[Файл:Speedup gpa.png\|700px\|right\|мини\|Рис.8. График зависимости ускорения от объема входных данных и числа процессов]]

OscarFox: /* Существующие реализации алгоритма */

2025-12-10T20:21:16Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 20:21, 10 декабря 2025
Строка 391:		Строка 391:
	Существует последовательная реализация GPA в библиотеке Prince<ref>''Prince Python library'' // https://maxhalford.github.io/prince/</ref> для языка программирования Python.		Существует последовательная реализация GPA в библиотеке Prince<ref>''Prince Python library'' // https://maxhalford.github.io/prince/</ref> для языка программирования Python.

	Также написаны [https://github.com/oscar-foxtrot/HPC-GPA/tree/main ~~авторская реализация~~] последовательного (на ЯП Python и C++) и параллельного алгоритма (на C++) Generalized Procrustes Analysis.		Также написаны [https://github.com/oscar-foxtrot/HPC-GPA/tree/main авторские реализации] последовательного (на ЯП Python и C++) и параллельного алгоритма (на C++) Generalized Procrustes Analysis.

	== Литература ==		== Литература ==
	<references />		<references />

OscarFox: /* Существующие реализации алгоритма */

2025-12-10T15:33:20Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 15:33, 10 декабря 2025
Строка 388:		Строка 388:

	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			Существует последовательная реализация GPA в библиотеке Prince<ref>''Prince Python library'' // https://maxhalford.github.io/prince/</ref> для языка программирования Python.

			Также написаны [https://github.com/oscar-foxtrot/HPC-GPA/tree/main авторская реализация] последовательного (на ЯП Python и C++) и параллельного алгоритма (на C++) Generalized Procrustes Analysis.

	== Литература ==		== Литература ==
	<references />		<references />

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

2025-12-10T15:15:03Z

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

← Предыдущая версия		Версия от 15:15, 10 декабря 2025
Строка 375:		Строка 375:
	[[Файл:Speedup gpa.png\|700px\|right\|мини\|Рис.8. График зависимости ускорения от объема входных данных и числа процессов]]		[[Файл:Speedup gpa.png\|700px\|right\|мини\|Рис.8. График зависимости ускорения от объема входных данных и числа процессов]]

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

	Максимальная эффективность составила <math>611.8\%</math> в случае <math>n=202</math>, и при числе процессов <math>p=4</math>.		Максимальная эффективность составила <math>611.8\%</math> в случае <math>n=202</math>, и при числе процессов <math>p=4</math>.

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

2025-12-10T15:11:26Z

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

← Предыдущая версия		Версия от 15:11, 10 декабря 2025
Строка 307:		Строка 307:
	Заметим, что параллелизм возможен только внутри итераций GPA. Итерации выполняются одна за другой последовательно, используя результаты предыдущих.		Заметим, что параллелизм возможен только внутри итераций GPA. Итерации выполняются одна за другой последовательно, используя результаты предыдущих.

	Сложность SVD ~~заслуживает отдельного внимания, так как есть различные алгоритмы и на практике~~		Сложность SVD может быть различной в зависимости от используемой реализации.

	Сначала проанализируем параллельную сложность CPA. Отметим, что матричные умножения и высчитывание определителя матрицы поворота в CPA вносят вклад <math>O(\log d + \log n + d) = O(\log n + d)</math> в высоту ЯПФ и <math>O(d^2 + nd)</math> в ширину. Если принять сложность SVD (по высоте ЯПФ) за <math>O(d^2)</math>, тогда суммарный вклад CPA в высоту ЯПФ - <math>O(\log n + d^2)</math>. Таким образом, SVD является определяющим фактором высоты ЯПФ в процедуре CPA, а матричные умножения определяют ширину.		Сначала проанализируем параллельную сложность CPA. Отметим, что матричные умножения и высчитывание определителя матрицы поворота в CPA вносят вклад <math>O(\log d + \log n + d) = O(\log n + d)</math> в высоту ЯПФ и <math>O(d^2 + nd)</math> в ширину. Если принять сложность SVD (по высоте ЯПФ) за <math>O(d^2)</math>, тогда суммарный вклад CPA в высоту ЯПФ - <math>O(\log n + d^2)</math>. Таким образом, SVD является определяющим фактором высоты ЯПФ в процедуре CPA, а матричные умножения определяют ширину.

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

2025-12-10T07:16:25Z

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

← Предыдущая версия		Версия от 07:16, 10 декабря 2025
Строка 358:		Строка 358:
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

	Исследование масштабируемости параллельной реализации алгоритма проводилось на суперкомпьютере «[https://parallel.ru/cluster/lomonosov2.html Ломоносов-2]». Для этого была исследована авторская реализация алгоритма с использованием средств MPI и OpenMP. В ходе исследования было произведено множество запусков программы с различными значениями параметра, задающего размерность форм и их число, а также различным числом процессов.		Исследование масштабируемости параллельной реализации алгоритма проводилось на суперкомпьютере «[https://parallel.ru/cluster/lomonosov2.html Ломоносов-2]». Для этого была исследована авторская реализация алгоритма, выполненная с использованием средств MPI и OpenMP. В ходе исследования было произведено множество запусков программы с различными значениями параметра, задающего размерность форм и их число, а также различным числом процессов.

	Далее представлены два графика зависимости времени выполнения от объема входных данных и числа процессов в различных масштабах. Важно, что здесь для наглядности представления положено <math>m = n = d</math>, т.е. число входных форм совпадает с числом строк и столбцов в этих формах. Соответственно, под размерностью матрицы понимается число <math>n=d</math>. Количество итераций равно двум (не включая нулевую).		Далее представлены два графика зависимости времени выполнения от объема входных данных и числа процессов в различных масштабах. Важно, что здесь для наглядности представления положено <math>m = n = d</math>, т.е. число входных форм совпадает с числом строк и столбцов в этих формах. Соответственно, под размерностью матрицы понимается число <math>n=d</math>. Количество итераций равно двум (не включая нулевую).

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

2025-12-10T07:14:29Z

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

← Предыдущая версия		Версия от 07:14, 10 декабря 2025
Строка 381:		Строка 381:
	Минимальная эффективность составила <math>0.0022\%</math> в случае <math>n=12</math>, и при числе процессов <math>p=92</math>.		Минимальная эффективность составила <math>0.0022\%</math> в случае <math>n=12</math>, и при числе процессов <math>p=92</math>.

	Исходный код и данные в числовом виде доступны в [https://github.com/oscar-foxtrot/HPC-GPA/tree/main GitHub-репозитории].		Исходный код, описание параметров окружения и данные в числовом виде доступны в [https://github.com/oscar-foxtrot/HPC-GPA/tree/main GitHub-репозитории].

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