Кратко об архитектуре
- Современная многопроцессорная система: несколько сокетов (NUMA‑узлов), в каждом — набор ядер (cores). Каждое ядро обычно имеет приватный кэш первого уровня ($L1$) и второго уровня ($L2$); кэш третьего уровня ($L3$) — часто общий для всех ядер сокета. Память распределена по NUMA‑узлам с локальными контроллерами памяти; доступы к удалённой памяти дороже по задержке и полосе пропускания.
- Согласованность кэшей обеспечивается протоколами типа MESI/MOESI (snooping на шине или directory‑based при большом масштабе). Запись в строку кэша приводит к инвалидированию/обновлению у других участников, что вызывает межпроцессорный трафик.
Модель затрат (упрощённо)
- Время доступа к данным можно представить как
$$EAT=p_{L1}{t}_{L1}+(1-p_{L1})p_{L2}{t}_{L2}+(1-p_{L1})(1-p_{L2})p_{L3}{t}_{L3}+\dots$$ где $p_{Li}$ — вероятность попадания в $i$-й уровень, $t_{Li}$ — задержка.
- Запись, вызывающая кооперативную инвалидизацию у $k$ шареров, стоит примерно
$$t_{write}\approx t_{local\_write}+k\cdot t_{inv\_per\_sharer}+t_{remote\_mem}\cdot 1_{\text{write\_to\_mem}}$$
Правила проектирования алгоритмов и структур данных
1) Локальность — главный фактор
- Минимизируйте удалённые доступы: размещайте данные в том NUMA‑узле, где их используют (first‑touch или numa_alloc_onnode). Привязывайте потоки к CPU (cpuset/sched_setaffinity).
- Старайтесь, чтобы горячие данные попадали в $L1/L2$ — уменьшайте рабочее множество.
2) Разделение и шардинг
- Разделяйте глобальные структуры на независимые шардированные подструктуры по NUMA/ядрам. Примеры: таблица хешей с шардированием по ключу, очередь на шард‑базе.
- Локальные операции выполняются без межузловой синхронизации; агрегирование результатов выполняйте периодически (reduce).
3) Минимизация совместного изменения одних и тех же строк кэша (избегать false sharing)
- Кэш‑линия обычно $64$ байта: $\text{CL}=64$.
- Выравнивайте и паддите разные часто записываемые поля на границу $\text{CL}$: например, alignas($\text{CL}$) и добавить padding.
- Вместо одного счётчика на всех — per‑thread/per‑core счётчики с периодическим суммированием.
4) Bulk и batching
- Агрегируйте мелкие изменения в батчи, чтобы снизить частоту синхронизации и сетевого/межпроцессорного трафика (например, буферизация записей, пакетная отправка).
5) Выбор синхронизации, минимизировать микросинхронизацию
- Для read‑heavy — использовать RCU/версионирование/копирование/репликацию; для write‑heavy — локальные блокировки или sharded locks.
- Предпочитайте lock‑free структуры, избегая постоянной модификации одной строки кэша. Используйте атомарные операции экономно и по необходимости.
- Используйте атомики в relaxed/Acquire‑Release режимах, когда это безопасно, и full fences только при необходимости.
6) NUMA‑специфичные методы
- Аллоцируйте память узло‑локально: first‑touch или explicit APIs (numa_alloc_onnode, mbind).
- Держите списки свободных объектов per‑node (freelist per NUMA) и выполняйте операции локально; стыковка/перераспределение — реже.
- Когда данные неизменны — реплицируйте их по узлам, чтобы читать локально.
7) Управление памятью и безопасное удаление
- При lock‑free/RCU/HP/epoch: избегайте немедленного освобождения памяти, чтобы не ломать локальные кэш‑строки у других ядер; используйте epoch‑reclamation или hazard pointers.
- Учитывайте стоимость удалённого free (возможно освобождать память на узле, где она была выделена).
8) Предзагрузка и предсказование
- Используйте software prefetch для последовательных/пределанных доступов, чтобы заполнить $L1/L2$ до использования.
- Упаковка данных в структуры («struct of arrays» vs «array of structs») оптимизирует пространственную локальность в зависимости от паттерна доступа.
Примеры паттернов
- Счётчики: вместо одного global atomic — per‑core counter $c_i$; итог = ${\sum }_i{c}_i$. Это уменьшает число атомарных операций и кэш‑конфликты.
- Очередь/стек: per‑NUMA queue + work‑stealing между узлами только при пустоте (локальный fast path).
- Хеш‑таблица: sharding по ключу + per‑shard lock или lock‑free вариант; редкие глобальные ре‑организации.
Инструменты и измерение
- Измеряйте локальность/latency: perf, numastat, likwid, hwloc.
- Проверяйте показания: частота промахов в L1/L2/L3, межузловой трафик, процент remote RAM accesses.
Краткие практические советы
- Поместите горячие поля в отдельные кеш‑линии, pad поля для записи.
- Делайте first‑touch при инициализации для привязки к узлу.
- Используйте sharding/replication/aggregates для снижения write‑coherence.
- Профилируйте и оптимизируйте по наблюдаемым метрикам, а не по предположениям.
Итог: минимизировать задержки — значит повысить локальность на уровне кэшей и NUMA, уменьшить частоту изменений одних и тех же кэш‑строк и избегать частых межузловых операций; согласованность достигается правильным подбором структур (шардирование, репликация, RCU/epoch, аккуратные атомики) и распределением памяти/потоков по узлам.