Законы производительности параллельных систем

ОБЯЗАТЕЛЬНО

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

Основные понятия

Пусть:

• T₁ — время на одном процессоре (одно ядро, один поток);
• T_p — время на p процессорах (ядрах, MPI-процессах);
• S(p) = T₁ / T_p — ускорение (speedup): во сколько раз быстрее стало;
• E(p) = S(p) / p — эффективность: какая доля от «идеальных p×» вы реально получили.

Пример: было 100 с на одном ядре, стало 25 с на четырёх → S(4) = 100/25 = 4×, E(4) = 4/4 = 100% (идеал). Если стало 50 с → S(4) = 2×, E(4) = 50% — половина мощности «простаивала» из-за ожиданий, памяти или последовательного кода.

Идеал: S(p) = p, E(p) = 1. На практике редко достижимо.

---

Закон Амдала (1967)

Гене Амдаль (1967) формализовал простую мысль: ускорение ограничено той частью программы, которую нельзя распараллелить.

Программа состоит из:

• S — последовательная часть (нельзя параллелить: инициализация, I/O, финальная редукция, один общий lock);
• P — параллельная часть (идеально делится на p частей без потерь).

Доля последовательного кода: f = S / (S + P) (число от 0 до 1). Параллельная доля: (1 − f).

Числовая интуиция: f = 0,1 значит 10 % времени «непараллельно». Даже на бесконечном числе ядер оставшиеся 10 % остаются → максимум 10× ускорение всей программы.

T_p = S + P/p = T₁ · ( f + (1−f)/p )

S(p) = T₁ / T_p = 1 / ( f + (1−f)/p )

Предел при p → ∞

S_max = 1 / f

Пример: f = 0.05 (5 % последовательно) → S_max = 20× — даже на миллионе ядер больше не ускорим.

f	S_max
0.50	2×
0.10	10×
0.01	100×
0.001	1000×

Инженерный вывод

Сначала сжимайте последовательную часть: профилируйте, убирайте лишние barrier, объединяйте мелкие MPI-сообщения, не синхронизируйтесь каждую итерацию.

См. также упоминание в главе про многоядерность.

---

Закон Густафсона-Барсиса (1988)

Амдаль смотрит на фиксированный размер задачи: при росте p параллельная часть делится, последовательная остаётся. Густафсон предложил другую установку: масштабировать задачу с ростом машины (типично для HPC — считаем большую сетку на большем кластере).

Пусть s — доля последовательной работы на p процессорах (измеренная на большой задаче). Тогда:

S(p) = p − (p − 1) · s

При фиксированном s speedup линейен по p (без потолка Амдала в классической форме) — потому что параллельная работа растёт вместе с ресурсами.

Смысл: если вы умеете увеличивать объём полезной параллельной работы, масштабирование может быть гораздо лучше, чем предсказывает наивный Амдаль с фиксированным n.

Оба закона верны в своих предпосылках; спор — про модель нагрузки.

---

Сравнение Амдаль и Густафсон

	Амдаль	Густафсон
Размер задачи	Фиксирован	Растёт с p
Что фиксировано	Последовательный объём	Доля s
Посыл	Есть потолок speedup	Линейное масштабирование возможно
Типичный курс	Учебный	Суперкомпьютерные симуляции

---

Производительность конвейерных систем

Для конвейера из k стадий, обрабатывающего n однородных элементов:

T = (k − 1) · τ + n · τ ≈ n · τ   при большом n

Throughput (элементов/сек): ≈ 1/τ при полной загрузке.

Ускорение относительно последовательной обработки без конвейера (n·k·τ):

S ≈ k   (асимптотически)

На алгоритмическом уровне software pipelining: стадии «load / compute / store» перекрываются для разных итераций — см. архитектуры.

---

Масштабируемость

Сильная масштабируемость (Strong scaling)

