# Как процессоры оптимизируют работу с памятью: от когерентности к консистентности

Источник: https://www.youtube.com/watch?v=nFXWmo9MFiY
Канал: Stanford Online
Опубликовано: 23.09.2024

---

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

## 🔄 Основы когерентности кэша и протокол MSI
[[JUMP:0:05]]

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

Классическое определение когерентной системы памяти включает в себя два фундаментальных условия:

1.  **Порядок операций:** все операции чтения и записи по конкретному адресу памяти, выполненные всеми процессорами, могут быть выстроены в единую последовательную очередь. Этот глобальный порядок должен соответствовать программному порядку (program order), заданному внутри каждого отдельного потока.
2.  **Актуальность значений:** значение, возвращаемое операцией чтения, всегда должно соответствовать результату самой последней записи по этому адресу в рамках общего последовательного порядка.

Для практической реализации такой системы аппаратура должна строго поддерживать два инварианта:

* **Инвариант единственного писателя и множества читателей (SWMR):** доступ к любой строке кэша делится на эпохи. В эпоху чтения-записи (read-write epoch) только один процессор имеет монопольный доступ к строке и может изменять ее. В эпоху «только чтение» (read-only epoch) сразу несколько процессоров могут параллельно читать данные, но никто не имеет права на запись.
* **Инвариант значения данных:** значение, считываемое в любой read-only эпохе, должно быть идентично значению, записанному в самую последнюю read-write эпоху.



Простейшая реализация когерентности на базе сквозной записи (write-through) неэффективна, поскольку каждая запись отправляется на системную шину, мгновенно превращая ее в узкое горлышко производительности. Поэтому современные системы используют кэши с обратной записью (write-back), где данные модифицируются локально, а в метаданных строки выставляется грязный бит (dirty bit). 

Для управления этими состояниями применяется аппаратный протокол **MSI** (Modified, Shared, Invalid), работающий на основе отслеживания шины (snooping). В нем строка кэша может находиться в трех состояниях:

* **Invalid (I):** строка отсутствует в кэше или неактуальна. Любое обращение к ней приводит к промаху (miss).
* **Shared (S):** строка валидна и может присутствовать в кэшах нескольких ядер. Память при этом гарантированно содержит актуальную информацию.
* **Modified (M):** строка изменена и присутствует исключительно в одном кэше в системе. Грязный бит установлен, а копия данных в основной памяти устарела.

Взаимодействие между ядрами происходит через транзакции на системной шине:

* **Bus Read (BusRd):** запрос строки для чтения.
* **Bus Read Exclusive (BusRdX):** запрос строки для последующей модификации, требующий от всех остальных кэшей аннулировать свои копии.
* **Bus Write-Back (BusWB):** вытеснение грязной строки из кэша и перезапись данных в основную память.

## 📊 Пошаговый разбор работы MSI на примере
[[JUMP:15:42]]

Чтобы наглядно продемонстрировал механизмы сериализации транзакций, лектор разбирает пошаговый сценарий работы трех процессоров (P1, P2, P3) с одной переменной X.

1.  **P1 выполняет чтение X:** на шину отправляется транзакция *BusRd*. Строка загружается из основной памяти, переходит в состояние *Shared* в кэше P1, а в остальных кэшах остается в состоянии *Invalid*.
2.  **P3 выполняет чтение X:** на шину снова идет *BusRd*. Данные опять берутся из памяти. Теперь строка находится в состоянии *Shared* одновременно в P1 и P3.
3.  **P3 выполняет запись в X:** процессору требуется эксклюзивное право на модификацию, поэтому генерируется транзакция *BusRdX*. Кэш-контроллер P1, перехватывая эту команду на шине, немедленно переводит свою копию в состояние *Invalid*. Строка в P3 переходит в состояние *Modified*, а данные пишутся локально.
4.  **P1 снова пытается прочесть X:** происходит промах кэша, и P1 инициирует транзакция *BusRd*. Контроллер P3 замечает этот запрос, понимает, что у него находится единственная актуальная копия (состояние *Modified*), и сообщает памяти «придержать ответ». P3 сам отдает актуальные данные из своего кэша на шину (транзакция *BusWB*), обновляя память и переводя свою строку в состояние *Shared*. Кэш P1 также получает эти данные в состоянии *Shared*.
5.  **P1 повторно читает X:** операция завершается мгновенно, так как это чистое попадание (cache hit) в состоянии *Shared*. Никаких транзакций на шину не выводится.
6.  **P3 снова выполняет запись в X:** генерируется транзакция *BusRdX*, аннулирующая копию в P1. Строка в P3 опять переходит в статус *Modified*.

