26-29 октября 2010 года, Красноярск

Щукин Г.А.  

Методы оптимизации исполнения фрагментированных программ в runtime-системе FP RTS

В технологии фрагментированного программирования [1,2] программа представляется в виде множеств фрагментов данных - ячеек памяти, фрагментов кода - функций по обработке данных, и фрагментов вычислений - применения фрагментов кода к фрагментам данных. Исполнение фрагментированной программы заключается в запуске ее фрагментов вычислений, с учетом отношения частичного порядка на их множестве.

Для динамического управления исполнением фрагментированной программы и реализации ее динамических свойств (настройка на ресурсы, динамическая балансировка нагрузки, коммуникации на фоне счета) была разработана runtime-система [3] FP RTS. Одна из особенностей FP RTS - внутреннее представление фрагментированной программы в виде взвешенного ориентированного графа, (вершины - фрагментам вычислений, дуги - пути передачи фрагментов данных), строящимся на основе описания программы. Преимущество такого представления заключается в возможности применения различных статических и динамических оптимизаций процесса исполнения программ, многие из которых реализованы в FP RTS:

  • Использование уже существующих алгоритмов разбиения графов для распределения фрагментов по вычислительным узлам.
  • Планирование исполнения с упреждением благодаря знанию о дальнейшем ходе исполнения всей программы или ее участка.
  • Размещение соединенных дугами фрагментов на одном узле или на узлах, соединенных физическим коммуникационным каналом, с целью минимизации затрат на обмен данными и лучшей работы с памятью.
  • Применение алгоритмов модификации графов для оптимизации исполнения программы. Например, статическое или динамическое дублирование фрагментов данных, позволяеющее убрать зависимости по данным между фрагментами вычислений для их параллельного исполнения.

Список литературы

  1. Вальковский В.А., Малышкин. В.Э. Синтез параллельных программ и систем на вычислительных моделях. - Наука, Новосибирск, 1988, 128 стр.
  2. 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.
  3. 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.


К списку докладов