Параллельные вычисления
Shared Memory
16-ядерный CPU выполняет 16 потоков параллельно. Но разделённый счётчик с 16 потоками - медленнее однопоточного. Cache coherence - скрытая стоимость общей памяти. Intel 2007, Nehalem: первый CPU с NUMA (Non-Uniform Memory Access). Память одна - но доступ к локальной памяти в 2 раза быстрее, чем к памяти соседнего процессора. Многопоточность перестала быть симметричной. И ещё: false sharing убивает производительность без единой гонки данных. Два потока пишут в разные переменные - но если эти переменные в одной cache line (64 байта), MESI-протокол вынуждает синхронизировать каждую запись.
- **PyTorch DDP**: gradient sync через NCCL использует shared memory ring buffer между GPU-процессами - zero-copy на 150 МБ батч вместо 600 МБ копирования
- **NumPy/Pandas**: multiprocessing.Pool копирует данные, не шарит - решение через SharedMemory API (Python 3.8+)
- **Python multiprocessing.Queue**: Lock под капотом, при > 8 процессов становится bottleneck из-за cache coherence traffic
- **CUDA kernels**: atomicAdd к глобальной памяти до 10x медленнее локальных операций при высокой конкуренции на одну ячейку
Cache Coherence и MESI-протокол
Каждое ядро имеет собственный L1/L2 кеш. Когда ядро 0 читает переменную `x`, её значение копируется в кеш ядра 0. Когда ядро 1 пишет в `x` - кеш ядра 0 содержит устаревшее значение. Без координации - data race на hardware-уровне. MESI-протокол решает это: каждая cache line помечается состоянием Modified/Exclusive/Shared/Invalid. Запись одним ядром отправляет Invalidation message всем остальным по interconnect-шине. Следующее чтение требует cache miss и fetch из памяти или кеша соседнего ядра.
**Interconnect bandwidth как bottleneck**: при высокой конкуренции на shared переменную, coherence traffic насыщает QPI/Infinity Fabric шину между NUMA-узлами. 16 ядер, каждое делает write к одному счётчику - пропускная способность шины, а не ALU, становится ограничением. Именно поэтому "параллельный" счётчик медленнее однопоточного.
Ядро 0 записало значение в переменную, которая находится в состоянии Shared (есть копии в кешах ядер 1, 2, 3). Что происходит в MESI-протоколе?
Memory Model и Memory Ordering
CPU не выполняют инструкции в порядке записи - они переупорядочивают их для заполнения pipeline. Store buffer задерживает запись в кеш. Invalidation queue откладывает обработку invalidate-сообщений. Результат: другие ядра могут видеть записи в порядке, отличном от программного. Memory model - контракт между программистом и CPU о гарантиях видимости. **Happens-before** - фундаментальное отношение: если операция A happens-before B, то результат A виден при выполнении B. Acquire/release семантика создаёт это отношение: release-запись в точке синхронизации видна acquire-чтению.
**C++ memory_order**: `relaxed` - только атомарность, без ordering. `acquire` - все последующие reads/writes не уходят выше. `release` - все предыдущие reads/writes не уходят ниже. `seq_cst` - полная последовательная консистентность (самое медленное). Python GIL - эквивалент `seq_cst` для всего интерпретатора: только один поток в момент времени, reordering невозможен в принципе.
Поток 1 записывает данные (`data = result`) и затем устанавливает флаг (`flag.store(true, memory_order_release)`). Поток 2 ждёт флаг (`while (!flag.load(memory_order_acquire))`). Что гарантирует пара release/acquire?
False Sharing: незаметный убийца
Cache line - минимальная единица передачи между кешем и памятью: 64 байта на x86. MESI-протокол работает на уровне cache line, не отдельных переменных. Если два потока пишут в разные переменные, но они находятся в одной cache line - каждая запись инвалидирует cache line для другого ядра. Это **false sharing**: потоки не делят логические данные, но делят физическую cache line. Никакой гонки данных нет - и никакой видимой причины для замедления тоже. Performance degradation от 10x до 100x при высокой частоте записи.
**Struct of Arrays vs Array of Structs (SoA vs AoS)**: в ML-задачах часто нужно итерировать по одному полю всех объектов (все веса, все градиенты). AoS - `{w, g, m}[]` - при чтении весов `w` в кеш попадают `g` и `m`, которые не нужны: cache bandwidth тратится впустую. SoA - `{w[], g[], m[]}` - чтение весов использует всю cache line под полезные данные. Для PyTorch: параметры хранятся в contiguous tensors - это SoA на уровне данных.
Два потока работают со структурой `struct { int a; int b; }`. Поток 0 только пишет в `a`, поток 1 только пишет в `b`. Гонки данных нет. Профилировщик показывает 80% времени в cache miss. Причина?
Атомарные операции и Lock-Free алгоритмы
Атомарная операция - неделимая: ни одно другое ядро не может наблюдать промежуточное состояние. CPU предоставляет несколько примитивов: **CAS** (Compare-And-Swap) - если текущее значение равно expected, записать new_value, вернуть true/false; **fetch-add** - атомарный инкремент с возвратом старого значения; **exchange** - атомарная замена. На x86: инструкции `LOCK CMPXCHG`, `LOCK XADD`. На ARM: `LDXR`/`STXR` пара (Load-link/Store-conditional). Lock-free алгоритмы используют CAS в цикле: прочитать текущее, вычислить новое, CAS - если не совпало (кто-то изменил), повторить.
**ABA Problem в lock-free алгоритмах**: CAS проверяет значение, но не версию. Поток читает A, другой поток меняет A -> B -> A, первый поток видит A и считает, что ничего не изменилось - хотя структура данных уже другая. Решения: tagged pointer (версия в старших битах), hazard pointers, RCU (Read-Copy-Update). В production lock-free коде - всегда один из этих механизмов.
Атомарные операции всегда быстрее мьютексов - они же не требуют syscall
Под низкой конкуренцией (мало потоков, редкие конфликты) - атомики быстрее. Под высокой конкуренцией - CAS retry storm создаёт O(N) coherence трафик, мьютекс с парковкой потоков - эффективнее.
Mutex при конкуренции отправляет поток в sleep (futex syscall) - поток не занимает шину retry-ами. Spinlock на CAS держит все неудачные потоки в активном ожидании, каждый retry - cache line invalidation для всех остальных. При 16 потоках на один атомик: 15 потоков непрерывно генерируют coherence трафик ради нулевого прогресса.
Benchmark показывает: при 2 потоках lock-free стек с CAS в 3x быстрее mutex. При 16 потоках - lock-free в 4x медленнее mutex. Почему?
Ключевые идеи
- **Cache coherence (MESI)**: запись одним ядром инвалидирует копии в кешах всех остальных ядер - interconnect bandwidth становится bottleneck при высокой конкуренции
- **Memory ordering**: CPU переупорядочивают инструкции для производительности; acquire/release семантика - минимальный барьер для корректной синхронизации без sequential consistency overhead
- **False sharing**: переменные в одной 64-байтовой cache line синхронизируются как единое целое, даже если потоки пишут в разные поля - `alignas(64)` разносит по разным линиям
- **Atomic vs Lock**: под низкой конкуренцией CAS-based lock-free быстрее mutex; под высокой конкуренцией spinlock на CAS деградирует до O(N) bandwidth waste - выбор зависит от contention profile
Связанные темы
Shared memory - центральная тема, связывающая hardware-архитектуру, OS и параллельное программирование:
- Синхронизация потоков — Mutex и semaphore реализованы через атомарные операции, описанные в этом уроке
- Deadlock и Starvation — Locks для защиты shared memory - источник deadlock при неправильном порядке захвата
- Архитектура процессора — Cache иерархия и store buffer - hardware основа memory ordering
- OS Синхронизация — OS-примитивы синхронизации используют те же CAS-инструкции CPU
- Репликация в распределённых системах — Cache coherence и distributed replication решают одну задачу на разных масштабах
Вопросы для размышления
- NUMA-топология означает, что доступ к 'чужой' памяти в 2 раза дороже. Как это меняет стратегию размещения данных в многопоточном приложении с несколькими NUMA-узлами?
- False sharing можно устранить padding-ом или struct-of-arrays. Но padding увеличивает размер структур. Когда оверхед памяти оправдан, а когда нет?
- Python GIL - 'тяжёлый' memory model: только один поток выполняется в момент времени. Это устраняет false sharing и cache coherence проблемы, но за какую цену? Когда multiprocessing предпочтительнее threading?