Согласованность кэша

Термин компьютерной архитектуры, касающийся данных общих ресурсов

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

Некогерентные кеши: кеши имеют разные значения одного адреса.

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

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

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

Обзор

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

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

Запись распространения

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

Сериализация транзакций

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

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

Определение

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

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

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

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

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

Многопроцессорная система состоит из четырех процессоров — 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 и Б именно в таком порядке. ^[5]

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

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

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

Механизмы согласованности

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

Слежка

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

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

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

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

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

Протоколы согласованности

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

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

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

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

Запись-недействительна

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

Запись-обновление

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

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

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

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

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

• Модель согласованности
• Согласованность на основе каталогов
• Барьер памяти
• Неравномерный доступ к памяти (NUMA)
• Ложный обмен

Рекомендации

1. Э. Томадакис, Майкл (2011). Архитектура процессора Nehalem и платформ Nehalem-EP SMP (PDF) . Техасский университет A&M. п. 30. Архивировано из оригинала (PDF) 11 августа 2014 г.
2. Ян, Солихин. Основы параллельной многоядерной архитектуры . ОСЛК  884540034.
3. Сорин, Дэниел Дж.; Хилл, Марк Д.; Вуд, Дэвид Аллен (1 января 2011 г.). Введение в согласованность памяти и согласованность кэша . Издательство Морган и Клейпул. ОСЛК  726930429.
4. Паттерсон и Хеннесси. Компьютерная организация и дизайн - 4-е издание . ISBN 978-0-12-374493-7.
5. Неупане, Махеш (16 апреля 2004 г.). «Когерентность кэша» (PDF) . Архивировано из оригинала (PDF) 20 июня 2010 года.
6. Стейнке, Роберт С.; Натт, Гэри Дж. (1 сентября 2004 г.). «Единая теория согласованности общей памяти». Дж. АКМ . 51 (5): 800–849. arXiv : cs/0208027 . дои : 10.1145/1017460.1017464. ISSN  0004-5411. S2CID  3206071.
7. Паттерсон, Дэвид А.; Хеннесси, Джон Л. (1990). Архитектура компьютера. Количественный подход . Издательство Морган Кауфманн. стр. 467–468. ISBN 1-55860-069-8.
8. «Равишанкар, Чинья; Гудман, Джеймс (28 февраля 1983 г.). «Реализация кэша для нескольких микропроцессоров»» (PDF) . Труды IEEE COMPCON: 346–350 .
9. Расмус Ульфснес (июнь 2013 г.). «Разработка отслеживающего фильтра для протоколов когерентности кэша на основе отслеживания». Архивировано 1 февраля 2014 г. в Wayback Machine (PDF). diva-portal.org . Норвежский университет науки и технологий. Проверено 20 января 2014 г.
10. «Лекция 18: Отслеживание против согласованности на основе каталогов» (PDF) . Беркли.edu . Проверено 14 мая 2023 г.
11. Криуил (16 сентября 2013 г.). Формальный анализ спецификации ACE для систем на кристалле с когерентным кэшем. В «Формальных методах для промышленных критических систем ». Шпрингер Берлин Гейдельберг. ISBN 978-3-642-41010-9.
12. ООО, Арм. «АМБА | АМБА 5». Разработчик рук . Проверено 27 апреля 2021 г.

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

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