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

Сороковой А.А.  

Алгоритм распределения вычислительных ресурсов мультикомпьютера для исполнения фрагментированных программ.

В технологии фрагментированного программирования (ТФП) [1] программа может быть представлена в виде ориентированного взвешенного графа. Для того чтобы обеспечить её исполнение необходимо найти отображение во времени графа программы на мультикомпьютер, то есть распределить данные и вычисления по вычислительным узлам. Оно должно по возможности обеспечивать полную и равномерную во времени загрузку вычислителя. Была поставлена задача поиска такого отображения для класса
программ, реализующих явные конечно-разностные схемы. Для решения поставленной задачи был разработан и реализован следующий алгоритм, содержащий 3 этапа.

На первом этапе граф программы разбивается на слои подмножества вершин, которые соответствуют стадиям исполнения программы. Другими словами, фрагменты попадают в один слой, если предшествующий им (по информационным зависимостям) объем вычислений примерно одинаков. Для формирования такого разбиения граф взвешивается, вершинам назначается вес равный длине критического пути до нее. Далее вершины располагаются на прямой согласно этому весу. Далее задача сводится к задаче о ближайшем соседе [2].

На втором этапе фрагменты попавшие в один слой размещаются в N-мерном евклидовом пространстве Pi. Данные пространства Pi размещаем параллельно друг другу в N+1 мерном евклидовом пространстве S на
некотором малом расстоянии h. Далее вершины графа рассматриваются как точечные заряды с положительным зарядом, пропорциональным весу вершины, которые взаимодействуют по кулоновскому закону, а ребра - как пружинки с жесткостью пропорциональной весу ребра. Вычисляется совокупная энергия данной системы E, и ставиться задача E → min , и, таким образом, получается некоторое распределение графа в пространстве S. На третьем этапе граф программы разрезается ортогонально пространствам Pi на количество частей равное числу узлов, на которых будет производиться исполнение, равномерно относительно суммарного вычислительного веса попавшего в одну часть.

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

  1. V. Malyshkin, V. Perepelkin. Optimization of Parallel Execution of Numerical Programs in Luna Fragmented Programming System // Methods and Tools of Parallel Programming Multicomputers, LNCS 6083 - Springer, 2010, pp. 1-10.
  2. Ерзин А.И. Исследование операций. НГУ 99 стр. гл 3.3.


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