Когерентность кэша

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

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

Когерентные кэши: значение во всех копиях кэшей одинаково.

Обзор

В многопроцессорной системе с общей памятью и отдельной кэш-памятью для каждого процессора возможно иметь много копий общих данных: одну копию в основной памяти и одну в локальном кэше каждого процессора, который запросил ее. Когда одна из копий данных изменяется, другие копии должны отражать это изменение. Согласованность кэша — это дисциплина, которая гарантирует, что изменения значений общих операндов (данных) своевременно распространяются по всей системе. ^[1]

Ниже приведены требования к согласованности кэша: ^[2]

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

Теоретически, когерентность может быть выполнена на уровне гранулярности загрузки/сохранения . Однако на практике она обычно выполняется на уровне гранулярности блоков кэша. ^[3]

Определение

Согласованность определяет поведение операций чтения и записи по одному адресу. ^[2]

Один из типов данных, которые одновременно хранятся в разных кэш-памяти, называется когерентностью кэша или, в некоторых системах, глобальной памятью.

В многопроцессорной системе предположим, что более одного процессора кэшируют копию ячейки памяти X. Для достижения согласованности кэша необходимы следующие условия: ^[4]

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

Вышеуказанные условия удовлетворяют критериям Write Propagation, необходимым для когерентности кэша. Однако они недостаточны, поскольку не удовлетворяют условию Transaction Serialization. Чтобы лучше проиллюстрировать это, рассмотрим следующий пример:

Многопроцессорная система состоит из четырех процессоров - P1, P2, P3 и P4, все из которых содержат кэшированные копии общей переменной S, начальное значение которой равно 0. Процессор P1 изменяет значение S (в своей кэшированной копии) на 10, после чего процессор P2 изменяет значение S в своей собственной кэшированной копии на 20. Если мы обеспечим только распространение записи, то P3 и P4 наверняка увидят изменения, внесенные в S P1 и P2. Однако P3 может увидеть изменение, внесенное P1, после того, как увидит изменение, внесенное P2, и, следовательно, вернуть 10 при чтении в S. P4, с другой стороны, может увидеть изменения, внесенные P1 и P2 в том порядке, в котором они были сделаны, и, следовательно, вернуть 20 при чтении в S. Процессоры P3 и P4 теперь имеют несогласованное представление памяти.

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

Записи в одно и то же местоположение должны быть упорядочены. Другими словами, если местоположение X получило два разных значения A и B в этом порядке от любых двух процессоров, процессоры никогда не смогут прочитать местоположение X как B, а затем прочитать его как A. Местоположение X должно быть видно со значениями A и B в этом порядке. ^[5]

Альтернативное определение когерентной системы осуществляется через определение модели памяти последовательной согласованности : «система последовательной согласованности кэша должна выполнять загрузку и сохранение всех потоков в одну ячейку памяти в общем порядке, который учитывает порядок программы каждого потока». ^[3] Таким образом, единственное различие между системой последовательной согласованности кэша и системой последовательной согласованности заключается в количестве адресных ячеек, о которых говорится в определении (одна ячейка памяти для системы последовательной согласованности кэша и все ячейки памяти для системы последовательной согласованности).

Другое определение: «мультипроцессор является кэш-консистентным, если все записи в одну и ту же область памяти выполняются в некотором последовательном порядке». ^[6]

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

Механизмы когерентности

Два наиболее распространенных механизма обеспечения согласованности — это снупинг и основанный на каталогах , каждый из которых имеет свои преимущества и недостатки. ^[7] Протоколы, основанные на снупинге, как правило, быстрее, если доступна достаточная пропускная способность , поскольку все транзакции представляют собой запрос/ответ, видимый всеми процессорами. Недостатком является то, что снупинг не масштабируется. Каждый запрос должен транслироваться на все узлы в системе, а это означает, что по мере увеличения системы размер (логической или физической) шины и предоставляемая ею пропускная способность должны расти. Каталоги, с другой стороны, имеют тенденцию иметь более длительные задержки (с 3-х сквозным запросом/пересылкой/ответом), но используют гораздо меньшую пропускную способность, поскольку сообщения передаются по принципу точка-точка, а не транслируются. По этой причине многие из более крупных систем (>64 процессоров) используют этот тип согласованности кэша.

Слежка

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

Для механизма слежки фильтр слежки уменьшает трафик слежки, поддерживая множество записей, каждая из которых представляет строку кэша, которая может принадлежать одному или нескольким узлам. Когда требуется замена одной из записей, фильтр слежки выбирает для замены запись, представляющую строку кэша или строки, принадлежащие наименьшему количеству узлов, как определено из вектора присутствия в каждой из записей. Временной или другой тип алгоритма используется для уточнения выбора, если более чем одна строка кэша принадлежит наименьшему количеству узлов. ^[9]

