Параллельные вычислительные процессы — введение

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

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

Параллельные вычисления - многоядерность и масштаб

Современный процессор — это уже десятки ядер, GPU с тысячами потоков, кластеры в дата-центрах и суперкомпьютеры из тысяч узлов. Задачи вроде моделирования климата, обучения нейросетей или расчёта конструкций физически не уложатся в разумное время на одном ядре.

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

Если вы только начинаете

Представьте 1000 одинаковых счётов — например, умножить каждый элемент огромного массива на 2. Один человек пройдёт все 1000 строк подряд. Десять человек разделят массив на 100 строк каждый и закончат примерно в 10 раз быстрее — если им никто не мешает и нет «общей тетради», куда все лезут одновременно.

Параллельное программирование учит:

1. Как делить работу (декомпозиция).
2. Когда делить нельзя (зависимости: шаг B ждёт результат шага A).
3. Как соединять части (синхронизация, обмен данными).
4. Почему 16 ядер редко дают ускорение ×16 (накладные расходы, память, последовательные участки).

В этом разделе сначала — картина мира (статьи 1–4), затем формальный анализ (5–6), законы скорости (7), инженерия и код (8–11).

Параллелизм и асинхронность — разные задачи

Асинхронность — программа продолжает работу, пока ждёт диск или сеть (раздел про асинхронность). Пока один запрос «в пути», обрабатываются другие. Параллелизм — несколько вычислений на CPU/GPU одновременно, чтобы ускорить тяжёлую математику. В одном приложении часто есть и то и другое: веб-сервер асинхронно принимает запросы, а внутри обработки — пул потоков для расчёта.

---

Что такое параллельный вычислительный процесс

Вычислительный процесс — последовательность шагов (операторов), которые превращают входные данные в результат: прочитать файл → посчитать → записать отчёт.

Параллельный процесс — когда несколько шагов идут в одно и то же время на разных ядрах или машинах, но только там, где это разрешено зависимостями.

Зависимость по данным — правило «сначала A, потом B»:

a := x + y      // шаг 1 пишет в a
b := a * 2      // шаг 2 читает a — ждёт шаг 1
c := x - y      // шаг 3 использует только x, y — может идти параллельно с шагом 1

Шаг 3 можно запустить одновременно с шагом 1. Шаг 2 обязан ждать шаг 1. Граф таких связей разбирается в статье 5.

Упрощённая картина:

Последовательно:  A → B → C → D → E        (время = сумма времён шагов)

Параллельно:      A → B ─┬→ C ─→ E
                         └→ D ─┘           (C и D независимы — идут параллельно)

Ключевой вопрос параллельного программирования: какие шаги можно выполнять одновременно, а какие — нет? Ответ даёт анализ зависимостей — об этом подробно в графе алгоритма и временном анализе.

---

Высокопроизводительные вычисления (HPC)

HPC (High-Performance Computing) — область, где критичны максимальная скорость и эффективное использование всей доступной вычислительной мощности: суперкомпьютеры, GPU-кластеры, научные расчёты, рендеринг, ML-тренировки.

HPC — не «магия железа». Это инженерная дисциплина с типичными проблемами:

1. Ограниченный параллелизм задачи

Не каждый алгоритм можно бесконечно дробить. В любой программе есть последовательные участки (инициализация, финальная редукция, синхронизация). Закон Амдала показывает: даже 5 % последовательного кода ограничивает ускорение на бесконечном числе ядер.

Пример: перед расчётом нужно один раз прочитать конфиг с диска (2 секунды), затем час считать на всех ядрах. Сколько ядер вы ни добавьте, эти 2 секунды останутся — потолок ускорения всей задачи ограничен.

2. Пропускная способность памяти (memory wall)

Процессор считает быстрее, чем память успевает отдавать данные. На больших массивах программа **упирается в байты/сек из RAM или между узлами NUMA. Без локальности данных (работа с «своим» куском массива) параллелизм только увеличит трафик и замедлит расчёт.

3. Стоимость коммуникаций

На распределённой памяти (кластер, несколько серверов) процессоры обмениваются данными по сети. Передача 1 МБ может стоить микросекунд–миллисекунд — на фоне наносекундных операций в регистре это огромная цена. Параллельный алгоритм должен минимизировать обмен и крупными блоками передавать данные.

4. Накладные расходы на синхронизацию

Барьеры, мьютексы, атомарные операции, ожидание «всех потоков» — всё это останавливает часть вычислителей. Частые синхронизации «съедают» выигрыш от параллелизма.

5. Балансировка нагрузки (load imbalance)