Фиксированная задача, растёт p. Хороший тест «насколько быстрее на большей машине ту же задачу». Обычно E(p) падает из-за коммуникаций и f.

Слабая масштабируемость (Weak scaling)

Задача на процессор фиксирована, растут и p, и общий объём пропорционально. Цель: T_p ≈ const. Реалистичнее для роста симуляции.

Efficiency_weak = T_1 / T_p   (при p·work на узел)

---

Верхняя граница времени

Из временного анализа:

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

• T∞ — критический путь;
• W/p — объём работы;
• T_comm — время обмена на distributed системах.

Факторы, ухудшающие производительность:

Фактор	Что делать
Последовательный код	Уменьшить f
Синхронизация	Реже barriers, async MPI
False sharing	Padding, локальные буферы
NUMA	Affinity, first-touch
Load imbalance	Dynamic scheduling
Мелкие сообщения	Batch, aggregation

---

Пример численный (Амдаль)

T₁ = 100 с, f = 0.08, p = 16:

T_16 = 100 · (0.08 + 0.92/16) = 100 · (0.08 + 0.0575) = 13.75 с
S = 100 / 13.75 ≈ 7.27×   (не 16×!)
E = 7.27 / 16 ≈ 45%

---

Вывод формулы Амдаль (для запоминания)

Пусть T₁ = S + P, параллельная часть идеально делится на p процессоров:

T_p = S + P/p = S + (T₁ − S)/p = T₁ · ( S/T₁ + (1 − S/T₁)/p ) = T₁ · ( f + (1−f)/p )

Отсюда S(p) = 1 / (f + (1−f)/p). Ключевой вывод: S не зависит от абсолютного размера задачи, только от доли f и p.

---

Численный пример Густафсонa

Симуляция на p = 1024 процессорах: измерили, что s = 0,01 (1 % времени — последовательная фаза, 99 % — параллельная работа на большой сетке).

S(1024) = 1024 − 1023 · 0,01 = 1024 − 10,23 ≈ 1013,8×

При том же f = 0,01 Амдаль даёт S_max = 100× для фиксированной малой задачи. Разница — в том, что при росте машины вы считаете бóльшую сетку, и параллельная работа растёт.

---

Karp–Flatt metric (где теряется масштабирование)

e — доля «последовательной работы», оценённая из эксперимента:

e = ( 1/S(p) − 1/p ) / ( 1 − 1/p )

Если e стабильно > 0 при росте p, узкое место структурное (код, синхронизация), а не шум измерения. Удобно строить график e от p.

---

Iso-efficiency (кратко)

Iso-efficiency отвечает: «насколько нужно увеличить задачу, чтобы при удвоении p сохранить ту же efficiency?» Алгоритм с хорошей iso-efficiency (медленный рост объёма) масштабируется на большие кластеры; с плохой — быстро упирается в коммуникации. Формально связано с ростом T_comm от p — см. модели и топологии.

---

Модель Roofline (связь с памятью)

Упрощённо: производительность ограничена min(пик FLOPS, bandwidth × operational intensity).

Performance ≤ min( Peak_FLOPS , Bandwidth × (FLOPs / Bytes) )

• Compute-bound — много операций на байт (плотная матрица, хороший cache).
• Memory-bound — мало (stencil на большой сетке, naive matmul).

Параллелизм слабо помогает, если каждое ядро уже упирается в память (memory-bound): нужна локальность данных и блочная обработка — инженерия, введение.

---

Таблица — что измерять в отчёте

Метрика	Формула	Интерпретация
Speedup	T₁/T_p	Во сколько раз быстрее
Efficiency	S/p	1 = идеал
f (Амдаль)	из S(p) или профиля	Потолок
s (Густафсон)	serial time / total	При росте задачи
Weak eff.	T₁(n/p)/T_p(n)	Постоянство при росте n и p

---

Что дальше

• Практика OpenMP/MPI

• Инженерия параллельных алгоритмов

• Умножение матриц

• Введение в HPC

---