Многоядерность: согласованность, барьеры, модели памяти

Многоядерность — не архитектурное достижение, а вынужденное отступление. К середине 2000-х рост тактовой частоты упёрся в плотность тепла (Мощность и пределы), а рост ширины внеочередного ядра — в конечность параллелизма реального кода (Суперскалярность и внеочередное исполнение). Оставалось поставить рядом несколько ядер и переложить задачу поиска параллелизма на программиста. Индустрия пошла на это неохотно: до того момента производительность росла без единой строчки изменений в коде.

Программная сторона конкурентности разобрана в обзорной главе про конкурентность и параллелизм и в языковых треках. Здесь мы разбираем ровно то, что происходит в железе: почему два ядра могут увидеть разный порядок событий, что физически делает барьер, во сколько тактов обходится атомарная операция и откуда берётся предел масштабирования, из-за которого добавление ядер иногда ухудшает результат.

Когерентность и согласованность — разные вещи

Это первое место, где ломается разговор, потому что по-русски оба слова звучат похоже, а по-английски (coherence и consistency) их регулярно путают даже в документации.

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

Согласованность (модель памяти) — свойство отношений между разными адресами. Она отвечает на вопрос: «если ядро записало сначала X, потом Y, в каком порядке эти записи станут видны другому ядру?» Ответ: зависит от архитектуры, и почти нигде он не совпадает с наивным ожиданием.

Разница принципиальна. Когерентность — деталь реализации, программе не видная. Согласованность — часть контракта ISA, программе видная напрямую, и код, корректный на одной архитектуре, на другой ломается.

Почему порядок ломается: физические причины

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

Буфер записи (store buffer). Записи не идут прямо в кэш: они складываются в буфер, чтобы ядро не ждало получения строки в эксклюзивное владение. Собственные чтения ядра проверяют буфер и видят свои записи, а чужие — нет, пока запись не выйдет в кэш. Отсюда единственная перестановка, разрешённая моделью TSO: запись может быть отложена относительно последующего чтения.

Внеочередное исполнение чтений. Ядро выпускает загрузки в порядке готовности адресов, а не в порядке программы. С точки зрения соседнего ядра чтения происходят как попало.

Спекуляция. Чтения выполняются до разрешения предшествующих переходов; при подтверждении предсказания результат остаётся, и наблюдаемый снаружи порядок сдвигается.

Иерархия и топология. В многоядерном кристалле сообщения когерентности идут по кольцу или сетке разными путями, и два ядра могут получить уведомления в разном порядке.

Компилятор. Отдельный и не менее сильный источник: он переставляет обращения к памяти, держит значения в регистрах, устраняет «лишние» чтения. Барьеры нужны и на этом уровне тоже.

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

Классический пример: два ядра видят разное

Каноническая проверка модели памяти — «буферизация записей» (store buffering). Обе переменные изначально нули.

// Ядро 1                    // Ядро 2
x = 1;                       y = 1;
r1 = y;                      r2 = x;

Вопрос: может ли получиться r1 == 0 && r2 == 0? При последовательной согласованности — нет: хотя бы одна из записей обязана произойти раньше обоих чтений. На реальном железе — да, и это наблюдается на x86-64 тоже, потому что перестановка «запись затем чтение» разрешена даже строгой моделью TSO.

Второй классический пример — «передача сообщения» (message passing), и вот он уже различает архитектуры:

// Ядро 1: подготовить данные и поднять флаг
data = 42;
ready = 1;

// Ядро 2: дождаться флага и прочитать данные
while (ready == 0) { }
printf("%d\n", data);   // гарантированно 42?

• На x86-64 порядок «запись затем запись» сохраняется, порядок «чтение затем чтение» тоже, поэтому аппаратно этот код сработает. Но компилятор всё равно вправе всё переставить или выкинуть цикл ожидания целиком, если переменные не атомарные.
• На ARM, RISC-V, Power аппаратура вправе переставить и записи, и чтения. Ядро 2 может увидеть ready == 1 и при этом старое значение data. Программа сломается, причём редко и невоспроизводимо.

Именно поэтому ошибки такого рода «работают на моей машине» и всплывают через полгода на другой архитектуре. Классический разбор подобных примеров (litmus tests) — в работе группы Питера Сьюэлла по формализации моделей памяти x86 и ARM.

Модели памяти живых архитектур

Читать таблицу нужно так: чем больше «да», тем слабее модель и тем больше свободы у реализации. Слабая модель — не небрежность, а осознанный размен:

