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

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

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

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

Обзор

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

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

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

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

Определение

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

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

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

При чтении, выполняемом процессором P в ячейку X, которое следует за записью того же процессора P в X, без записи в X со стороны другого процессора между инструкциями записи и чтения, выполненными P, X всегда должен возвращать значение написал П.
При чтении, выполняемом процессором 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. в в том порядке, в котором они были сделаны, и, следовательно, возвращать 20 при чтении в S. P4, с другой стороны, может видеть изменения, сделанные P1 и P2 , Процессоры 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 (интерфейс когерентного концентратора) ^{[ 12 ]} от ARM Ltd , которая принадлежит к группе спецификаций AMBA5, определяет интерфейсы для подключения полностью когерентных процессоров.

См. также

Ссылки

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

[:1-1] Jump up to: ^а ^б Э. Томадакис, Майкл (2011). Архитектура процессора Nehalem и платформ Nehalem-EP SMP (PDF) . Техасский университет A&M. п. 30. Архивировано из оригинала (PDF) 11 августа 2014 г.

[:0-2] Jump up to: ^а ^б Ян, Солихин. Основы параллельной многоядерной архитектуры . OCLC 884540034 .

[:2-3] Jump up to: ^а ^б Сорин, Дэниел Дж.; Хилл, Марк Д.; Вуд, Дэвид Аллен (1 января 2011 г.). Введение в согласованность памяти и согласованность кэша . Издательство Морган и Клейпул. OCLC 726930429 .

[:3-4] Jump up to: ^а ^б ^с Паттерсон и Хеннесси. Компьютерная организация и дизайн - 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 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

v т и Параллельные вычисления
Общий	Распределенные вычисления Параллельные вычисления Массивная параллель Облачные вычисления Высокопроизводительные вычисления Многопроцессорность Многоядерный процессор ГПГПУ Компьютерная сеть Систолический массив
Уровни	Кусочек Инструкция Нить Задача Данные Память Петля Трубопровод
Многопоточность	Временной Одновременный (SMT) Одновременное и гетерогенное Спекулятивный (СпМТ) упреждающий Кооператив Кластерная многопоточная обработка (CMT) Аппаратный разведчик
Теория	Модель ПРАМ PEM-модели Анализ параллельных алгоритмов Закон Амдала Закон Густавсона Экономическая эффективность Метрика Карпа – Флатта Замедлять Ускорение
Элементы	Процесс Нить Волокно Окно инструкций Множество
Координация	Многопроцессорность Согласованность памяти Согласованность кэша Аннулирование кэша Барьер Синхронизация Контрольная точка приложения
Программирование	Потоковая обработка Программирование потоков данных Модели Неявный параллелизм Явный параллелизм Параллелизм Неблокирующий алгоритм
Аппаратное обеспечение	Таксономия Флинна СИСД SIMD Обработка массивов (SIMT) Конвейерная обработка Ассоциативная обработка МИСД МИМД Архитектура потока данных Конвейерный процессор Суперскалярный процессор Векторный процессор Мультипроцессор симметричный асимметричный Память общий распределенный распределенный общий ОДИН НУМА ЕСТЬ Массивно-параллельный компьютер Компьютерный кластер Кластер Беовульф Сетевой компьютер Аппаратное ускорение
API	Атеджи ПХ Способствовать росту Часовня HPX Очарование++ Том Коаррей Фортран ДРУГОЙ Дриада С++ AMP Глобальные массивы GPUОткрыть ИМБ OpenMP OpenCL OpenHMPP OpenACC Параллельные расширения НДС pthreads РафтЛиб РПЦм СКП TBB ЗПЛ
Проблемы	Автоматическое распараллеливание Тупик Детерминированный алгоритм Смущающе параллельно Параллельное замедление Состояние гонки Программная блокировка Масштабируемость Голод
Категория: Параллельные вычисления