Законы производительности параллельных систем
Основные понятия
Пусть:
- 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. На практике редко достижимо.
Модель функциональных устройств
Для вывода законов удобна абстракция функционального устройства (ФУ) — блок, выполняющий один тип операций (умножение, загрузка из памяти, передача по сети).
| Понятие | Определение |
|---|---|
| Стоимость операции τ | Время одной операции на ФУ |
| Стоимость работы | Сумма τ по всем операциям алгоритма |
| Загруженность p | Доля реально использованной мощности ФУ за интервал |
| IPC | Число завершённых операций на такт процессора |
| Пиковая производительность | Максимум FLOPS при идеальной загрузке всех ФУ |
Простое ФУ — следующая операция стартует только после завершения предыдущей. Конвейерное ФУ — цепочка стадий: throughput растёт, пока конвейер заполнен (конвейер в архитектурах).
Минимальное время алгоритма на одной машине не меньше длины критического пути в информационном графе (статья 6). Параллельная система добавляет несколько ФУ, но связи между ними (память, сеть) вводят простои — отсюда ограничения Амдаля и рост T_comm.
Закон Амдала (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 (связь с памятью)
Roofline связывает пиковые FLOPS процессора, пропускную способность памяти и operational intensity — сколько операций приходится на байт, прочитанный из RAM.
Performance ≤ min( Peak_FLOPS , Bandwidth × Intensity )
Упрощённо: производительность ограничена min(пик FLOPS, bandwidth × operational intensity).
- Compute-bound — много операций на байт (плотная матрица, хороший cache).
- Memory-bound — мало (stencil на большой сетке, naive matmul).
Пример (порядок величин) — сервер ~200 GFLOPS (double), RAM ~100 GB/s.
| Kernel | FLOPs на элемент | Байт на элемент | Intensity | Упирается в |
|---|---|---|---|---|
SAXPY y=a*x+y | 2 | 24 (3×8) | 0,08 | Память (~8 GFLOPS) |
| Плотный matmul 64×64 block | ~2n³ / n² = 2n | ~3n²×8 | ~n/12 | Compute при больших n |
| 5-point stencil | ~5 | ~40 | 0,125 | Память |
Параллелизм слабо помогает, если каждое ядро уже упирается в память: нужна локальность данных и блочная обработка — инженерия, память и NUMA.
Интерактивные демо
Play ITЗагрузка интерактивного демо…
Лаборатория ускорения — как меняется speedup при росте числа ядер и параллельной доли; сравните сценарии Амдаля и weak scaling.
Play ITЗагрузка интерактивного демо…
Roofline Explorer — где узкое место kernel: память или вычисления. Пройдите SAXPY → stencil → matmul на одном «железе».
Play ITЗагрузка интерактивного демо…
Численный пример — иллюзия параллелизма
Последовательная сумма n элементов — T₁ = n·τ.
На p потоках с идеальным балансом — T_p ≈ n·τ/p + T_reduce, где T_reduce ≈ τ·log p.
| n | p | T₁ (мкс) | T_p (мкс) | Speedup |
|---|---|---|---|---|
| 10⁴ | 8 | 10 | ~1,5 + 0,03 | ~6,5× |
| 10² | 8 | 0,1 | ~0,02 + 0,03 | ~2× (overhead!) |
Маленькая задача на многих ядрах упирается в закон Амдала и накладные расходы — создание потоков, барьеры и обмен сообщениями съедают выигрыш, когда полезной работы мало.
Факторы, влияющие на производительность
Даже при "правильном" алгоритме итог на p узлах определяет совокупность факторов:
| Фактор | Вопрос инженеру |
|---|---|
| Архитектура | Подходит ли SIMD для задачи? Хватает ли пропускной способности сети? |
| Баланс ФУ | Нет ли узла, который все ждут (один медленный диск, слабый линк)? |
| Алгоритм | Минимизированы ли синхронизации и объём сообщений? |
| Реализация | Векторизация, размер блока, NUMA affinity, overlap MPI_Isend |
| Постановка | Растёт ли полезный объём работы с числом процессоров (weak scaling)? |
Практический порядок оптимизации — сначала алгоритм и декомпозиция (инженерия, mapping), затем библиотеки и компилятор, в конце — разгон тактов.
Таблица — что измерять при бенчмарке
| Метрика | Формула | Интерпретация |
|---|---|---|
| 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 |
Что дальше
- IT-законы и эмпирические принципы — закон Амдала в контексте других принципов
- Практика OpenMP/MPI
- Параллельный метод Гаусса — где факторы "алгоритм + обмен" видны наглядно
- Инженерия параллельных алгоритмов
- Умножение матриц
- Введение в HPC