SDDP, scalability

Основные авторы описания: В.М.Добровольский.

Локальность данных и вычислений

На практике алгоритм SDDP необходим для решения задачи с количеством этапов порядка 100, количеством состояний порядка 20 и размерностью решения и ограничений порядка 50 на 50. Таким образом, в памяти на протяжении всей программы должно храниться 100\cdot 20\cdot (2\cdot 50+2\cdot 50\cdot 50) = 1 000 000 000 чисел типа double, т.е. около 8 ГБ. Также, каждому состоянию в ходе программы привязывается набор коэффициентов гиперплоскости, с каждой итерацией добавляются новые наборы. Так, на 100 - итерации, в памяти должно храниться около 100\cdot 20\cdot 51\cdot 100 = 10 200 000 т.е. около 80мб. Обращение к входным данным имеет временную неравномерность. Если количество пробных сценариев = k, то один раз за итерацию к каждой матрице каждого этапа алгоритм обратится k раз, причем почти одновременно. Таким образом, можно ускорить выполнение алгоритма в условиях недостаточной быстрой памяти с помощью загрузки данных нескольких этапов в кэш. При параллельной реализации можно предоставить памяти, выделенной под исходные данные, общий доступ, так как запись в эту область не предусматривается.

Другая область памяти, необходимая алгоритму - пространство коэффициентов гиперплоскости. В отличие от области входных данных, данная область растет с увеличением количества итераций алгоритма пропорционально корню номера итерации. Обращение к данному участку памяти происходит также неравномерно, т.е. k почти одновременных обращений раз в итерацию. Также нельзя без дополнительных условий организовать общий доступ к данной области памяти, т.к. в ней предусмотрены как запись новых значений, так и удаление старых.

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

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

Ввиду того, что существуют реализации алгоритма только на языке R и Matlab, которые не установлены ни на Blue gene (установить невозможно), ни на Lomonosov(в процессе установки) Результаты расчетов были проведены лишь для количества задействованных ядер многоядерного домашнего компьютера. Параметры запуска:

Процессор Intel Core i5 (4 ядра)

Программа написана на языке R, программа запуска - R.exe (R - не компилируемый, а интерпритируемый язык, изначально приложение R.exe написано на С и было откомпилировано для операционной системы Windows до установки на ПК).

Версия исполняемого скрипта - собственный автора, написанный в рамках магистерской диссертации.

Используемые библиотеки: lpSolve, Rmpi, snow, Rcluster.

Результаты тестов:

Размерность данных (T;S;N;M)	1	2	4
(5;5;10;10)	279	159,064	86,24
(10;10;10;10)	1120,8	608,402	323,239
(28;59;6;6)	62344363,245	Na	Na

Выводы о масштабируемости:

Данный алгоритм хорошо масштабируется по измерению T, т.е. в случае, когда количество этапов T - достаточно велико, использование дополнительных процессоров заметно ускоряет решение задачи.

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

Те немногие данные, которые удалось получить посредством экспериментов запуска алгоритмов на многоядерном процессоре домашнего компьютера не позволяют сделать глубоких и исчерпывающих выводов. Однако, судя по таблице, указанной в разделе 3.2 данной статьи, можно сделать вывод, что при бОльшем количестве вычислительных узлов, время выполнения алгоритма алгоритма растет медленнее при росте числа этапов.