Участница:OvsyannikovaSA/Программная реализация стохастического градиентного спуска - История изменений

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

2025-12-09T12:22:10Z

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

← Предыдущая версия		Версия от 12:22, 9 декабря 2025
Строка 18:		Строка 18:

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

			Параллелизация алгоритма стохастического градиентного спуска была произведена на основе принципа массового параллелизма, используя библиотеку OpenMP для организации многопоточности в общей памяти.

			Главная цель состояла в ускорении вычислительно наиболее затратной фазы одного шага SGD: вычисление градиента по мини-батчу.

	Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.		Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.

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

2025-12-09T11:54:08Z

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

← Предыдущая версия		Версия от 11:54, 9 декабря 2025
Строка 29:		Строка 29:
	Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.		Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

	Реализация выполнена с помощью OpenMP на суперкомпьютере "Ломоносов-2".		Реализация выполнена с помощью OpenMP на суперкомпьютере "Ломоносов-2". Число объектов в выборке <math>N=200000</math>, размерность признаков <math>m=20</math>, число эпох <math>E=30</math>, learning rate <math>\alpha=0.005</math>.
	[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]		[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

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

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

2025-12-09T09:06:09Z

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

← Предыдущая версия		Версия от 09:06, 9 декабря 2025
Строка 29:		Строка 29:
	Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.		Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

			Реализация выполнена с помощью OpenMP на суперкомпьютере "Ломоносов-2".
	[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]		[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

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

OvsyannikovaSA: добавлено: масштабируемость алгоритма и его реализации

2025-12-09T09:04:50Z

добавлено: масштабируемость алгоритма и его реализации

Новая страница

==Ссылки==
==Локальность данных и вычислений==
==Масштабируемость алгоритма и его реализации==
===Теоретическая масштабируемость алгоритма===
Масштабируемость алгоритма SGD определяется его структурой и необходимостью синхронизации на каждом шаге.

Масштабируемость самого алгоритма SGD (не зависимо от платформы) ограничена его последовательной природой в цикле обновления весов.

На каждом шаге SGD происходят следующие критические операции, которые ограничивают масштабируемость:

1. Вычисление частных градиентов: массово параллельный этап. Потоки работают независимо на своих частях мини-батча.

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

3. Обновление весов: последовательный по времени этап, но параллельный по координатам вектора весов.

Максимальное ускорение <math>S_{max}</math> на одном шаге SGD ограничено законом Амдала, где последовательная часть — это время, затраченное на глобальную редукцию и, в меньшей степени, на векторное обновление. На практике масштабируемость ограничивается эффективностью редукции при росте числа процессоров.

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

Сильная масштабируемость SGD хорошая до определенного предела. При увеличении <math>P</math> рабочая нагрузка на один процессор <math>B/P</math> уменьшается, что приводит к сокращению времени вычисления градиента.

Когда <math>P</math> становится близким к <math>B</math>, уменьшение времени вычисления градиента замедляется. При дальнейшем росте <math>P</math> время, затрачиваемое на синхронизацию, начинает доминировать над временем полезных вычислений. Это приводит к падению эффективности и остановке роста ускорения.

<math>S_{max}</math> достигается, когда <math>P \approx B</math> или <math>P \approx d</math> (зависит от того, что больше; <math>d</math> - размерность вектора весов).

Слабая масштабируемость SGD очень хорошая. При одновременном увеличении общего размера данных <math>N</math> и числа процессоров <math>P</math> время вычисления градиента (самая затратная часть) остается примерно постоянным, поскольку нагрузка на один процессор неизменна.

Слабая масштабируемость ограничивается временем глобальных операций. При очень больших <math>P</math> накладные расходы на редукцию и коммуникацию начинают увеличиваться, вызывая медленный, но стабильный рост общего времени выполнения.

[[Файл:Ускорение параллельного SGD в зависимости от числа потоков и размера батча.png]]

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