Граф алгоритма и матрица следования
Граф зависимостей - порядок шагов в параллельном коде
Перед распараллеливанием нужно ответить: какие операторы обязаны идти строго друг за другом, а какие — нет? Ответ даёт граф алгоритма (граф зависимостей).
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 нет пути ни в одну сторону — они логически совместимы и могут выполняться параллельно на разных процессорах.
Формально граф задают парой G = (V, E) — множество операций V и дуги E "результат i нужен для j". Ацикличность значит: ни одна величина не определяется через саму себя по цепочке зависимостей.
Взвешенный и мультиграф
| Расширение | Смысл |
|---|---|
| Вес на дуге cᵢⱼ | Интенсивность обмена данными между ветвями (байты, сообщения MPI) |
| Вес на вершине w(i) | Время оператора — основа временного анализа |
| Мультиграф | Несколько дуг i → j, если одна операция читает разные результаты из i |
Критический путь — путь максимальной суммарной стоимости; его длина — нижняя граница времени при бесконечном числе процессоров.
Уровневая нумерация вершин
Все вершины без предшественников помечают уровнем 1 и удаляют из графа. Повторяют для оставшегося ациклического графа с уровнями 2, 3, … пока граф не опустеет.
Свойства разметки:
- вершины одного уровня не связаны дугой напрямую — кандидаты на параллельный запуск;
- число уровней s не меньше длины критического пути и не больше числа вершин;
- для фиксированного s можно строить слои расписания (как этажи на диаграмме Ганта).
Построение графа алгоритма
Шаг 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 операторов.
Граф вычисления переходного процесса
Граф переходного процесса — развитие графа алгоритма для задач, где состояние системы меняется во времени (итерации, шаги по времени в моделировании). Вершины — операторы на одном шаге, дуги — зависимости между шагами и внутри шага. Это мост к матрице следования: сначала фиксируют допустимые переходы, затем получают матрицу T для анализа параллелизма.
Для итерационных алгоритмов (решение СЛАУ, time-step симуляции) добавляют время как измерение:
- Вершина — оператор в конкретном временном шаге t.
- Дуга — зависимость внутри шага t или между t и t+1.
Так строят information graph / computation graph для временного анализа: когда оператор раньше всего и позже всего может стартовать.
Проблема отображения (mapping)
Имея граф и p процессоров, нужно раскрасить вершины в p цветов (уровни параллелизма) или упаковать в расписание минимальной длины. Это связано с:
- Раскраской графа — минимальное число цветов = хроматическое число уровня (не все параллельные группы одинаковы по весу).
- List scheduling — готовые вершины (все предшественники выполнены) назначать свободным процессорам.
Качество mapping определяет реальный speedup — см. законы производительности.
Разбор — выражение (a+b)*(c+d)
Задача: вычислить выражение (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) — максимальные множества попарно совместимых операторов.
Что дальше
- Временной анализ и информационный граф
- Инженерия параллельных алгоритмов
- Сети Петри — когда нужны ресурсы и ветвление