• Строгая модель дешевле для программиста, дороже для железа. Чтобы сохранять порядок, ядру приходится ограничивать буфер записи, отслеживать порядок завершения обращений и откатывать спекулятивные чтения, если сосед успел записать в тот же адрес раньше.
• Слабая модель дешевле для железа, дороже для программиста. Барьеры расставляются явно, и там, где они не нужны, ничего не платится. Для энергоэффективных ядер это существенный выигрыш.

RISC-V формализовал свою модель (RVWMO) в самой спецификации, с математическим определением допустимых исполнений, — редкий случай, когда модель памяти описана строго, а не как список примеров. Это прямое следствие тридцати лет опыта, когда неформальные описания приводили к тому, что железо, компилятор и программисты расходились в понимании контракта (Система команд).

Барьеры: что они делают физически

Барьер (fence, memory barrier) — инструкция, запрещающая определённые перестановки. Важно понимать, что барьер ничего не отправляет и не «сбрасывает кэш» — это самое распространённое заблуждение. Он останавливает конвейер в отношении определённого класса обращений, пока не выполнится нужное условие.

Классификация по тому, что упорядочивается:

StoreLoad дороже остальных потому, что требует фактически дождаться опустошения буфера записи, а это единственная операция, которую ядро не может перекрыть полезной работой. Порядок стоимости на ядрах общего назначения 2020-х — десятки тактов при отсутствии конкуренции и намного больше при активной работе соседей.

Как это выглядит в разных ISA:

# x86-64: модель TSO уже даёт все порядки кроме StoreLoad,
# поэтому нужен ровно один барьер — и то не всегда явный
mfence                  # полный барьер, включая StoreLoad
lock addl $0, (%rsp)    # исторический более дешёвый эквивалент: любая lock-операция
                        # является полным барьером как побочный эффект

# AArch64: барьеры параметризованы направлением и областью видимости
dmb ishld               # упорядочить чтения, область — внутренняя разделяемая
dmb ish                 # полный барьер внутри домена когерентности
dsb ish                 # сильнее: дождаться завершения, а не только упорядочения
# плюс инструкции с встроенным порядком, обычно дешевле явных барьеров:
ldar w0, [x1]           # чтение с семантикой acquire
stlr w0, [x1]           # запись с семантикой release

# RISC-V: один барьер с явным указанием, что упорядочивается
fence rw, rw            # полный: предшествующие чтения и записи до последующих
fence r, r              # только чтения
fence w, w              # только записи
fence.tso               # эмуляция модели TSO целиком

Обратите внимание на строки ldar и stlr: современный подход — не отдельный барьер рядом с обычной операцией, а обращение с встроенным порядком. Это дешевле, потому что ограничение локально: упорядочивается конкретная операция, а не вся граница. Отсюда и терминология acquire/release, которая пришла в языковые модели памяти.

Атомарные операции и их цена

Барьер упорядочивает, но не делает операцию неделимой. Для «прочитать, изменить, записать» нужны отдельные механизмы, и их два семейства.

Готовые атомарные инструкции. Одна инструкция выполняет всю последовательность: сравнение с обменом, атомарное прибавление, обмен. Так устроены lock-инструкции x86 и расширение A в RISC-V (amoadd, amoswap, amoor).

Пара «загрузка с резервированием — условная запись» (LL/SC): lr/sc в RISC-V, ldxr/stxr в AArch64. Первая инструкция читает значение и ставит метку на строку; вторая записывает только если метка цела, иначе сообщает о неудаче, и цикл повторяется.

# RISC-V: атомарный инкремент через LL/SC — так строится любая операция,
# для которой нет готовой инструкции
.retry:
    lr.w    t0, (a0)         # загрузка с резервированием
    addi    t1, t0, 1
    sc.w    t2, t1, (a0)     # условная запись: t2 = 0 при успехе
    bnez    t2, .retry       # кто-то вклинился — начинаем заново

# То же самое одной инструкцией, если есть расширение A
    li      t1, 1
    amoadd.w t0, t1, (a0)    # t0 получает старое значение

Разница инженерная, а не стилистическая. Готовые инструкции компактны и не могут «живо блокироваться» (livelock), но их набор фиксирован. LL/SC универсальна — на ней собирается любая операция, включая сложные, — но требует аккуратности: между lr и sc нельзя делать почти ничего, иначе резервирование слетит, и цикл никогда не завершится.

Сколько это стоит на самом деле

Цена атомарной операции определяется не самой инструкцией, а состоянием строки кэша, в которую она пишет.

