Протокол MESI

Протокол MESI — это протокол когерентности кэш-памяти, используемый в многопроцессорных системах для обеспечения согласованности данных, хранящихся в кэшах отдельных процессоров. Он определяет набор состояний, в которых может находиться каждая строка кэша, и правила перехода между ними при выполнении операций чтения и записи. Название протокола образовано от первых букв названий четырёх состояний: Modified (изменён), Exclusive (эксклюзивный), Shared (разделённый) и Invalid (недействительный). Протокол MESI является одним из наиболее распространённых базовых протоколов когерентности и лежит в основе многих современных процессорных архитектур, включая x86 и ARM.

История

Разработка протоколов когерентности кэша стала актуальной с появлением многопроцессорных систем в 1980-х годах. Первые протоколы, такие как MSI (Modified, Shared, Invalid), были предложены для решения проблемы рассогласования данных между кэшами. Протокол MESI был разработан в 1983 году исследователями из Университета Иллинойса в Урбане-Шампейне (в частности, Папамаркосом и Пателем) как усовершенствование протокола MSI. Основным нововведением стало добавление состояния Exclusive, которое позволило сократить количество транзакций на шине при последовательном чтении данных одним процессором. В 1990-х годах протокол MESI был реализован в процессорах Intel Pentium и стал стандартом де-факто для симметричных многопроцессорных систем (SMP). Впоследствии он был расширен до более сложных протоколов, таких как MOESI (добавлено состояние Owned) и MESIF (добавлено состояние Forward), используемых в современных процессорах AMD и Intel соответственно.

Состояния строки кэша

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

Modified (M — изменён)

Строка кэша присутствует только в данном кэше и была изменена (модифицирована) по сравнению с данными в основной памяти. Данные в основной памяти считаются устаревшими (stale). Процессор, владеющий строкой в состоянии Modified, может читать и записывать её без уведомления других процессоров. Перед тем как другой процессор запросит эту строку для чтения или записи, текущий владелец должен записать её обратно в основную память (операция write-back) и перевести строку в состояние Shared или Invalid.

Exclusive (E — эксклюзивный)

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

Shared (S — разделённый)

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

Invalid (I — недействительный)

Строка кэша не содержит актуальных данных. Любая операция чтения или записи по адресу, соответствующему этой строке, вызывает кэш-промах (cache miss) и требует загрузки данных из основной памяти или из другого кэша. Состояние Invalid является начальным состоянием для всех строк кэша после сброса системы.

Правила перехода между состояниями

Переходы между состояниями происходят в ответ на два типа событий: локальные запросы процессора (чтение PrRd, запись PrWr) и запросы от других процессоров, наблюдаемые на шине (чтение BusRd, запись BusRdX, инвалидация BusUpgr). Ниже приведены основные правила переходов для одного процессора (снайпера), наблюдающего шину.

Локальные запросы

• PrRd (чтение): Если строка в состоянии I — происходит кэш-промах. Процессор отправляет запрос BusRd на шину. Если ни один другой кэш не имеет строки в состоянии M, данные загружаются из памяти, строка переходит в состояние E (если нет других копий) или S (если другие кэши имеют копию в S или E). Если другой кэш имеет строку в M, он отдаёт данные и переводит свою строку в S, а запрашивающий процессор получает данные и переводит строку в S.
• PrWr (запись): Если строка в состоянии M или E — запись выполняется без транзакций на шине, строка остаётся в M. Если строка в состоянии S — процессор отправляет запрос BusRdX (чтение с намерением записи) на шину, инвалидируя все копии в других кэшах, и строка переходит в M. Если строка в состоянии I — происходит кэш-промах, процессор отправляет BusRdX, данные загружаются, все копии инвалидируются, строка переходит в M.

Запросы от других процессоров (наблюдение шины)

