Граф алгоритма и матрица следования

ОБЯЗАТЕЛЬНО

Разработчику Архитектору

Граф зависимостей - порядок шагов в параллельном коде

Перед распараллеливанием нужно ответить: какие операторы обязаны идти строго друг за другом, а какие — нет? Ответ даёт граф алгоритма (граф зависимостей).

DAG (Directed Acyclic Graph) — ориентированный ациклический граф: стрелки показывают порядок «сначала → потом», циклов «A ждёт B, B ждёт A» внутри одного шага нет. Циклы for в коде разбирают отдельно (межитерационные зависимости).

Элемент графа	Что означает
Вершина	Один элементарный шаг: присваивание, умножение, вызов функции
Дуга u → v	v нельзя начать, пока не закончился u (из-за данных)
Нет дуги между u и v	Шаги можно выполнять параллельно (если хватает процессоров)

Вершина — элементарный оператор (присваивание, арифметическая операция, вызов).

Дуга u → v — оператор v зависит от результата u (истинная или антизависимость по данным).

     ┌──► B ──┐
A ───┤        ├──► E
     └──► C ──┘
          D ────► (если D независим от B,C — параллелен им)

Если между B и C нет пути ни в одну сторону — они логически совместимы и могут выполняться параллельно на разных процессорах.

---

Построение графа алгоритма

Шаг 1. Разбить алгоритм на операторы

Каждое присваивание и каждая операция чтения/записи — отдельная вершина. Условные операторы можно развернуть в несколько путей или пометить как «region».

Пример последовательного кода:

(1)  a := x + y
(2)  b := a * 2
(3)  c := x - y
(4)  d := b + c

Шаг 2. Найти зависимости по данным

• Истинная зависимость (flow): (2) читает a, которую пишет (1) → дуга 1→2.
• Антизависимость (anti): (4) читает b до того, как кто-то перезапишет — если бы был reuse, нужна дуга.
• Зависимость по выходу (output): два оператора пишут в одну переменную.

Для (1)–(4):

(1) → (2) → (4)
(3) ────────► (4)

(1) и (3) оба используют x, y, но не зависят друг от друга — параллельны. (2) и (3) тоже параллельны после завершения своих предшественников.

Шаг 3. Транзитивное замыкание (опционально)

Если есть путь u → … → v, зависимость u → v выполняется транзитивно. Для анализа параллелизма часто хранят непосредственные дуги (cover edges).

---

Матрица следования (precedence matrix)

Для n операторов строится матрица T размер n × n:

T[i][j] = 1, если оператор i должен завершиться ДО начала j
T[i][j] = 0 иначе

Для примера выше (нумерация 1…4):

     1  2  3  4
1 [  0  1  0  0 ]
2 [  0  0  0  1 ]
3 [  0  0  0  1 ]
4 [  0  0  0  0 ]

Транзитивное замыкание (алгоритм Warshall–Floyd) даёт полную матрицу всех порядковых ограничений:

T*[i][j] = 1  ⇔  существует путь от i к j в графе

Логически несовместимые операторы

Операторы i и j несовместимы (не могут идти одновременно), если:

T[i][j] = 1  ИЛИ  T[j][i] = 1

Совместимы (потенциально параллельны), если оба элемента 0 в транзитивном замыкании для пары (i, j) и (j, i).

Для (2) и (3): T[2][3]=0, T[3][2]=0 → можно параллелить.

---

Матрица смежности и преобразования

Матрица смежности A графа: A[i][j]=1, если есть прямая дуга i→j.

Полезные преобразования:

Операция	Смысл
Транзитивное замыкание	Все косвенные зависимости
Транзитивное сокращение	Удалить «лишние» дуги, сохранив порядок
Дополнение	Пары без пути — кандидаты в параллельные группы

При распараллеливании цикла (loop) строят граф для одной итерации и граф межитерационных зависимостей (distance vector) — иначе параллельный for даст неверный результат.

---

---

Межитерационные зависимости (distance vector)

Классический пример — рекуррентное обновление массива:

for i = 1 .. n-1
    a[i+1] = a[i] + b[i]

Итерация i пишет a[i+1], итерация i+1 читает a[i+1]. Зависимость между соседними итерациями, distance d = 1.

Distance d	Смысл	Параллелизм без преобразования
0	Нет межитерационной зависимости	Все n итераций на одной «волне»
1	i зависит от i−1	Не более ⌈n/2⌉ одновременно
d	i зависит от i−d	Не более ⌈n/d⌉

Преобразования: loop interchange, strip-mining, renaming (временные массивы) — см. инженерию.

---

Алгоритм Warshall — пошагово

Для графа из 4 операторов матрица смежности (прямые дуги):

     1  2  3  4
1 [  0  1  0  0 ]
2 [  0  0  0  1 ]
3 [  0  0  0  1 ]
4 [  0  0  0  0 ]

Warshall: для каждого k от 1 до n: если T[i][k]=1 и T[k][j]=1, то T[i][j]=1.

k	Новые единицы
1	без изменений
2	T[1][4]=1 (цепочка 1→2→4)
3	T[1][4]=1 уже (1→3→4)
4	—

Итоговое замыкание:

     1  2  3  4
1 [  0  1  0  1 ]
2 [  0  0  0  1 ]
3 [  0  0  0  1 ]
4 [  0  0  0  0 ]

Пары (2,3) и (3,2) — нули → параллельны. Пара (1,3): оба нуля → тоже параллельны.

Сложность: O(n³) для n операторов.

---

Граф вычисления переходного процесса

Для итерационных алгоритмов (решение СЛАУ, time-step симуляции) добавляют время как измерение:

• Вершина — оператор в конкретном временном шаге t.
• Дуга — зависимость внутри шага t или между t и t+1.

Так строят information graph / computation graph для временного анализа: когда оператор раньше всего и позже всего может стартовать.

---

Проблема отображения (mapping)

Имея граф и p процессоров, нужно раскрасить вершины в p цветов (уровни параллелизма) или упаковать в расписание минимальной длины. Это связано с:

• Раскраской графа — минимальное число цветов = хроматическое число уровня (не все параллельные группы одинаковы по весу).
• List scheduling — готовые вершины (все предшественники выполнены) назначать свободным процессорам.

Качество mapping определяет реальный speedup — см. законы производительности.

---

Практический мини-разбор

Задача: вычислить выражение (a+b)*(c+d) минимумом операций.

S1: t1 = a + b
S2: t2 = c + d
S3: t3 = t1 * t2

Матрица следования (S1,S2,S3):

• S1→S3, S2→S3; S1 и S2 независимы.

На 2 процессорах: S1 и S2 одновременно, затем S3.

---

Инструменты и автоматизация

Компиляторы строят dependence graph внутри циклов (автовекторизация, OpenMP depend). Для ручного анализа:

• нарисовать DAG на бумаге;
• построить матрицу в таблице;
• найти уровни (antichains) — максимальные множества попарно совместимых операторов.

---

Что дальше

• Временной анализ и информационный граф
• Инженерия параллельных алгоритмов
• Сети Петри — когда нужны ресурсы и ветвление

---