Последняя строка — самая важная и самая недооценённая. При конкуренции нескольких ядер за один счётчик возникает «перебрасывание строки» (cache line ping-pong): каждое ядро получает строку, делает одну операцию и отдаёт её следующему. Пропускная способность такого счётчика не растёт с числом ядер, а падает.

Диаграмма читается как список компромиссов. Универсальное лекарство от правого верхнего угла ровно одно: уменьшить количество общего изменяемого состояния. Шардирование счётчиков по ядрам с редким суммированием, локальные буферы с пакетной отдачей, распределение работы без общей очереди — всё это работает не потому, что «меньше блокировок», а потому что меньше строк кэша ходит между ядрами.

Не забываем и про ложное разделение, разобранное в главе 09: переменные разных потоков, случайно попавшие в одну строку, дают ровно ту же деградацию без всякой логической конкуренции.

От аппаратной модели к языковой

Писать код под конкретную аппаратную модель нельзя: программа переносима, а модели разные. Поэтому языки определяют свою модель памяти, а компилятор отображает её в инструкции целевой платформы.

Отсюда наблюдение, которое многих удивляет: на x86-64 acquire и release почти бесплатны — они запрещают только компиляторные перестановки, потому что аппаратура и так их соблюдает. А seq_cst стоит настоящих тактов. На слабых архитектурах картина другая: каждый уровень выше relaxed стоит инструкций.

Практические правила, одинаковые для всех языков:

1. По умолчанию используйте самый сильный порядок (seq_cst в C++/Rust, volatile в Java, обычные каналы и мьютексы в Go). Он и так не самый дорогой на большинстве платформ, а рассуждать о корректности с ним можно.
2. Ослабляйте только по результатам измерения и только там, где вы можете доказать корректность. Ошибки в relaxed-коде не воспроизводятся в тестах.
3. Никогда не изобретайте блокировки заново. Реализация корректного спинлока с правильными барьерами и стратегией отступления — задача сложнее, чем кажется, и уже решена в стандартных библиотеках.
4. Гонка данных — это неопределённое поведение, а не «иногда неверное значение». Компилятор вправе исходить из её отсутствия и оптимизировать соответственно (Неопределённое поведение).

Языковая сторона подробно разобрана в главах про конкурентность: Rust, Java, Go, потоки и синхронизация в C.

Топология кристалла и NUMA

Ядра нужно чем-то соединить, и выбор соединения определяет, насколько дорога связь между ними.

• Общая шина — простейший вариант, работает на единицах ядер, дальше не масштабируется: все запросы через одно место.
• Кольцо — каждое ядро связано с соседями, сообщение обходит кольцо. Латентность растёт линейно с числом ядер; хорошо до нескольких десятков.
• Сетка (mesh) — двумерная решётка маршрутизаторов. Латентность растёт как корень из числа узлов, площадь и энергия — заметно.
• Кроссбар — все со всеми, минимальная латентность, площадь растёт квадратично. Годится для небольших групп ядер внутри кластера.

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

NUMA — та же идея на уровне платформы. У каждого сокета своя память; доступ к чужой идёт через межпроцессорную связь и стоит дороже — порядок в полтора-два раза по латентности и заметно хуже по пропускной способности. Практика:

# Что за топология под вами: узлы, расстояния, распределение памяти
numactl --hardware
lstopo-no-graphics --of console

# Запустить процесс, привязав его к одному узлу целиком
numactl --cpunodebind=0 --membind=0 ./prog

# Посмотреть, сколько обращений идёт к чужому узлу
numastat -p $(pgrep prog)

Правило по умолчанию для многосокетной машины: поток и его данные должны жить на одном узле. Linux по умолчанию выделяет страницу на узле того потока, который к ней первым обратился (политика first-touch) — отсюда классический приём: инициализировать массив тем же потоком, который потом будет с ним работать, а не одним потоком в начале программы.

Предел масштабирования: почему ядер иногда слишком много

Закон Амдала даёт верхнюю границу: если доля последовательной части s, ускорение на n ядрах не превысит 1 / (s + (1 - s) / n). При s = 0.05 потолок — двадцать раз, сколько ядер ни добавляй.

Но реальность хуже: закон Амдала предполагает, что параллельная часть масштабируется идеально. На деле есть ещё стоимость согласования, которая растёт с числом участников. Универсальный закон масштабируемости (Нил Гюнтер) добавляет этот член:

C(n) = n / (1 + a·(n − 1) + b·n·(n − 1))

