8.2 Понятие графа зависимости между операторами

Информационные связи между операторами могут быть определены на графе зависимости. Две операции являются зависимыми, если при выполнении они обращаются к одной и той же переменной (ячейке памяти). То есть, информационная зависимость реализуется выполнением операции чтения – запись над одной и той же переменной программы.

Пример графо зависимости:

Переменные Х, У, изменяемые в ходе выполнения программы. Значения Х,У определяются в операторах 1,2,4,6. Тогда вид графо зависимости:

Вывод, таким образом, информационный граф программы является подграфом зависимости. Из графа зависимости вытекает понятие графа влияния программы.

8.3 Граф влияния

Транзитивное замыкание непосредственных зависимостей позволяет получить граф влияния. Операция программы влияет на другую (транзитивная зависимость), если изменяющиеся значения переменной, которые вычисляются в перовой операции, влияют на изменение значений переменной, вычисляемой в другой операции, таким образом, граф влияния предполагает соединение дугой каждой пары вершин, в которых одна операция влияет на другую (направление дуги графа совпадает с направлением влияния между оператором). Отношения управления информационной связью и зависимости не являются транзитивными, отношения влияния транзитивны. Граф влияния – это представление транзитивного замыкания графо зависимости.

Пример:

Изменение значений в 1 и 2 влияет на 4 и 6.

8.4 Теоретико-графовый подход к распараллеливанию алгоритмов

Задача представляется в виде последовательности операторов А = {a_1, a_2, a_3, …, a_n}.Задача распараллеливания состоит в выделении из множества Ф подмножества _i взаимно независимых операторов, где i определяет некоторый ярус ЯПФ. Через ₀ могут быть обозначены операторы, зависящие от входных данных программы. Для совокупности подмножеств _i выполняется условие:

1. _i ,

2. _{i j} = 0,

3. = A

Задача распараллеливания может быть сформирована в соответствии с теорией графов.

Множество А представляется в виде графа G: G (A,Г),

Где а_i, a_{j ,} (а_i, a_j) Г

Дуга (а_i, a_j) соединяет две вершины в случае если результат i-го оператора является аргументом для j-го.

Обозначения:

Г _j - множество вершин, последующих за j-м ярусом, в которые ведут дуги из операторов данного j-го яруса, тогда

_i - некоторое подмножество Г _j, то есть множество вершин i-го яруса, в которые ведут дуги из вершин j-го яруса (множество _j).

Г _j - множество вершин графа последующих ярусов, в которые ведут дуги из данного оператора a_j, тогда a_i Г _j (наличие дуги, ведущей из оператора a_j в a_i ). Таким образом, Г _j и Г _j определяют множество вершин, соединенных дугами с вершинами множества _j либо с вершинами _j. Тогда распараллеливание – это задача разбиения вершин графа на подмножества _j, так, чтобы удовлетворить введенные условия (1,2,3) и множество _j является подмножеством Г _j. Для каждой операции a_{i S} предполагается наличие другой операции a_{i S-1,} a_j Гa_j.