Как подчеркивает лектор, постоянная конкуренция за одну строку кэша между ядрами приводит к эффекту «метания» (thrashing), когда строка циркулирует между кэшами, порождая лавинообразный рост промахов и драматическое падение производительности системы.

## 🚀 Оптимизация протокола: от MSI к MESI
[[JUMP:27:10]]

Базовый протокол MSI имеет очевидный недостаток. Если ядро сначала читает данные (переводя строку в состояние *Shared*), а затем решает совершить запись, ему приходится выполнять операцию обновления (upgrade). Это порождает две последовательные транзакции на шине: сначала *BusRd*, а затем *BusRdX*, даже если ни одно другое ядро в системе этой строкой не интересовалось.

Для устранения этой неэффективности был создан протокол **MESI**, в который добавили четвертое состояние — **Exclusive (E)**. 

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

Теперь, если процессор запрашивает чтение строки, которая больше нигде не закэширована, она сразу переходит из состояния *Invalid* в состояние *Exclusive*. Если затем приложение решает выполнить запись в эту переменную, кэш-контроллер локально переводит строку из состояния *Exclusive* в *Modified* без отправки транзакции *BusRdX* на системную шину. Это экономит пропускную способность и существенно снижает задержки.

## 🕸 Масштабирование систем: каталоги вместо шины
[[JUMP:30:25]]

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

Решением проблемы для современных многоядерных чипов стал отказ от шины в пользу межсоединений типа «кольцо» (ring) или «сетка» (mesh) совместно с использованием **протоколов на основе каталогов (directory-based)**. Вместо трансляции запросов всем подряд, система хранит специальный каталог, который точно знает, какие ядра содержат копии конкретной строки кэша. Это позволяет отправлять сообщения об аннулировании данных точечно (point-to-point).

В качестве примера лектор приводит архитектуру процессоров Intel Core i7, используемых на лабораторных компьютерах класса (Myth machines). 



В этих процессорах ядра связаны кольцевой топологией, а когерентность поддерживается за счет распределенного каталога, привязанного к общему кэшу третьего уровня (L3). Для корректной работы такой схемы кэш L3 спроектирован как **инклюзивный** (inclusive) — любая строка, находящаяся в кэше L2 любого из ядер, обязательно должна дублироваться в L3. 

Каждая строка в L3 снабжается метаданными каталога, которые в простейшем случае можно представить в виде 5 бит:

* Четыре бита присутствия (по одному на каждое из 4 ядер процессора).
* Один грязный бит (dirty bit).

Если строка находится в состоянии *Shared*, в каталоге могут быть выставлены, например, три бита (ядра 0, 1 и 2 хранят копии). При поступлении запроса на запись система посмотрит в каталог и отправит команды инвалидации только этим трем ядрам, не трогая ядро 3. 

Если же строка находится в состоянии *Modified*, будет взведен грязный бит и только один бит конкретного владельца (например, ядра 3). Использование каталогов позволяет успешно масштабировать когерентность до десятков и даже сотен процессорных ядер в рамках одной системы.

## 📉 Архитектура NUMA и цена задержек кэша
[[JUMP:35:20]]

В многопроцессорных системах с несколькими сокетами (разъемами на материнской плате) физическая память становится распределенной. Такая архитектура называется **NUMA** (Non-Uniform Memory Access — неоднородный доступ к памяти). 

Каждому сокету (процессору) выделяется свой локальный модуль оперативной памяти DRAM. Процессор соединен со своей DRAM напрямую высокоскоростными каналами, а к памяти соседнего сокета он вынужден обращаться через межпроцессорное соединение. Из-за этого скорость доступа к локальной и удаленной памяти кардинально различается.



Аппаратные протоколы когерентности скрывают эту сложность от программиста, но за это приходится платить задержками. На примере данных для Intel Core i7 лектор демонстрирует, как усложнение статуса когерентности строки кэша увеличивает время доступа к ней:

* **40 циклов:** задержка при попадании в кэш L3, если строка является неразделяемой (unshared).
* **65 циклов:** задержка, если строка находится в состоянии *Shared*.
* **75 циклов:** задержка доступа, если строка была модифицирована локальным кэшем другого ядра (требуется вмешательство протокола для извлечения данных).

Переход от однопоточного кода к параллельному кардинально меняет распределение промахов в иерархии памяти, смещая их в сторону более медленных уровней с огромными задержками. Для поиска таких проблем лектор рекомендует использовать специализированные утилиты профилирования: **Intel VTune** для процессоров x86 или **Apple Xcode Instruments** для систем на чипах Apple M1.

## ⚠️ Ложное разделение памяти (False Sharing)
[[JUMP:40:43]]

Одной из самых коварных аппаратных проблем для параллельного программиста является **ложное разделение данных** (false sharing). Оно возникает из-за того, что аппаратная когерентность оперирует не отдельными байтами или переменными, а крупными блоками — строками кэша (cache lines).

Лектор демонстрирует классический пример кода, где создается массив счетчиков, в который каждый поток пишет по своему уникальному индексу `ID`:

```c
// Вариант 1: Ложное разделение
int per_thread_counters[NUM_THREADS];

void worker(int thread_id) {
    for (int i = 0; i < ITERATIONS; i++) {
        per_thread_counters[thread_id]++;
    }
}
```

С точки зрения логики программы, потоки абсолютно независимы и не разделяют данные. Однако физически эти целочисленные переменные располагаются в памяти вплотную друг к другу и гарантированно попадают в одну и ту же 64-байтную строку кэша. 

Как только поток 0 инкрементирует свой счетчик, его кэш-контроллер переводит строку в состояние *Modified* и инвалидирует аналогичную строку в кэше потока 1. Когда поток 1 пытается обновить свой счетчик, происходит промах, строка с боем отнимается обратно, инвалидируя копию потока 0. Начинается разрушительный пинг-понг кэш-строки между ядрами.

Эксперимент на 4-ядерной системе показывает, что выполнение этого неоптимизированного кода занимает **14,2 секунды**. Если же применить выравнивание структур (padding), принудительно разнося переменные по разным строкам кэша, время выполнения падает до **4,7 секунды**.

Исторические бенчмарки, созданные в Стэнфорде около 30 лет назад (такие как Radiosity и Radix Sort), наглядно подтверждают эту аппаратную особенность. 

При увеличении размера строки кэша количество истинных промахов (true sharing) снижается благодаря хорошей пространственной локальности. Но в алгоритме *Radiosity* график ложных промахов ползет вверх, а в алгоритме сортировки по разрядам *Radix Sort* наблюдается катастрофический всплеск ложного разделения, полностью нивелирующий все преимущества длинных строк кэша. 

Единственный способ борьбы с этим на программном уровне — искусственное разнесение (spacing) независимых данных в памяти, пусть даже ценой неэффективного расхода адресного пространства.

## 🧠 Консистентность памяти: новые правила игры
[[JUMP:52:52]]

В то время как когерентность кэша заботится о согласованности копий **одного конкретного** адреса памяти, концепция **консистентности памяти (memory consistency)** отвечает на совершенно другой вопрос: в каком порядке разные процессоры видят операции чтения и записи, совершенные по **разным** адресам?

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

Всего существует четыре базовых типа упорядочивания операций над парами различных адресов X и Y:

1.  **Write-to-Read (W→R):** запись по адресу X должна зафиксироваться в памяти до того, как произойдет чтение по адресу Y.
2.  **Read-to-Read (R→R):** первое чтение должно строго предшествовать второму чтению.
3.  **Read-to-Write (R→W):** чтение должно завершиться до совершения последующей записи.
4.  **Write-to-Write (W→W):** первая запись должна строго завершиться до выполнения второй записи.

Чтобы продемонстрировать, насколько неочевидным может быть параллельное исполнение кода, лектор предлагает разобрать простую программу, где исходные значения переменных A и B равны 0:

```
Поток Р0:
A = 1;
print B;

Поток Р1:
B = 1;
print A;
```

Инструкции внутри каждого потока выполняются строго друг за другом (в программном порядке), но на многопроцессорной системе их выполнение во времени может переплетаться произвольным образом. Аудитория предлагает различные варианты вывода программы на экран: `11`, `01`, `10`. Лектор задает ключевой вопрос: допустим ли в реальности исход `00`?