n — число ядер или потоков
a — доля работы, требующей сериализации (как у Амдала)
b — коэффициент когерентности: стоимость согласования между парами участников

При b > 0 кривая имеет МАКСИМУМ: после некоторого n производительность падает.

"""Универсальный закон масштабируемости: где находится максимум.

Сложность: O(n_max) по времени, O(1) по памяти — просто перебор точек.
Числа иллюстративные: цель — показать форму кривой, а не предсказать вашу систему.
"""

def usl(n: int, a: float, b: float) -> float:
    """Относительная пропускная способность при n параллельных исполнителях."""
    return n / (1.0 + a * (n - 1) + b * n * (n - 1))


def найти_максимум(a: float, b: float, n_max: int = 256) -> tuple[int, float]:
    лучший_n, лучшее = 1, usl(1, a, b)
    for n in range(2, n_max + 1):
        v = usl(n, a, b)
        if v > лучшее:
            лучший_n, лучшее = n, v
    return лучший_n, round(лучшее, 2)


сценарии = {
    "независимые задачи, общего состояния почти нет": (0.02, 0.0000),
    "общий счётчик с редкой записью":                  (0.05, 0.0002),
    "общая очередь под нагрузкой":                     (0.10, 0.0030),
    "горячая строка кэша, пишут все":                  (0.15, 0.0150),
}

for имя, (a, b) in сценарии.items():
    n, s = найти_максимум(a, b)
    print(f"{имя:48} максимум при n = {n:3}, ускорение {s}")

Форма кривой объясняет наблюдение, которое иначе выглядит абсурдным: на 64 ядрах программа может работать медленнее, чем на 16. Причина не в «плохих ядрах», а в том, что при b > 0 каждая новая пара участников добавляет квадратично растущий объём согласования — то самое перебрасывание строк кэша.

Как определить свои a и b: измерить пропускную способность на 1, 2, 4, 8, … потоках и подогнать кривую. Если подгонка даёт заметное b, дальнейшее добавление ядер бессмысленно до устранения общего состояния. Это гораздо более полезная метрика, чем «загрузка CPU 100%» (Производительность конкурентного кода).

Гетерогенные ядра и что об этом должна знать ОС

Современный многоядерный кристалл всё чаще неоднороден: несколько крупных ядер с широким внеочередным исполнением и несколько компактных энергоэффективных. Формально они реализуют одну ISA, но с оговорками, которые ломают наивные предположения:

• Производительность на такт различается в разы, поэтому измерение времени в тактах теряет смысл при миграции потока между кластерами.
• Наборы расширений могут не совпадать, и тогда поток, начавший исполнять векторную инструкцию на большом ядре, не сможет продолжить на малом. Практическое решение индустрии — требовать одинаковый набор расширений во всех ядрах одного кристалла; исторические попытки нарушить это правило заканчивались отключением расширения целиком.
• Планировщик ОС обязан знать топологию: какие ядра быстрые, какие делят кэш, какие делят физическое ядро через SMT. Без этого поток с жёстким требованием по задержке может оказаться на энергоэффективном ядре (Процессы и планирование).

Как измерить взаимодействие ядер

# Ложное разделение и когерентный трафик: события зависят от платформы
perf stat -e cache-misses,cycles,instructions ./prog
perf c2c record ./prog && perf c2c report     # прямо показывает строки с конфликтом между ядрами

# Сколько времени уходит на ожидание блокировок
perf lock record ./prog && perf lock report

# Привязка и топология: кто где исполняется
taskset -c 0-7 ./prog
lstopo-no-graphics --of console
cat /sys/devices/system/cpu/cpu0/topology/{core_id,physical_package_id,thread_siblings_list}

# Масштабируемость: снять кривую пропускной способности по числу потоков
for t in 1 2 4 8 16 32; do ./bench --threads=$t; done

Инструмент perf c2c (cache-to-cache) заслуживает отдельного упоминания: он показывает конкретные строки кэша и конкретные строки исходного кода, из-за которых данные ходят между ядрами. Для диагностики ложного разделения это самый прямой путь.

Что это значит для кода

1. Минимизируйте общее изменяемое состояние — это единственная стратегия, которая масштабируется. Всё остальное лишь уменьшает константу.

2. Разделяйте по строкам кэша то, что пишут разные потоки. Паддинг и выравнивание на 64 байта — дешёвая страховка от ложного разделения.

3. Считайте локально, объединяйте редко. Один атомарный инкремент на тысячу операций вместо тысячи инкрементов меняет поведение системы качественно, а не количественно.

