Дубовик А.С.
Статический анализ фрагментированных программ: выделение групп
В теории фрагментированного программирования важную роль играет статический анализ фрагментированной программы [1] с целью оптимизации её исполнения.
Работа посвящена разработке алгоритма статического анализа ФП для выявления групп - подмножеств фрагментов данных и вычислений, относительно независимых от других частей ФП [2]. Оптимизация исполнения ФП состоит в том, что фрагменты вычислений назначаются на исполнение по группам, что влечёт своевременное потребление и освобождение промежуточных данных группы - фрагментов данных, существующих только во время её исполнения. Кроме этого, коммуникации, как правило, сконцентрированы внутри группы, поэтому она рассматривается исполнительной системой как единица при распределении ресурсов.
Для выделения групп из фрагментированной программы применена идея алгоритма имитации планирования [3]. Разработан алгоритм выделения частного вида групп, а именно потенциально бесконечных линейных цепочек фрагментов вычислений. Идея алгоритма заключается в обходе графа фрагментов вычислений в ширину и выделении последовательностей фрагментов вычислений, в которых каждый последующий фрагмент вычислений зависит только от предыдущего. Среди найденных цепочек выбирается набор непересекающихся цепочек, при этом критерием выбора является параметр алгоритма - качество разбиения на группы с учётом снижения непроцедурности [4].
В дальнейшем планируется усовершенствование алгоритма для выявления групп других видов, характерных для задач численного моделирования.
Список литературы
- Arykov, S., Malyshkin, V. Asynchronous Language and System of Numerical Algorithms Fragmented Programming. PaCT 2009, LNCS, vol. 5698, pp. 1-7.
- Malyshkin, V. Optimization of Parallel Execution of Numerical Programs in LuNA Fragmented Programming System / V. Malyshkin, V. Perepelkin // LNCS. - Heidelberg, 2010. - 6083 : Methods and Tools of Parallel Programming Multicomputers. - С. 1-10.
- Вальковский В.А, Малышкин В.Э. Синтез параллельных программ и систем на вычислительных моделях. // Новосибирск: Наука. Сиб. отд-ние, 1988. - 128 с.
- Малышкин В.Э. Параллельное программирование мультикомпьютеров. // Изд-во НГТУ, Новосибирск, 2006. - 296 с.
К списку докладов
