Граф зависимостей по данным
При разделении программы на нити прежде всего нужно учитывать зависимости по данным. Поэтому естественно потребовать, чтобы промежуточное представление программы содержало легкодоступную информацию о зависимостях по данным между различными частями программы. В то же время необходимо максимально отразить сведения о "естественном" параллелизме программы, причем на разных уровнях - от отдельных инструкций, до более крупных программных блоков.
Представлением, обладающим всеми необходимыми нам свойствами, является иерархический граф зависимостей по данным, используемый в [9] (data dependence graph, DDG). Узлом такого графа может являться:
- Простой оператор (сложение, умножение, сравнение, присваивание и т.д.)
- Более сложный оператор (условный оператор, оператор цикла и т.д.)
- Граф зависимостей по данным следующего уровня, инкапсули-рующий свойства соответствующего программного блока
Дуги графа DDG представляют собой зависимости по данным между узлами. Более формально, пусть u и v - узлы DDG, причем в последовательной программе u предшествует v. Дуга (u, v) входит в граф тогда и только тогда, когда между u и v есть зависимость по данным одного из трех типов:
- "запись-чтение" (в узле v необходимы результаты вычислений узла u),
- "чтение-запись" (в узле v записывается переменная, значение которой считывается в u),
- "запись-запись" (оба узла записывают одну и ту же пере-менную).
Наличие одной из указанных зависимостей по данным между узлами говорит о том, что при параллельном выполнении программы для получения результатов, совпадающих с последовательной версией, необходимо выполнить u раньше, чем v.
Легко заметить, что граф зависимостей по данным является ориентированным ациклическим графом. Это объясняется тем, что циклы в DDG означают наличие циклических зависимостей по данным, возможных, в свою очередь, только в операторах цикла исходной программы. Но циклы, как и другие сложные операторы, раскрываются на более низком уровне иерархии, обеспечивая разрыв таких зависимостей по данным.
Это свойство графа будет использоваться нами в дальнейшем.
Пример функции и ее графа зависимостей по данным приведен на Рис. 1. DDG состоит из трех узлов: двух простых узлов и оператора цикла, раскрывающегося в DDG второго уровня.
Граф зависимостей по данным строится для каждой функции программы. Алгоритм построения состоит из следующих этапов:
- Построение графа потока управления программы.
- Выбор программных блоков, которые будут узлами текущего уровня иерархии DDG.
- Нахождение зависимостей по данным между этими узлами с помощью алгоритма достигающих определений.
- Если необходимо, продвинуться на следующий уровень иерархии и достроить граф.
