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

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

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

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

Обзор [ править ]

В многопроцессорной системе с общей памятью с отдельной кэш-памятью для каждого процессора можно иметь много копий общих данных: одна копия в основной памяти и одна в локальном кэше каждого процессора, который ее запросил. Когда одна из копий данных изменяется, другие копии должны отражать это изменение. Согласованность кэша - это дисциплина, обеспечивающая своевременное распространение изменений значений общих операндов (данных) по всей системе. [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 , MERSI , MESIF , протокол однократной записи , Synapse, Беркли, Firefly и Dragon . [1] В 2011 году ARM Ltd предложила AMBA 4 ACE [10] для обеспечения согласованности в SoC .

См. Также [ править ]

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

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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