Участница:OvsyannikovaSA/Программная реализация стохастического градиентного спуска
Ссылки
Локальность данных и вычислений
Масштабируемость алгоритма и его реализации
Теоретическая масштабируемость алгоритма
Масштабируемость алгоритма SGD определяется его структурой и необходимостью синхронизации на каждом шаге.
Масштабируемость самого алгоритма SGD (не зависимо от платформы) ограничена его последовательной природой в цикле обновления весов.
На каждом шаге SGD происходят следующие критические операции, которые ограничивают масштабируемость:
1. Вычисление частных градиентов: массово параллельный этап. Потоки работают независимо на своих частях мини-батча.
2. Редукция: после вычисления частных градиентов все потоки должны выполнить редукцию для получения общего градиента. Эта операция является точкой барьерной синхронизации, т.к. ни один поток не может перейти к обновлению весов, пока не получен окончательный градиент.
3. Обновление весов: последовательный по времени этап, но параллельный по координатам вектора весов.
Максимальное ускорение [math]\displaystyle{ S_{max} }[/math] на одном шаге SGD ограничено законом Амдала, где последовательная часть — это время, затраченное на глобальную редукцию и, в меньшей степени, на векторное обновление. На практике масштабируемость ограничивается эффективностью редукции при росте числа процессоров.
Масштабируемость реализации
Параллелизация алгоритма стохастического градиентного спуска была произведена на основе принципа массового параллелизма, используя библиотеку OpenMP для организации многопоточности в общей памяти.
Главная цель состояла в ускорении вычислительно наиболее затратной фазы одного шага 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].
