Механизм когерентности кэшей

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

История и предпосылки

С развитием многопроцессорных систем в 1980-х годах возникла проблема согласования данных между кэшами. Первые коммерческие многопроцессорные машины, такие как Sequent Balance и Encore Multimax, использовали общую шину для связи между процессорами и памятью, что делало возможным реализацию простых протоколов когерентности. В 1983 году Джеймс Арчбальд и Роберт Баер ввели термин «когерентность кэшей» и формализовали требования к ней. Ключевой вехой стала разработка протокола MESI (Modified, Exclusive, Shared, Invalid) в 1983 году, который стал основой для большинства современных протоколов. В 1990-х годах с ростом числа ядер в одном процессоре механизмы когерентности стали внедряться и в однопроцессорных многоядерных системах, таких как Intel Pentium Pro и AMD K6. В 2000-х годах с появлением многопоточных процессоров и систем на кристалле (SoC) проблема когерентности стала ещё более актуальной, что привело к разработке протоколов для неоднородных архитектур, например, ARM AMBA CHI.

Основные проблемы и требования

Когерентность кэшей решает три фундаментальные проблемы:

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

Для обеспечения когерентности система должна удовлетворять следующим требованиям:

• Согласованность: Любое чтение из ячейки памяти возвращает последнее записанное в неё значение.
• Последовательность: Операции записи в одну и ту же ячейку памяти выполняются в порядке, определённом программой.
• Валидность: Кэш-линия, помеченная как валидная, содержит актуальные данные.

Протоколы когерентности кэшей

Протоколы когерентности определяют набор правил, по которым кэши обмениваются информацией о состоянии своих строк. Они делятся на два основных класса: протоколы на основе отслеживания (snooping) и протоколы на основе каталогов (directory-based).

Протоколы на основе отслеживания (Snooping Protocols)

В протоколах на основе отслеживания каждый кэш-контроллер «прослушивает» (snoops) общую шину или кольцо, по которому передаются все транзакции памяти. Когда один кэш-контроллер выполняет операцию (например, чтение или запись), он транслирует её на шину, и все остальные контроллеры проверяют, не хранят ли они копию запрашиваемой строки. Если да, они выполняют соответствующие действия (например, аннулируют свою копию или предоставляют данные).

Основные протоколы на основе отслеживания:

• MSI (Modified, Shared, Invalid): Простейший протокол. Строка может быть в состоянии Modified (изменена только в этом кэше), Shared (копия есть в нескольких кэшах, данные актуальны) или Invalid (недействительна). При записи в строку, находящуюся в состоянии Shared, все остальные копии аннулируются.
• MESI (Modified, Exclusive, Shared, Invalid): Добавляет состояние Exclusive (копия есть только в этом кэше, данные совпадают с памятью). Это позволяет избежать лишнего оповещения на шине при записи в строку, которая не была скопирована другими кэшами. MESI является стандартом для x86-совместимых процессоров.
• MOESI (Modified, Owned, Exclusive, Shared, Invalid): Добавляет состояние Owned (копия есть в этом кэше, она изменена, но другие кэши могут иметь устаревшие копии). Это позволяет кэшу, владеющему строкой, предоставлять данные другим кэшам без обращения к основной памяти, ускоряя передачу.
• MESIF (Modified, Exclusive, Shared, Invalid, Forward): Используется в процессорах Intel начиная с архитектуры Nehalem. Добавляет состояние Forward, которое указывает, что данный кэш является единственным, кто может предоставить копию строки другим кэшам, что снижает нагрузку на шину при широковещательных запросах.

Преимущества: Простота реализации, низкая задержка для небольших систем (до 4-8 процессоров). Недостатки: Плохая масштабируемость — каждая транзакция транслируется всем кэшам, что создаёт большую нагрузку на шину и ограничивает число процессоров.

Протоколы на основе каталогов (Directory-Based Protocols)

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

Основные протоколы на основе каталогов:

• Полностью ассоциативный каталог: Каждая запись каталога хранит битовую маску, указывающую, какие кэши имеют копию строки. Требует много памяти, но обеспечивает быстрый доступ.
• Ограниченный каталог: Каждая запись каталога хранит только ограниченное число указателей (например, 2-4). Если число кэшей, содержащих копию, превышает лимит, используется широковещательная рассылка. Более экономичен, чем полностью ассоциативный.
• Иерархический каталог: Используется в больших системах с многоуровневой иерархией кэшей. Каталог на каждом уровне хранит информацию о кэшах нижележащего уровня.

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

