Дипломная работа: Автоматическое распараллеливание программ для распределенных систем. Статическое построение расширенного графа управления
Распределение вычислений и данных является одним из основных шагов в процессе создания параллельного приложения. Существует два подхода к решению этой проблемы: доменная декомпозиция, при которой основное внимание уделяется распределению относящихся к задаче данных, и функциональная декомпозиция – сначала распределяются вычисления, а затем относящиеся к ним данные. Поскольку в нашем проекте системы автоматического распараллеливания выбрана вторая методика, вид внутреннего представления определяется, в первую очередь, удобным для анализа способом хранения вычислений.
Носителями вычислений программы являются входящие в ее состав операторы. Однако, с точки зрения распараллеливания интересны не столько конкретные операторы, сколько участки программы, состоящие из последовательно выполняющихся операторов, целиком подлежащие какому-то из видов исполнения - параллельному или последовательному, а также порядок следования этих участков. Объединяя группу операторов в один элемент высокоуровнего представления программы, следует агрегировать в нем некоторую информацию, относящуюся к этим операторам. В нашем случае такой информацией является:
- Количество вычислительных операций в блоке – арифметические операции и стандартные функции. Эти данные требуются для оценки времени выполнения блока.
- Наличие операторов некоторых типов. Например, присутствие в блоке операторов ввода\вывода препятствует его параллельному выполнению.
- Список обращений к переменным и массивам с разделением по типу обращения – чтение или модификация. Этот список нужен при поиске в блоке зависимостей по данным, а также для корректного распределения данных между элементами вычислительной сети.
- Список переменных специального вида и их характеристики. Примером могут служить редукционные переменные.
Линейная последовательность выполнения описанных блоков операторов может быть нарушена одной из следующих конструкций: цикл, ветвление, безусловный переход. Для них должны существовать элементы специальных типов, отражающих их особенности. В этих элементах необходимо предусмотреть возможность хранения относящихся к ним данным. Для цикла это может быть, в частности, количество итераций, для ветвления – вероятность перехода по каждой из веток и др.
2.3 Расширенный граф управления. Вспомогательные структуры
Классической структурой для описания последовательности выполнения операторов программы является граф потока управления. Разработанное в данной дипломной работе представление программы выполняет те же функции, только в качестве его элементов используются блоки более высокого уровня. Такое представление – назовем его расширенным графом потока управления программы - в совокупности с некоторыми вспомогательными структурами содержит в себе всю информацию, необходимую для следующих в цикле работы блоков системы распараллеливания.
В процессе обработки исходной программы реализован