Согласованность кеша - Cache coherence

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

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

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

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

Обзор

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

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

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

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

Определение

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

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

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

  1. При чтении, выполняемом процессором P в ячейку X, которое следует за записью того же процессора P в X, при отсутствии записи в X другим процессором, происходящей между инструкциями записи и чтения, выполненными P, 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 и B в таком порядке.[5]

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

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

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

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

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

Слежка

Основная статья: Слежение за автобусом
Впервые представленный в 1983 году,[7] Отслеживание - это процесс, при котором отдельные кэши отслеживают адресные строки для доступа к ячейкам памяти, которые они кэшировали.[4] В запись-недействительность протоколов и протоколы записи-обновления используйте этот механизм.
Для механизма отслеживания фильтр отслеживания уменьшает трафик отслеживания путем поддержания множества записей, каждая из которых представляет строку кэша, которая может принадлежать одному или нескольким узлам. Когда требуется замена одной из записей, фильтр отслеживания выбирает для замены запись, представляющую строку или строки кэша, принадлежащие наименьшему количеству узлов, как определено из вектора присутствия в каждой из записей. Временной или другой тип алгоритма используется для уточнения выбора, если более одной строки кэша принадлежит наименьшему количеству узлов.[8]

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

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

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

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

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

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

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

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

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

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

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

Для поддержания согласованности были разработаны различные модели и протоколы, такие как MSI, MESI (он же Иллинойс), MOSI, MOESI, МЕРСИ, MESIF, однократная запись, Synapse, Беркли, Светляк и Протокол дракона.[1] В 2011, АРМ ООО предложил AMBA 4 ACE[10] для обеспечения согласованности в SoC.

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

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

  1. ^ а б Э. Томадакис, Майкл (2011). Архитектура процессора Nehalem и платформ SMP Nehalem-EP (PDF). Техасский университет A&M. п. 30. Архивировано с оригинал (PDF) на 2014-08-11.
  2. ^ а б Ян, Солихин. Основы параллельной многоядерной архитектуры. OCLC  884540034.
  3. ^ а б Сорин, Дэниел Дж .; Хилл, Марк Д .; Вуд, Дэвид Аллен (01.01.2011). Праймер по согласованности памяти и согласованности кеша. Издательство Morgan & Claypool. OCLC  726930429.
  4. ^ а б c Паттерсон и Хеннесси. Организация и дизайн компьютера - 4-е издание. ISBN  978-0-12-374493-7.
  5. ^ Неупане, Махеш (16 апреля 2004 г.). "Согласованность кеша" (PDF). Архивировано из оригинал (PDF) 20 июня 2010 г.
  6. ^ Стейнке, Роберт С.; Натт, Гэри Дж. (2004-09-01). «Единая теория согласованности общей памяти». J. ACM. 51 (5): 800–849. arXiv:cs / 0208027. Дои:10.1145/1017460.1017464. ISSN  0004-5411.
  7. ^ "Равишанкар, Чинья; Гудман, Джеймс (28 февраля 1983 г.)". Реализация кэша для нескольких микропроцессоров"" (PDF). Труды IEEE COMPCON: 346–350.
  8. ^ Расмус Ульфснес (июнь 2013 г.). «Разработка фильтра отслеживания для протоколов когерентности кэша на основе отслеживания» В архиве 2014-02-01 в Wayback Machine (PDF). diva-portal.org. Норвежский университет науки и технологий. Проверено 20 января 2014.
  9. ^ https://people.eecs.berkeley.edu/~pattrsn/252F96/Lecture18.pdf
  10. ^ Криуиле. Формальный анализ спецификации ACE для кэш-когерентных систем на кристалле. В формальных методах для промышленных критических систем. Springer Berlin Heidelberg. ISBN  978-3-642-41010-9.

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