Временной анализ параллельных алгоритмов

ОБЯЗАТЕЛЬНО

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

Информационный граф

Информационный граф — граф алгоритма, где каждой вершине i сопоставлен вес w(i) — время выполнения оператора (или число тактов). Дуги показывают данные и порядок.

Зачем вешать веса: без них видно только «можно параллельно / нельзя», с весами — сколько времени займёт вся работа и где самая длинная цепочка (критический путь).

Цель анализа — найти:

1. Минимальное время T∞ при неограниченном числе процессоров (длина критического пути).
2. Минимальное число процессоров p для достижения T∞.
3. Расписание на заданное p с минимальным makespan (общим временем).

---

Ранние сроки (EST — Earliest Start Time)

Представьте стройку: фундамент → стены → крыша. Ранний срок отвечает на вопрос: «Как рано можно начать этап, если все предшественники работают без задержек?»

Обход в топологическом порядке (от истоков к стокам — сначала шаги без входящих стрелок):

EST(i) = max{ EST(j) + w(j) : j → i }   (если предшественников нет — 0)
EFT(i) = EST(i) + w(i)   // Earliest Finish Time

Обозначение	Расшифровка	Смысл
EST(i)	Earliest Start Time	Самое раннее время старта шага i
EFT(i)	Earliest Finish Time	Самое раннее время окончания = EST + вес

EST — как только все предшественники закончились, i может стартовать.

EFT — момент, когда i закончится при таком раннем старте.

Пример (веса = 1):

    (1)──►(2)──►(4)
      ╲         ▲
       ╲──►(3)──┘

i	EST	EFT
1	0	1
2	1	2
3	1	2
4	2	3

T∞ = max EFT = 3 — три «волны» параллелизма при бесконечных процессорах.

---

Поздние сроки (LFT — Latest Finish Time)

Поздний срок — зеркальная картина: «Как поздно можно начать/закончить шаг, чтобы общий дедлайн проекта (время T∞) не сдвинулся?»

Обход в обратном топологическом порядке от конца графа:

LFT(i) = min{ LST(j) : i → j }   (если преемников нет — T∞)
LST(i) = LFT(i) - w(i)

Обозначение	Смысл
LFT(i)	Latest Finish Time — крайний срок окончания i
LST(i)	Latest Start Time — крайний срок старта

LST — поздний срок начала без сдвига общего времени.

LFT — поздний срок окончания.

i	LST	LFT
4	2	3
2	1	2
3	1	2
1	0	1

---

Временной резерв (slack)

Slack(i) = LST(i) - EST(i) = LFT(i) - EFT(i)

• Slack = 0 — оператор на критическом пути; любая задержка увеличивает общее время.
• Slack > 0 — можно сдвинуть оператор без удлинения makespan → гибкость для балансировки нагрузки.

---

Критический путь

Критический путь — цепочка вершин от истока к стоку с максимальной суммой весов. Его длина = T∞.

На примере выше: 1 → 2 → 4 или 1 → 3 → 4 (оба длины 3).

Верхняя граница времени параллельного алгоритма на p процессорах:

T_p ≥ max( T∞ , ⌈W / p⌉ )

где W — сумма всех весов (время на одном процессоре). Второй член — нельзя быстрее, чем «объём работы / число рук».

---

Минимальное число процессоров

Чтобы уложиться в время T∞, нужно хотя бы столько процессоров, чтобы на каждом «уровне» antichain (множество параллельных операторов) хватило ядер:

p_min = max over levels | { i : EST(i) ∈ [t, t+1) на волне t } |

Для нашего примера на «волне» t=1 параллельны (2) и (3) → p_min = 2 для идеального T∞.

Если доступно p < p_min, время растёт: часть операторов ждёт свободный процессор.

---

Построение расписания (list scheduling)

Эвристика для p процессоров:

1. Вычислить EST, критический путь.
2. Пока есть незавершённые вершины:
   • взять готовые (все предшественники выполнены);
   • назначить приоритет: больше остаточный путь к стоку (critical-path-first);
   • отправить на свободные процессоры.

Получаем диаграмму расписания — см. модели.

---

Допустимые комбинации связей

При компоновке параллельных блоков важно сохранять частичный порядок графа:

Комбинация	Допустимость
Независимые ветви	Параллельно ✓
Producer → Consumer	Строго последовательно ✓
Цикл с зависимостью iter→iter+1	Итерации не все параллельны без специальных методов
Reduction (sum)	Параллельные частичные суммы + дерево суммирования ✓

Недопустимо: начать j до завершения предшественника по данным — гонка и неверный результат.

---

Оценки для цикла

Для цикла for i = 1..n с телом веса w и без межитерационных зависимостей:

T_1 = n · w
T∞ ≈ w        (все итерации на одной «волне»)
T_p ≈ ⌈n/p⌉ · w   (идеальная data-parallel декомпозиция)

При зависимости distance d (итерация i зависит от i−d):

Параллелизм ≤ ⌈n / d⌉

---

---

Развёрнутый пример с весами

Граф (веса в скобках):

(1:2) ──► (2:3) ──► (5:1)
  │         │
  └──► (3:1) ──► (4:2) ──► (5)

i	EST	EFT	LST	LFT	Slack
1	0	2	0	2	0
2	2	5	2	5	0
3	2	3	4	5	2
4	3	5	3	5	0
5	5	6	5	6	0

T∞ = 6 (критический путь 1→2→5 или 1→3→4→5). Узел (3) имеет slack = 2 — можно отложить без удлинения makespan.

List scheduling на p = 2

Время	P0	P1
0–2	(1)	—
2–5	(2)	(3)
3–5	—	(4) продолжение с 3
5–6	(5)	—

T₂ = 6 = T∞ — два процессора достаточны для этого графа по времени, но (5) ждёт оба предшественника.

Диаграмма Ганта (ASCII)

P0: |==1==|=====2=====|=5|
P1:       |=3=|==4==|
    0     2     4     6

---

Что дальше

• Законы Амдала и Густафсона — связь T∞ с реальным speedup
• Умножение матриц — применение временного анализа
• Построение алгоритмов

---