На основе каталога

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

Распределенные системы общей памяти имитируют эти механизмы, пытаясь сохранить согласованность между блоками памяти в слабосвязанных системах. ^[10]

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

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

Протокол должен реализовывать основные требования к согласованности. Он может быть адаптирован для целевой системы или приложения.

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

Распространение записи в протоколах слежения может быть реализовано одним из следующих методов:

Запись-аннулирование: Когда обнаруживается операция записи в место, копия которого имеется в кэше, контроллер кэша делает недействительной собственную копию отслеженного места памяти, что заставляет считывать из основной памяти новое значение при следующем доступе. ^[4]
Запись-обновление: Когда обнаруживается операция записи в область, копия которой имеется в кэше, контроллер кэша обновляет собственную копию отслеживаемой области памяти новыми данными.

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

Однако масштабируемость является одним из недостатков широковещательных протоколов.

Для поддержания когерентности были разработаны различные модели и протоколы, такие как MSI , MESI (он же Illinois), MOSI , MOESI , MERSI , MESIF , write-once , Synapse, Berkeley, Firefly и Dragon protocol . ^[1] В 2011 году ARM Ltd предложила AMBA 4 ACE ^[11] для управления когерентностью в SoC . Спецификация AMBA CHI (Coherent Hub Interface) ^[12] от ARM Ltd , которая принадлежит к группе спецификаций AMBA5, определяет интерфейсы для подключения полностью когерентных процессоров.

Смотрите также

Ссылки

^ ab E. Thomadakis, Michael (2011). Архитектура процессора Nehalem и платформ Nehalem-EP SMP (PDF) . Техасский университет A&M. стр. 30. Архивировано из оригинала (PDF) 2014-08-11.
^ ab Yan, Solihin. Основы параллельной многоядерной архитектуры . OCLC 884540034.
^ ab Sorin, Daniel J.; Hill, Mark D.; Wood, David Allen (2011-01-01). Учебник по согласованности памяти и согласованности кэша . Morgan & Claypool Publishers. OCLC 726930429.
^ abc Паттерсон и Хеннесси. Организация и проектирование компьютеров - 4-е издание . ISBN 978-0-12-374493-7.
^ Неупане, Махеш (16 апреля 2004 г.). "Кэш-когерентность" (PDF). Архивировано из оригинала (PDF) 20 июня 2010 г.
^ Steinke, Robert C.; Nutt, Gary J. (2004-09-01). «Единая теория согласованности общей памяти». J. ACM . 51 (5): 800–849. arXiv : cs/0208027 . doi :10.1145/1017460.1017464. ISSN 0004-5411. S2CID 3206071.
^ Паттерсон, Дэвид А.; Хеннесси, Джон Л. (1990). Архитектура компьютера: количественный подход . Morgan Kaufmann Publishers. стр. 467–468. ISBN 1-55860-069-8.
^ "Равишанкар, Чинья; Гудман, Джеймс (28 февраля 1983 г.). "Реализация кэш-памяти для нескольких микропроцессоров"" (PDF) . Труды IEEE COMPCON: 346–350 .
^ Расмус Ульфснес (июнь 2013 г.). «Разработка фильтра Snoop для протоколов когерентности кэша на основе Snoop». Архивировано 01.02.2014 на Wayback Machine (PDF). diva-portal.org . Норвежский университет науки и технологий. Получено 20.01.2014.
^ "Лекция 18: Слежка против согласованности на основе каталогов" (PDF) . Berkeley.edu . Получено 14 мая 2023 г. .
^ Kriouile (16 сентября 2013 г.). Формальный анализ спецификации ACE для систем с когерентным кэшем на кристалле. В Formal Methods for Industrial Critical Systems . Springer Berlin Heidelberg. ISBN 978-3-642-41010-9.
^ Ltd, Arm. "AMBA | AMBA 5". Разработчик Arm . Получено 2021-04-27 .

Дальнейшее чтение

Паттерсон, Дэвид ; Хеннесси, Джон (2009). Организация и проектирование компьютеров (4-е изд.). Морган Кауфманн . ISBN 978-0-12-374493-7.
Хэнди, Джим (1998). Книга кэш-памяти (2-е изд.). Морган Кауфманн . ISBN 9780123229809.
Сорин, Дэниел; Хилл, Марк; Вуд, Дэвид (2011). Учебник по согласованности памяти и когерентности кэша (PDF) . Морган и Клейпул. ISBN 978-1608455645. Получено 20 октября 2017 г.
Steinke, Robert C.; Nutt, Gary J. (1 сентября 2004 г.). «Единая теория согласованности общей памяти». Journal of the ACM . 51 (5): 800–849. arXiv : cs/0208027 . doi :10.1145/1017460.1017464. S2CID 3206071.