Граф зависимостей по данным

При разделении программы на нити прежде всего нужно учитывать зависимости по данным. Поэтому естественно потребовать, чтобы промежуточное представление программы содержало легкодоступную информацию о зависимостях по данным между различными частями программы. В то же время необходимо максимально отразить сведения о "естественном" параллелизме программы, причем на разных уровнях - от отдельных инструкций, до более крупных программных блоков.

Представлением, обладающим всеми необходимыми нам свойствами, является иерархический граф зависимостей по данным, используемый в [9] (data dependence graph, DDG). Узлом такого графа может являться:

Простой оператор (сложение, умножение, сравнение, присваивание и т.д.)
Более сложный оператор (условный оператор, оператор цикла и т.д.)
Граф зависимостей по данным следующего уровня, инкапсули-рующий свойства соответствующего программного блока

Дуги графа DDG представляют собой зависимости по данным между узлами. Более формально, пусть u и v - узлы DDG, причем в последовательной программе u предшествует v. Дуга (u, v) входит в граф тогда и только тогда, когда между u и v есть зависимость по данным одного из трех типов:

"запись-чтение" (в узле v необходимы результаты вычислений узла u),
"чтение-запись" (в узле v записывается переменная, значение которой считывается в u),
"запись-запись" (оба узла записывают одну и ту же пере-менную).

Наличие одной из указанных зависимостей по данным между узлами говорит о том, что при параллельном выполнении программы для получения результатов, совпадающих с последовательной версией, необходимо выполнить u раньше, чем v.

Легко заметить, что граф зависимостей по данным является ориентированным ациклическим графом. Это объясняется тем, что циклы в DDG означают наличие циклических зависимостей по данным, возможных, в свою очередь, только в операторах цикла исходной программы. Но циклы, как и другие сложные операторы, раскрываются на более низком уровне иерархии, обеспечивая разрыв таких зависимостей по данным.

Содержание Назад Вперед

Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий