Многопроцессорные и многоядерные системы: когерентность кэш-памяти (протоколы MESI, MOESI).

Многопроцессорные и многоядерные системы: когерентность кэш‑памяти (протоколы MESI, MOESI)

Введение

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

Когерентность кэша (cache coherence) — гарантия того, что:

1. Все ядра видят одинаковые значения для одного адреса памяти.
2. Операции записи одного ядра становятся видимыми другим ядрам в корректном порядке.
3. Нет «старых» или «потерянных» значений из‑за задержек в обновлении кэшей.

В статье рассмотрены:

• причины возникновения проблем когерентности;
• требования к когерентной системе;
• протоколы MESI и MOESI;
• механизмы реализации (snooping, directory);
• примеры работы;
• влияние на производительность.

1. Причины проблем когерентности

1.1. Сценарии несогласованности

• Ядро 1 читает значение A = 42 из памяти и помещает в свой кэш.
• Ядро 2 тоже читает A = 42 и сохраняет в свой кэш.
• Ядро 1 записывает A = 100. Теперь в кэше Ядра 1 — 100, в кэше Ядра 2 — 42, в памяти — ещё 42 (если запись отложена).
• Ядро 2 читает A и получает устаревшее значение 42.

1.2. Источники конфликтов

• Параллельные записи в один адрес.
• Отложенные записи (write‑back кэш).
• Реплицированные данные в нескольких кэшах.
• Задержки распространения сигналов между ядрами и памятью.

2. Требования к когерентной системе

1. Однородность записи (Write Propagation)
   • Результат записи должен стать видимым всем ядрам.
2. Транзакционность записи (Write Serialization)
   • Все ядра наблюдают записи в одном и том же порядке.
3. Согласованность с памятью (Memory Consistency)
   • Порядок видимости операций соответствует модели согласованности (например, sequential consistency).

3. Протоколы когерентности: общие принципы

3.1. Основные механизмы

• Отслеживание (snooping) — каждое ядро «слушает» шины/интерконнекта и реагирует на обращения к своим кэшированным данным.
• Директории (directory‑based) — централизованная таблица, хранящая, какие ядра кэшируют данные.
• Сообщения (messages) — передача команд между кэшами (Invalid, Shared, Exclusive и т. п.).

3.2. Состояния кэш‑строки

Каждая кэш‑строка имеет состояние (state), определяющее её доступность и актуальность. Протоколы используют разные наборы состояний.

4. Протокол MESI

MESI — один из самых распространённых протоколов (используется в x86, ARM). Название отражает 4 состояния:

• M (Modified) — строка изменена (dirty), только в этом кэше; данные в памяти устарели.
• E (Exclusive) — строка свежая, только в этом кэше; можно записывать без оповещений.
• S (Shared) — строка может быть в других кэшах; чтение разрешено, запись требует согласования.
• I (Invalid) — строка не действительна (не содержит актуальных данных).

4.1. Переходы между состояниями

Чтение (Read):

• Если строка в состоянии I — запрос на шину; если кто‑то имеет M/E/S — получаем данные и переходим в S.
• Если строка E или S — читаем локально.
• Если строка M — передаём данные и переходим в S (если другие тоже читают).

Запись (Write):

• Если строка I — отправляем запрос на исключительное владение; получаем данные, переходим в E, затем в M после записи.
• Если строка S — отправляем Invalid‑сообщение другим, переходим в M.
• Если строка E — пишем локально, переходим в M.
• Если строка M — пишем локально (уже модифицирована).

Ответ на запрос другого ядра:

• При запросе на чтение: если M — передаём данные и переходим в S; если E/S — передаём данные.
• При запросе на запись: если M/E/S — переходим в I (Invalid).

4.2. Пример работы MESI

Пусть два ядра (C1, C2) кэшируют строку A:

1. C1 читает A → C1: E.
2. C2 читает A → C1 отправляет данные, C1: S, C2: S.
3. C1 пишет A = 100 → C1 посылает Invalid‑сообщение C2; C1: M, C2: I.
4. C2 снова читает A → C2 запрашивает данные; C1 отправляет 100, C1: S, C2: S.

5. Протокол MOESI

MOESI расширяет MESI состоянием O (Owned), чтобы уменьшить трафик при чтении модифицированных данных.

Состояния:

• M — как в MESI.
• O (Owned) — строка модифицирована и может быть в других кэшах (но только это ядро «владеет» правом записи).
• E — как в MESI.
• S — как в MESI.
• I — как в MESI.

5.1. Преимущества MOESI

• При чтении строки в состоянии M или O ядро‑владелец может передавать данные напрямую, не сбрасывая их в память.
• Снижается число обращений к основной памяти (меньше задержек).
• Особенно полезно для многоядерных систем с общей шиной/интерконнектом.

5.2. Переходы в MOESI

Чтение при M:

• Вместо перехода в S и сброса в память, ядро переходит в O и передаёт данные другому кэшу.

Запись при O:

• Ядро может писать локально (оно «владеет» строкой).

Запрос на запись от другого ядра:

• Если текущее состояние O — ядро сбрасывает данные в память (если нужно) и переходит в I.

5.3. Пример работы MOESI

1. C1 пишет A = 100 → C1: M.
2. C2 читает A → C1 передаёт данные и переходит в O, C2: S.
3. C1 снова пишет A = 200 → C1 пишет локально, остаётся в O.
4. C3 читает A → C1 передаёт 200, остаётся в O, C3: S.
5. C1 записывает A = 300 → локальная запись, O.

Без MOESI на шагах 2 и 4 C1 пришлось бы сбрасывать данные в память и переходить в S, увеличивая трафик.

6. Механизмы реализации

6.1. Snooping (наблюдение)

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

6.2. Directory‑based (директивный)

• Централизованная или распределённая директория хранит, какие ядра кэшируют каждую строку.
• Запросы направляются только заинтересованным ядрам.
• Плюсы: масштабируемость до десятков/сотен ядер.
• Минусы: сложность, дополнительные задержки на запросы к директории.

7. Оптимизации протоколов

1. Write‑invalidate vs Write‑update
   • Write‑invalidate — отправка Invalid‑сообщений (MESI/MOESI).
   • Write‑update — рассылка нового значения всем кэшам (реже используется).
2. Отложенная обработка (deferred actions) — группировка сообщений.