Параллельные вычисления — итоги
Кратко — что стоит унести из раздела "Параллельные вычисления". Если пункт кажется туманным — откройте указанную главу или оглавление.
FAQ — Часто задаваемые вопросы
Типичные сбои и ситуации при распараллеливании — от "добавил потоки — стало медленнее" до странных результатов на кластере. Здесь — что делать и где копать в главах; формулировки для самопроверки — в чек-листе.
Вопрос. Добавил parallel for — стало медленнее, чем один поток. Я что-то сломал?
Ответ. Накладные расходы на создание потоков, синхронизацию и кэш могут перевесить выигрыш на маленьких данных. Измерьте на вашем N; параллелизм окупается на достаточно больших задачах. Подробнее здесь — законы производительности, инженерия алгоритмов.
Вопрос. Результат на 8 ядрах каждый раз чуть разный — это баг железа?
Ответ. Часто race condition — недетерминированный порядок без барьеров или atomic. Сначала проверьте корректность на одном потоке, затем с -O0 и thread sanitizer. Подробнее здесь — практика OpenMP/MPI, инженерия.
Вопрос. "У нас 32 ядра — значит ускорение будет ×32?"
Ответ. Закон Амдаля: последовательная доля и sync ограничивают speedup. 16 ядер ≠ ×16 даже при идеальном коде. Подробнее здесь — законы производительности, лаборатория на intro.
Вопрос. Путаница: async/await в веб-сервере и OpenMP в численном коде — одно и то же?
Ответ. Нет. Async в I/O — не блокировать ожидание сети; OpenMP/MPI — параллельные вычисления над данными. Разные модели и метрики. Подробнее здесь — введение, асинхронность.
Вопрос. Программа иногда зависает на всех ядрах — CPU 100%, прогресса нет.
Ответ. Подозрение на deadlock или livelock — барьеры, lock order, MPI waitall. Упростите до 2 потоков, добавьте таймауты в тестах. Подробнее здесь — сети Петри, практика.
Вопрос. OpenMP или MPI — что выбрать для первого проекта на кластере?
Ответ. Одна shared-memory машина — OpenMP. Несколько узлов без общей RAM — MPI. Гибрид OpenMP+MPI — когда узел многоядерный. Подробнее здесь — модели и топологии, практика.
Вопрос. Разбил массив на части — на границах неверные значения (stencil, матрицы).
Ответ. Нужен обмен halo / ghost cells между соседними блоками перед следующим шагом. Без halo граница "не видит" соседа. Подробнее здесь — инженерия алгоритмов, умножение матриц.
Вопрос. Speedup на 2 ядрах 1.9×, на 16 — только 4×. Куда делось ускорение?
Ответ. Растут конкуренция за память, false sharing, barriers. Постройте граф зависимостей и профиль — узкое место смещается с CPU на sync. Подробнее здесь — законы производительности, временной анализ.
Вопрос. False sharing — слышал термин, на практике что ломается?
Ответ. Два потока пишут в разные переменные в одной cache line — кэш бесконечно инвалидируется. Выравнивание и padding по строкам кэша. Подробнее здесь — инженерия, архитектуры.
Вопрос. NUMA-сервер: без настройки потоки медленнее, чем на ноутбуке.
Ответ. Память выделяется на узле первого касания — first-touch. Привязывайте потоки и данные к одному socket (numactl). Подробнее здесь — память и кластеры, инженерия.
Вопрос. GPU даёт ×100 на matmul в рекламе, у меня — ×3.
Ответ. Малые матрицы упираются в копирование host↔device; kernel должен быть compute-bound с высокой intensity. Смотрите Roofline. Подробнее здесь — введение и Roofline, умножение матриц.
Вопрос. MPI-программа на 4 процессах работает, на 64 — падает или висит.
Ответ. Проверьте collective vs point-to-point, deadlock в нестандартном порядке send/recv, лимиты открытых файлов на кластере. Запускайте с MPI_Comm_size 2→4→8. Подробнее здесь — практика MPI, модели.
Вопрос. Slurm выделил 8 узлов, job сразу в очереди часами.
Ответ. Кластер планирует ресурсы — возможно, запрошено больше, чем свободно, или неверная partition/qos. Начните с одного узла для отладки. Подробнее здесь — память и кластеры.
Вопрос. Не могу распараллелить цикл — итерация i+1 зависит от i.
Ответ. Это зависимость по данным — постройте граф алгоритма, найдите wavefront или другую декомпозицию. Не каждый цикл parallelizable. Подробнее здесь — граф алгоритма, временной анализ.
Вопрос. Matmul на MPI "работает", но результат не совпадает с numpy.
Ответ. Проверьте раскладку блоков, индексацию row/column major (в NumPy — row-major, см. массивы), halo. Сравнивайте с эталоном на малых N. Подробнее здесь — умножение матриц, практика.
Вопрос. #pragma omp parallel for без reduction — сумма накапливается неверно.
Ответ. Несколько потоков пишут в одну переменную — data race. Используйте reduction(+:sum) или локальные аккумуляторы + merge. Подробнее здесь — практика OpenMP, инженерия.
Вопрос. Профiler показывает 90% времени в MPI_Wait — оптимизировать вычисления?
Ответ. Узкое место — коммуникации. Overlap compute/comm (MPI_Isend), уменьшите число сообщений, смените топологию. Подробнее здесь — практика, модели.
Вопрос. Weak scaling: удвоил процессы и данные — время выросло. Это провал?
Ответ. Растут синхронизация и сеть — смотрите efficiency и iso-efficiency. Густафсон даёт другую картину, чем Амдаль на фиксированном input. Подробнее здесь — законы производительности.
Вопрос. SAXPY быстрый на одном ядре, SIMD "не помогает".
Ответ. SAXPY часто memory-bound — упирается в bandwidth, не в FLOPS. Оптимизируйте locality, blocking; SIMD без bandwidth мало даёт. Подробнее здесь — введение / Roofline, архитектуры SIMD.
Вопрос. Метод Гаусса на кластере — на последних шагах один процесс занят, остальные ждут.
Ответ. Этапная зависимость по pivot — на поздних k мало строк, load imbalance. Это ожидаемо; сравните с matmul. Подробнее здесь — метод Гаусса, временной анализ.
Вопрос. Не понимаю PRAM — зачем модель, если железо другое?
Ответ. PRAM даёт нижние границы и идею шагов без шума реальной сети — переносите выводы осторожно на MPI. Подробнее здесь — модели и топологии, граф алгоритма.
Вопрос. Критический путь в графе алгоритма длиннее, чем время на одном CPU — почему?
Ответ. Критический путь — минимум по времени при неограниченных ресурсах; реальное время ≥ этого пути + накладные расходы. Подробнее здесь — временной анализ, граф.
Вопрос. Сеть Петри "для теоретиков" — есть ли польза инженеру?
Ответ. Помогает увидеть конфликт ресурсов, deadlock, bounded buffer до написания кода. Подробнее здесь — сети Петри.
Вопрос. Запускаю OpenMP с OMP_NUM_THREADS=999 — bудет быстрее?
Ответ. Потоков больше, чем физических ядер, — oversubscription и context switch. Обычно threads = cores или cores−1. Подробнее здесь — практика, архитектуры.
Вопрос. Результат верен на float, на double расходится между serial и parallel.
Ответ. Порядок суммирования меняется — ассоциативность float нарушена. Для strict bitwise equality используйте Kahan или фиксированный порядок reduction. Подробнее здесь — инженерия, практика.
Вопрос. Новичок хочет "распараллелить" весь монолитный legacy на выходных.
Ответ. Начните с profiling hot spot — одно compute-bound ядро (matvec, matmul). Параллелизм без модели даёт хрупкий код. Подробнее здесь — введение, инженерия.
Вопрос. Fortran/OpenMP в статье 11 страшен — можно ли пройти раздел без C++?
Ответ. Статьи 1–10 и псевдокод — основной маршрут; блоки C/C++ — справочные эталоны. Подробнее здесь — о разделе, практика.
Вопрос. Что такое параллельные вычисления и зачем они нужны?
Ответ. Это одновременное выполнение частей задачи на нескольких ядрах или узлах для ускорения compute-bound работ — моделирование, ML, HPC. Подробнее здесь — введение в параллельные процессы.
Вопрос. OpenMP tutorial — как распараллелить цикл for в C/C++?
Ответ. #pragma omp parallel for над независимыми итерациями; для reduction — reduction(+:sum). Сначала проверьте зависимости. Подробнее здесь — практика OpenMP/MPI, инженерия.
Вопрос. MPI что это — Message Passing Interface простыми словами?
Ответ. MPI — стандарт обмена сообщениями между процессами на кластере без общей RAM. Send/Recv, Broadcast, Reduce. Подробнее здесь — модели и топологии, практика.
Вопрос. Закон Амдаль — формула и почему 16 ядер не дают ×16?
Ответ. Speedup ограничен долей последовательного кода f: S ≤ 1/(f + (1-f)/N). Даже малая f даёт потолок. Подробнее здесь — законы производительности, лаборатория на intro.
Вопрос. Multithreading vs multiprocessing — в чём разница?
Ответ. Потоки — общая память процесса (OpenMP); процессы — отдельные адресные пространства (MPI). Подробнее здесь — память и кластеры, модели.
Вопрос. CUDA и GPU параллельные вычисления — когда нужна видеокарта?
Ответ. GPU оправдан при массовом data-parallel (matmul, нейросети) с большими массивами; малые задачи проигрывают из-за копирования. Подробнее здесь — законы и Roofline, GPU в энциклопедии.
Вопрос. Что такое SIMD и AVX — связь с параллелизмом?
Ответ. SIMD — одна инструкция над пакетом данных (векторные регистры AVX/NEON). Это data-parallel на одном ядре. Подробнее здесь — классификация архитектур Флинн.
Вопрос. Shared memory vs distributed memory — простое объяснение?
Ответ. Shared — потоки видят одну RAM (OpenMP); distributed — у каждого узла своя память, обмен через MPI/сеть. Подробнее здесь — память, кластеры, GRID.
Вопрос. NUMA что это и почему влияет на скорость программы?
Ответ. Non-Uniform Memory Access — память ближе к одному CPU socket дороже с другого. First-touch и привязка потоков критичны. Подробнее здесь — память и кластеры, инженерия.
Вопрос. Roofline model — как понять memory-bound vs compute-bound?
Ответ. Сравните operational intensity (FLOPs/byte) с наклоном bandwidth и потолком FLOPS — ниже knee = memory-bound. Подробнее здесь — введение, лаборатория Roofline на intro.
Вопрос. Strong scaling vs weak scaling — в чём разница?
Ответ. Strong — фиксированный размер задачи, растём по P; weak — задача растёт с P (Густафсон-Barsis). Разные метрики efficiency. Подробнее здесь — законы производительности.
Вопрос. Как распараллелить умножение матриц — алгоритм MPI?
Ответ. Блочное разбиение (Cannon, SUMMA), halo не нужен для dense matmul, но нужны синхронные обмены блоков. Подробнее здесь — параллельное умножение матриц, практика.
Вопрос. Slurm HPC cluster — как запустить MPI job?
Ответ. Скрипт с #SBATCH, srun mpirun ./program — узлы и процессы задаёт планировщик. Подробнее здесь — память и кластеры, практика MPI.
Вопрос. Race condition в многопоточности — что это?
Ответ. Несколько потоков обращаются к данным без синхронизации — результат зависит от порядка. Лечится locks, atomics, immutable data. Подробнее здесь — инженерия параллельных алгоритмов, практика.
Вопрос. Deadlock в параллельной программе — классический пример?
Ответ. Dining philosophers, циклическое ожидание lock A→B и B→A. Моделируйте в сетях Петри до кода. Подробнее здесь — сети Петри.
Вопрос. Data parallelism vs task parallelism — примеры?
Ответ. Data — одна операция над массивом (SAXPY); task — разные функции на разных данных (pipeline). Подробнее здесь — инженерия алгоритмов.
Вопрос. PRAM model — зачем учить, если железо другое?
Ответ. PRAM даёт теоретические шаги и нижние границы без стоимости сети — перенос на реальные системы с поправкой на comm. Подробнее здесь — модели и топологии.
Вопрос. Критический путь в параллельном алгоритмe — как найти?
Ответ. Постройте DAG, посчитайте EST/LST, slack = LST − EST; нулевой slack — критический путь. Подробнее здесь — временной анализ, граф алгоритма.
Вопрос. MPI_Bcast vs MPI_Scatter — когда что использовать?
Ответ. Bcast — одни и те же данные всем; Scatter — разные куски каждому процессу. В Гауссе — bcast pivot row. Подробнее здесь — метод Гаусса, практика MPI.
Вопрос. Параллельный метод Гаусса для СЛАУ — в чём сложность?
Ответ. Этапная синхронизация по pivot, broadcast строки, load imbalance на поздних k. Контраст с matmul. Подробнее здесь — параллельное решение СЛАУ — метод Гаусса.
Вопрос. Как измерить speedup и efficiency параллельной программы?
Ответ. Speedup = T1/Tp; efficiency = S/p. Сравнивайте на одних данных и прогоняйте serial baseline. Подробнее здесь — законы производительности.
Вопрос. HPC кластер vs облако AWS — когда свой кластер?
Ответ. Постоянная heavy нагрузка и низкая latency между узлами — свой кластер/GRID; эпизодические job — облако с MPI. Подробнее здесь — память, кластеры, GRID.
Вопрос. Fortran OpenMP MPI — почему в HPC до сих пор Fortran?
Ответ. Историческая база численных библиотек, предсказуемость, компиляторы с vectorization. Для обучения моделей достаточно псевдокода раздела. Подробнее здесь — Fortran HPC, практика.
Вопрос. Параллелизм vs асинхронность Node.js — частая путаница?
Ответ. Async I/O не загружает все ядра CPU; для compute нужны worker threads, cluster или native HPC. Подробнее здесь — введение, асинхронность.
Терминология раздела
Краткий словарь для навигации по статьям. Подробные определения — в соответствующих главах.
Архитектура и память
| Термин | Смысл |
|---|---|
| SISD / SIMD / MIMD | Таксономия Флинна — один или много потоков команд и данных (глава 2) |
| Shared memory | Потоки или процессы видят одну RAM на узле |
| Distributed memory | У каждого MPI-процесса своя память; обмен только сообщениями |
| NUMA | Память физически привязана к сокетам; «чужая» RAM медленнее |
| halo | Слой соседних ячеек у границы декомпозиции для stencil-задач |
Модели и графы
| Термин | Смысл |
|---|---|
| PRAM | Идеализированная shared-memory машина для теоретических оценок |
| SPMD | Один код на всех процессах, разные данные по rank |
| Критический путь | Самая длинная цепочка зависимостей — нижняя граница времени |
Производительность
| Термин | Смысл |
|---|---|
| Speedup S(p) = T₁/T_p | Во сколько раз быстрее на p исполнителях |
| Efficiency E(p) = S/p | Доля от идеального линейного ускорения |
| Strong scaling | Фиксированный размер задачи, растёт p |
| Weak scaling | Размер задачи растёт пропорционально p |
| Operational intensity | FLOPs на байт из памяти — ось модели Roofline |
MPI
| Термин | Смысл |
|---|---|
| rank | Номер процесса в группе (0, 1, …, size−1) |
| size | Число процессов |
| communicator | Именованная группа; MPI_COMM_WORLD — все процессы запуска |
| tag | Целое — метка типа сообщения между одной парой процессов |
OpenMP
| Термин | Смысл |
|---|---|
| fork-join | Главный поток создаёт команду потоков на регион, затем ждёт их |
| reduction | Частичные результаты потоков сводятся в одно значение |
| barrier | Точка, где все потоки ждут друг друга |
Что запомнить
Раздел "Параллельные вычисления" закрывает пробел между "железом с многими ядрами" и осознанным построением параллельных программ.
Архитектура и системы
- Флинн (SISD/SIMD/MIMD) задаёт рамку — data-parallel (GPU, AVX) vs независимые потоки (OpenMP, MPI).
- Shared vs distributed memory определяет API: потоки в одном процессе или сообщения между узлами.
- NUMA, кластеры, GRID — от одного сервера до метакомпьютинг с разной ценой коммуникации.
Модели и формализация
- PRAM, message passing, SPMD — абстракции для оценок и переноса алгоритмов.
- Граф алгоритма и матрица следования — кто с кем несовместим; основа расписания.
- Информационный граф, EST/LST, критический путь — нижняя граница времени и pmin.
- Сети Петри — ресурсы, конфликты, bounded buffers.
Производительность
- Амдаль — потолок из-за последовательной доли f.
- Густафсон-Барсис — рост задачи вместе с машиной.
- Strong / weak scaling, efficiency, конвейерный throughput.
Практика
- Data vs task parallelism, блочная декомпозиция, halo, first-touch.
- Матричное умножение — эталон для BLAS/MPI/GPU; matvec и scan — ступени к matmul.
- Метод Гаусса — этапные барьеры и broadcast pivot; контраст с matmul.
- История HPC — рост объёма данных определяет спрос на параллелизм.
- OpenMP, MPI, профилирование — код и отладка на практике.
- Профилирование, минимизация barriers, overlap compute/comm.
Связь с другими разделами
| Тема | Куда идти дальше |
|---|---|
| Потоки и IPC | 4.05 Асинхронность |
| Железо, SIMD, NUMA | 1.08 Как работает компьютер |
| OpenMP / MPI в коде | Fortran 811 |
| Сложность алгоритмов | 4.01 Анализ эффективности |
Параллелизм — не самоцель: измеряйте speedup, проверяйте корректность на p = 1 и документируйте предположения о данных и топологии.
Куда идти дальше
Полный маршрут — на странице о разделе.
Проверьте себя: Чек-лист самопроверки.