Если один поток получил в два раза больше работы, остальные ждут его в конце этапа. Неравномерное разбиение данных — частая причина, почему 8 ядер дают ускорение 3×, а не 8×.

6. Масштабируемость и эффективность

Ускорение (speedup) — во сколько раз быстрее, чем на одном процессоре. Эффективность — какая доля мощности реально используется. На 1000 ядрах часто эффективность падает до нескольких процентов — и это нормальная инженерная проблема, а не «плохой код».

7. Сложность отладки

Гонки данных, недетерминированный порядок, «плавающие» баги при изменении числа потоков — параллельные программы сложнее проверять и воспроизводить.

---

Уровни параллелизма

Уровень	Пример	Типичные инструменты
Внутри ядра	SIMD (AVX), конвейер, SMT	Компилятор, intrinsics
Между ядрами одного CPU	OpenMP, std::thread, goroutines	Shared memory
Между CPU одного сервера	NUMA-aware потоки	numactl, affinity
Между узлами кластера	MPI, распределённый TensorFlow	Message passing
GPU / ускорители	CUDA, OpenCL, SYCL	Массовый data-parallel

Подробнее об архитектурах — в классификации и моделях памяти.

---

Параллелизм по задачам и по данным

Два главных стиля (разбор в инженерии алгоритмов):

• Task parallelism (параллелизм по задачам) — разные функции или этапы pipeline выполняются на разных процессорах (как конвейер на заводе).
• Data parallelism (параллелизм по данным) — одна и та же операция применяется к разным элементам данных (умножить каждый элемент массива на 2 — классика для GPU).

Многие HPC-программы сочетают оба подхода: данные режутся на блоки (data), а этапы «прочитать → посчитать → записать» идут pipeline (task).

---

Жизненный цикл параллельной разработки (обзор)

1. Постановка — что считаем, какой размер данных, какой дедлайн, какое железо.
2. Анализ зависимостей — граф алгоритма, что можно параллелить.
3. Выбор модели — shared memory (OpenMP) vs distributed (MPI) vs GPU.
4. Декомпозиция — разбиение данных/задач с учётом локальности.
5. Реализация и синхронизация — минимум блокировок.
6. Оценка — speedup, efficiency, профилирование (узкие места).
7. Масштабирование — проверка на большем числе ядер/узлов.

Каждый этап в разделе раскрывается отдельными статьями.

---

Где это применяется

• Наука и инженерия — CFD, молекулярная динамика, климат (Fortran + MPI на суперкомпьютерах).
• ML и AI — матричные операции на GPU (нейросети).
• Обработка данных — Spark, Dask, параллельные SQL-запросы.
• Игры и графика — многопоточный рендер, job system на нескольких ядрах.
• Криптография и рендер — embarrassingly parallel задачи с минимумом связей.

Даже обычный backend иногда выигрывает от параллелизма (пул воркеров, параллельные тесты), но глубокая теория нужна там, где стоимость ошибки в производительности высока — HPC, real-time симуляции, big data на кластере.

---

Модель Roofline на пальцах

Roofline связывает три величины: пиковые FLOPS процессора, пропускную способность памяти и operational intensity (сколько операций на байт, прочитанный из RAM).

Performance ≤ min( Peak_FLOPS , Bandwidth × Intensity )

Пример (порядок величин): сервер ~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	Память

Вывод: добавить ядра к memory-bound задаче не ускорит её, пока не улучшите локальность (блоки, cache, NUMA). Подробнее — законы производительности.

---

Дерево выбора — OpenMP, MPI, GPU

Задача CPU-bound?
├─ Да → Данные помещаются на одном сервере?
│        ├─ Да → OpenMP / потоки (статья 11)
│        └─ Нет → MPI или MPI+OpenMP (статьи 3, 11)
└─ Массовый однотипный цикл по массиву?
         └─ GPU / SIMD (статьи 2, 9)

Красные флаги перед параллелизацией:

• Последовательная доля f > 10 % без плана её сжать.
• Каждая итерация читает «весь мир» (replicate all-to-all).
• Размер задачи на поток < 10⁴ операций (overhead съест выигрыш).

---

Численный пример — иллюзия параллелизма

Последовательная сумма 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!)

Маленькая задача на многих ядрах упирается в закон Амдала и накладные расходы: создание потоков, барьеры и обмен сообщениями съедают выигрыш, когда полезной работы мало.

---

Что дальше

Тема	Статья
Классификация машин (Флинн, SIMD, конвейер)	2. Архитектуры
Shared / distributed memory, кластеры, GRID	3. Память и системы
Законы Амдала и Густафсона	7. Производительность
Граф и матрица следования	5. Граф алгоритма

---