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

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

Теоретическая масштабируемость алгоритма

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

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

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

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

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

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

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

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

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

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

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

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

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

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