4. Не полагайтесь на «оно работает на x86». Модель TSO прощает ошибки, которые слабые модели не прощают. Если код должен переноситься, проверяйте его на слабой архитектуре или инструментами моделирования.

5. Атомарные операции — не бесплатная замена блокировкам. Цикл CAS под высокой конкуренцией может быть хуже мьютекса: он сжигает такты на повторные попытки, тогда как мьютекс отдаёт ядро другому потоку.

6. Привязывайте потоки и память на NUMA-машинах. Это часто даёт больше, чем любая правка алгоритма.

7. Измеряйте кривую масштабирования, а не одну точку. Ответ «на скольких ядрах запускать» находится в максимуме кривой, и он редко совпадает с «на всех».

Типичные заблуждения

«Барьер сбрасывает кэш». Нет. Барьер запрещает перестановки. Кэш он не трогает — данные и так когерентны.

«volatile в C делает переменную потокобезопасной». Не делает. volatile в C и C++ запрещает компилятору кэшировать значение в регистре, но не даёт ни атомарности, ни барьеров. Для многопоточности нужны атомарные типы. (В Java значение слова другое: там volatile действительно задаёт порядок.)

«Атомарная операция быстрая, ведь это одна инструкция». Её стоимость определяется состоянием строки кэша, а не длиной кодирования.

«Когерентность гарантирует, что я увижу свежие данные». Она гарантирует согласованность по одному адресу. Порядок между разными адресами задаёт модель памяти, и без барьеров он может быть любым.

«Больше ядер — больше пропускная способность». Только пока нет общего состояния. При заметном коэффициенте когерентности кривая имеет максимум, за которым идёт спад.

«Мьютекс — это дорого, сделаю без блокировок». Код без блокировок под конкуренцией часто медленнее и почти всегда сложнее в доказательстве корректности. Решать должно измерение.

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

Мини-итог

• Когерентность решает вопрос об одном адресе и обеспечивается железом всегда; согласованность решает вопрос о порядке между адресами и является частью контракта ISA.
• Перестановки возникают из буфера записи, внеочередного исполнения, спекуляции, топологии кристалла и оптимизаций компилятора; корректность требует согласия всех трёх слоёв.
• Модель TSO у x86-64 разрешает единственную перестановку — запись перед последующим чтением; ARM, RISC-V и Power разрешают почти все, зато не платят за то, чего вы не просили.
• Барьеры ничего не сбрасывают: они запрещают перестановки. Самый дорогой класс — StoreLoad, потому что требует опустошения буфера записи.
• Атомарные операции строятся либо готовыми инструкциями, либо парой «загрузка с резервированием — условная запись»; их стоимость определяется состоянием строки кэша, а не самой инструкцией.
• Главный аппаратный источник плохого масштабирования — перемещение строк кэша между ядрами: и явное (общий счётчик), и случайное (ложное разделение).
• Топология кристалла и NUMA делают стоимость связи между ядрами неоднородной; привязка потоков и памяти часто важнее алгоритмических правок.
• Предел масштабирования описывается не только законом Амдала: член согласования делает кривую немонотонной, и у неё есть максимум.

Источники

• V. Nagarajan, D. Sorin, M. Hill, D. Wood. A Primer on Memory Consistency and Cache Coherence, 2-е издание — doi.org/10.2200/S00962ED2V01Y201910CAC049. Основной современный текст по теме.
• P. Sewell et al. x86-TSO: A Rigorous and Usable Programmer’s Model for x86 Multiprocessors. CACM, 2010 — doi.org/10.1145/1785414.1785443.
• L. Maranget, S. Sarkar, P. Sewell. A Tutorial Introduction to the ARM and POWER Relaxed Memory Models — PDF.
• The RISC-V Instruction Set Manual, том I, приложение по модели памяти RVWMO — riscv.org.
• L. Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE ToC, 1979 — определение последовательной согласованности.
• N. Gunther. Guerrilla Capacity Planning — универсальный закон масштабируемости и методика подгонки его параметров по измерениям.
• H. Sutter. The Free Lunch Is Over, 2005 — gotw.ca: статья, зафиксировавшая переход к многоядерности как проблему для разработчиков.
• P. McKenney. Is Parallel Programming Hard, And, If So, What Can You Do About It? — kernel.org: практическая сторона со стороны ядра Linux.
• Документация perf c2c — man7.org: диагностика ложного разделения.

Что дальше

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

Ускорители: GPU, NPU, FPGA, ASIC и когда они оправданы