Для анализа стабильности исхода строится граф зависимостей «happens-before». Чтобы оба принта вывели `0`, печать переменной B на процессоре P0 должна произойти строго до того, как процессор P1 запишет в нее единицу (`print B -> B = 1`). Соответственно, печать переменной A на процессоре P1 должна случиться до записи в нее на P0 (`print A -> A = 1`). 

Учитывая внутренний программный порядок (`A = 1 -> print B` и `B = 1 -> print A`), мы получаем замкнутый круговой цикл в графе зависимостей. Поскольку событие не может произойти раньше самого себя, в классическом интуитивном понимании работы памяти результат `00` является физически невозможным.

## ⏱ Последовательная консистентность и наследие Лесли Лампорта
[[JUMP:1:04:45]]

Интуитивные ожидания программиста от поведения памяти описываются строгой математической моделью под названием **последовательная консистентность (Sequential Consistency — SC)**. Эту концепцию в 1976 году сформулировал выдающийся ученый Лесли Лампорт, за что в 2013 году был удостоен Премии Тюринга.

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



Лектор предлагает метафору многопозиционного переключателя (switch metaphor) для визуализации этой модели. Представьте, что между процессорами и памятью стоит вращающийся тумблер. Он случайным образом подключается к одному из ядер, атомарно выполняет одну или несколько его инструкций с памятью, а затем перескакивает на другое ядро. В такой архитектуре получение результата `00` или `10` в рассмотренном ранее примере абсолютно нелегально.

## ⚡ Ослабление моделей памяти и аппаратные барьеры
[[JUMP:1:07:23]]

Если последовательная консистентность так удобна и понятна, почему инженеры практически всех полупроводниковых компаний отказались от нее в реальном железе? Ответ банален — ради производительности.

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

Чтобы скрыть огромные задержки операций записи, инженеры внедрили аппаратный **буфер записи (write buffer)**, располагающийся между процессорным ядром и кэшем. Теперь ядро сбрасывает операцию записи в буфер и, не дожидаясь ее фактического исполнения на уровне кэшей, сразу же приступает к выполнению последующих инструкций чтения. 

Однако появление буферов записи мгновенно разрушает модель последовательной консистентности. Возвращаясь к примеру с переменными А и Б: если оба процессора успели отправить свои записи в локальные буферы и тут же выполнили чтение из кэшей, программа на реальном железе напечатает те самые заветные `00`.

По этой причине современные процессорные архитектуры используют ослабленные (weak) модели консистентности памяти:

* **Total Store Order (TSO):** модель, используемая в архитектуре x86 (Intel/AMD). Она разрешает нарушать только порядок Write-to-Read (чтение может обогнать запись). Все процессоры видят операции записи всех ядер в одном и том же порядке.
* **Partial Store Order (PSO) / Processor Consistency:** модели, допускающие еще большие вольности, где операции записи могут обгонять друг друга.
* **Relaxed Consistency:** максимально расслабленная модель, где аппаратура вообще не гарантирует никакого порядка выполнения инструкций по умолчанию. Именно такая модель применяется в процессорах ARM, которые стоят практически в каждом современном смартфоне.

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

Для восстановления контроля над железом программисты вынуждены использовать специальные аппаратные инструкции — **барьеры памяти, или фенсы (fences)**. Инструкция `fence` заставляет процессор полностью приостановить выполнение команд и дождаться, пока вся цепочка памяти «успокоится» (quiesce). Все операции, стоящие до барьера, гарантированно должны завершиться до того, как процессор перейдет к инструкциям после барьера. Существуют раздельные барьеры на чтение (load fence) и на запись (store fence).

Главное правило безопасного параллельного программирования — **Data Race-Free (DRF)**. Разработчикам категорически запрещено писать программы, содержащие незащищенные, несинхронизированные одновременные обращения к одним и тем же данным со стороны разных потоков, если хотя бы одно из этих обращений является записью. Любые общие переменные должны быть строго обернуты в мьютексы, семафоры или атомики. 

Низкоуровневую работу по расстановке тяжелых, замедляющих систему аппаратных фенсов берут на себя авторы системных библиотек и компиляторов. Прикладному же программисту достаточно просто доверять этим проверенным инструментам, не пытаясь перехитрить расслабленную модель памяти вручную.