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

2022-07-20T13:35:00Z

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

← Предыдущая версия		Версия от 13:35, 20 июля 2022
Строка 59:		Строка 59:
	= Динамические характеристики и эффективность реализации алгоритма =		= Динамические характеристики и эффективность реализации алгоритма =

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

	= Результаты прогонов =		= Результаты прогонов =

ASA: Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:VladimirDobrovolsky611В.М.Добровольс...»

2022-07-20T13:34:24Z

Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:VladimirDobrovolsky611<b>В.М.Добровольс...»

Новая страница
{{level-i}}

Основные авторы описания: [https://algowiki-project.org/ru/Участник:VladimirDobrovolsky611<b>В.М.Добровольский</b>].

= Ссылки =

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

На практике алгоритм 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.

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

{|border = "1"
!Размерность данных (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 - достаточно велико, использование дополнительных процессоров заметно ускоряет решение задачи.

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

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

= Результаты прогонов =

[[Категория:Статьи в работе]]

[[En:SDDP, scalability]]

SDDP, scalability - История изменений

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

ASA: Новая страница: «{{level-i}} Основные авторы описания: [https://algowiki-project.org/ru/Участник:VladimirDobrovolsky611В.М.Добровольс...»