Щукин Г.А.
Методы оптимизации исполнения фрагментированных программ в runtime-системе FP RTS
В технологии фрагментированного программирования [1,2] программа представляется в виде множеств фрагментов данных - ячеек памяти, фрагментов кода - функций по обработке данных, и фрагментов вычислений - применения фрагментов кода к фрагментам данных. Исполнение фрагментированной программы заключается в запуске ее фрагментов вычислений, с учетом отношения частичного порядка на их множестве.
Для динамического управления исполнением фрагментированной программы и реализации ее динамических свойств (настройка на ресурсы, динамическая балансировка нагрузки, коммуникации на фоне счета) была разработана runtime-система [3] FP RTS. Одна из особенностей FP RTS - внутреннее представление фрагментированной программы в виде взвешенного ориентированного графа, (вершины - фрагментам вычислений, дуги - пути передачи фрагментов данных), строящимся на основе описания программы. Преимущество такого представления заключается в возможности применения различных статических и динамических оптимизаций процесса исполнения программ, многие из которых реализованы в FP RTS:
- Использование уже существующих алгоритмов разбиения графов для распределения фрагментов по вычислительным узлам.
- Планирование исполнения с упреждением благодаря знанию о дальнейшем ходе исполнения всей программы или ее участка.
- Размещение соединенных дугами фрагментов на одном узле или на узлах, соединенных физическим коммуникационным каналом, с целью минимизации затрат на обмен данными и лучшей работы с памятью.
- Применение алгоритмов модификации графов для оптимизации исполнения программы. Например, статическое или динамическое дублирование фрагментов данных, позволяеющее убрать зависимости по данным между фрагментами вычислений для их параллельного исполнения.
Список литературы
- Вальковский В.А., Малышкин. В.Э. Синтез параллельных программ и систем на вычислительных моделях. - Наука, Новосибирск, 1988, 128 стр.
- Malyshkin V.E. Assembling of Parallel Programs for Large Scale Numerical Modeling. In the Handbook of Research on Scalable Computing Technologies, IGI Global, USA, 2010, Chapter 13, pp. 295-311.
- Kalgin K.V., Malyshkin V.E., Nechaev S.P., Tschukin G.A. Runtime System for Parallel Execution of Fragmented Subroutines. PACT-2007, LNCS vol. 4671, pp. 544-552.
К списку докладов