• BusRd (чтение другим): Если текущая строка в состоянии M — процессор записывает данные обратно в память (write-back) и переводит строку в S. Если в состоянии E — строка переводится в S (так как теперь есть копия). Если в S — остаётся в S. Если в I — без изменений.
• BusRdX (чтение с записью другим): Если текущая строка в состоянии M — процессор записывает данные в память и переводит строку в I. Если в E или S — строка переводится в I (инвалидируется).
• BusUpgr (инвалидация): Если текущая строка в состоянии S — она переводится в I. Если в E или M — такого запроса не происходит (так как владелец уже имеет эксклюзивный доступ).

Применение

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

• Процессоры x86: Начиная с Intel Pentium (1993), протокол MESI (с некоторыми вариациями) используется в процессорах Intel и AMD. В современных многоядерных процессорах он дополнен состояниями Owned (MOESI) для AMD и Forward (MESIF) для Intel.
• Процессоры ARM: Архитектура ARMv8 и более новые поддерживает протокол MESI как часть системы когерентности ACE (AXI Coherency Extensions).
• Встраиваемые системы: В многопроцессорных системах на кристалле (SoC) с несколькими ядрами ARM или RISC-V.
• Серверные системы: В многопроцессорных серверах с несколькими сокетами, где когерентность кэша обеспечивается через протоколы типа QPI (Intel) или HyperTransport (AMD).

Преимущества и недостатки

Преимущества

• Эффективность при последовательном доступе: Состояние Exclusive позволяет одному процессору многократно читать и записывать строку без транзакций на шине, что снижает задержки и нагрузку на межсоединение.
• Простота реализации: Протокол имеет всего четыре состояния и чёткие правила переходов, что упрощает проектирование аппаратных контроллеров.
• Совместимость: Является основой для более сложных протоколов, что обеспечивает обратную совместимость в семействах процессоров.

Недостатки

• Избыточные транзакции при записи в разделённые данные: Если несколько процессоров часто пишут в одну и ту же строку (например, при работе с общими счётчиками), протокол вызывает постоянные инвалидации и перезагрузки, что приводит к эффекту «ложного разделения» (false sharing) и снижению производительности.
• Отсутствие состояния Owned: В протоколе MESI, если строка в состоянии Modified передаётся другому процессору, она обязательно записывается в память, даже если это не требуется. Протокол MOESI решает эту проблему, позволяя строке оставаться изменённой в одном кэше и одновременно разделяться в других.
• Широковещательные запросы: Все запросы на инвалидацию и чтение являются широковещательными, что создаёт нагрузку на шину в системах с большим числом процессоров. Для масштабирования требуются более сложные протоколы с направленными запросами (directory-based).

Интересные факты

• Протокол MESI иногда называют «протоколом Иллинойса» (Illinois protocol) по месту его разработки.
• В процессорах Intel Pentium Pro была впервые реализована поддержка протокола MESI на уровне вторичного кэша (L2), что позволило строить многопроцессорные конфигурации без дополнительных контроллеров.
• Состояние Exclusive является ключевым отличием MESI от более раннего протокола MSI; оно позволяет избежать так называемой «проблемы ложного разделения» в некоторых сценариях, но не устраняет её полностью.
• В современных процессорах Intel (начиная с архитектуры Nehalem) протокол MESI используется в модифицированном виде как часть более сложной системы когерентности, работающей через кольцевую шину (ring bus) или сетку (mesh).

Источники

• Патент US 5140681 A, «Cache coherence protocol for multiprocessor system», 1983.
• Papamarcos, M. S., Patel, J. H. (1984). «A new cache coherence scheme for shared-memory multiprocessors». Proceedings of the 11th Annual International Symposium on Computer Architecture.
• Hennessy, J. L., Patterson, D. A. (2011). «Computer Architecture: A Quantitative Approach», 5th edition. Morgan Kaufmann.
• Intel Corporation (1997). «Pentium Pro Family Developer’s Manual, Volume 3: Operating System Writer’s Guide».
• ARM Limited (2011). «ARM Architecture Reference Manual, ARMv8-A».