Средства разработки приложений


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


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

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

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

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

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

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

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


Начало  Назад  Вперед



Книжный магазин