Классификация механизмов когерентности

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

1. Write-invalidate (Запись с аннулированием): При записи в строку все остальные копии этой строки в других кэшах аннулируются. Это наиболее распространённый подход, используемый в протоколах MESI, MOESI. При следующем чтении аннулированной строки кэш выполняет промах и загружает новую копию.
2. Write-update (Запись с обновлением): При записи в строку все остальные копии этой строки обновляются новым значением. Этот подход реже используется из-за высокой нагрузки на шину, но может быть эффективен в некоторых сценариях (например, при частом чтении обновляемых данных).

Реализация в современных процессорах

В современных процессорах (Intel Core, AMD Ryzen, ARM Cortex) механизмы когерентности реализованы аппаратно на уровне кэш-контроллера. В многоядерных процессорах обычно используется протокол MESI или его расширения (MESIF, MOESI). В системах с несколькими процессорами (многопроцессорные серверы) часто применяются протоколы на основе каталогов, реализованные в чипсете или встроенном контроллере памяти.

Например, в процессорах Intel Core используется протокол MESIF, где состояние Forward позволяет одному кэшу предоставлять данные другим без обращения к памяти. В процессорах AMD Ryzen применяется протокол MOESI. В мобильных процессорах ARM Cortex-A часто используется протокол MOESI с поддержкой когерентности между ядрами и GPU.

Когерентность в неоднородных системах (Heterogeneous Coherence)

С ростом популярности гетерогенных вычислительных систем (например, SoC с CPU, GPU, DSP, NPU) возникла необходимость в когерентности между различными типами ядер. Для этого разработаны протоколы, такие как ARM AMBA CHI (Coherent Hub Interface) и Intel QuickPath Interconnect (QPI). Эти протоколы обеспечивают когерентность между кэшами CPU, GPU и других ускорителей, что позволяет эффективно обмениваться данными без копирования через основную память.

Критика и ограничения

• Сложность реализации: Протоколы когерентности требуют сложной аппаратной логики, что увеличивает площадь кристалла и энергопотребление.
• Проблемы с масштабируемостью: Протоколы на основе отслеживания плохо масштабируются из-за широковещательной рассылки. Протоколы на основе каталогов требуют значительных ресурсов для хранения каталогов.
• Задержки: Каждая операция когерентности (аннулирование, обновление) вносит дополнительную задержку, что может снижать производительность в некоторых сценариях.
• Проблема «ложного разделения» (False Sharing): Когда два процессора работают с разными данными, но эти данные находятся в одной кэш-линии, система когерентности может аннулировать строку при каждом изменении, что приводит к избыточным промахам кэша и снижению производительности.
• Энергопотребление: Аппаратные механизмы когерентности потребляют значительную энергию, особенно в протоколах на основе отслеживания, где каждый кэш-контроллер постоянно прослушивает шину.

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

• Первый протокол когерентности кэшей был реализован в суперкомпьютере Cray X-MP в 1982 году.
• Протокол MESI был разработан в 1983 году группой исследователей из Университета Иллинойса.
• В процессорах Intel Pentium Pro использовался протокол MESI, который стал первым коммерческим протоколом когерентности для x86-архитектуры.
• Современные процессоры могут иметь до 8-12 уровней кэша (L1, L2, L3, L4), каждый из которых участвует в протоколе когерентности.
• В некоторых суперкомпьютерах (например, IBM Blue Gene) используются специальные протоколы когерентности, оптимизированные для работы с тысячами процессоров.

Источники

• Архитектура компьютерных систем. Таненбаум Э., Остин Т. (2017)
• Организация ЭВМ и систем. Паттерсон Д., Хеннесси Дж. (2018)
• Cache Coherence Protocols. David A. Patterson, John L. Hennessy (2011)
• A Primer on Memory Consistency and Cache Coherence. Daniel J. Sorin, Mark D. Hill, David A. Wood (2011)
• Intel 64 and IA-32 Architectures Software Developer’s Manual (2023)