Связность на основе каталогов - Directory-based coherence

Связность на основе каталогов это механизм для обработки Согласованность кеша проблема в Распределенная разделяемая память (DSM) a.k.a. Неравномерный доступ к памяти (NUMA). Другой популярный способ - использовать специальный компьютер. автобус между всеми узлами как «общая шина» (также известная как «общая шина»). Системная шина ).[1] Согласованность на основе каталогов использует специальный каталог служить вместо общей шины в протоколах согласования на основе шины. Обе эти конструкции используют соответствующий носитель (например, каталог или шину) в качестве инструмента для облегчения связи между различными узлы, и гарантировать, что протокол согласованности работает должным образом на всех взаимодействующих узлах. В согласованности кэша на основе каталогов это делается с помощью этого каталога для отслеживания состояния всех тайник блоков, статус каждого блока включает в себя согласованность кеша "штат "этот блок есть, и какие узлы совместно используют этот блок в то время, что можно использовать для устранения необходимости трансляция все сигналы ко всем узлам и отправлять их только тем узлам, которые заинтересованы в этом единственном блоке.

Ниже приведены несколько преимуществ и недостатков протокола согласованности кэша на основе каталогов:

  • Масштабируемость: Это одна из самых сильных мотиваций для перехода к дизайну на основе каталогов. Что мы подразумеваем под масштабируемость Короче говоря, насколько хорошо конкретная система справляется с растущим объемом работы, которую она несет ответственность. По этому критерию системы на основе шины не могут работать хорошо из-за ограничений, вызванных наличием общей шины, которую все узлы используют одновременно. Для относительно небольшого количества узлов хорошо подойдут шинные системы. Однако пока количество узлов растет, в этом отношении могут возникнуть некоторые проблемы. Тем более, что только одному узлу разрешено использовать шину одновременно, что значительно снизит производительность всей системы. С другой стороны, при использовании систем на основе каталогов не будет такого узкого места, ограничивающего масштабируемость системы.
  • Простота: Это один из моментов, когда шинная система превосходит. Поскольку структура автобуса сама по себе может служить организатором всего трафика, проходящего через систему, и обеспечивать атомарность всех пройденных сигналов. Таким образом, не будет необходимости прилагать больше усилий для обеспечения атомарности и упорядочения сигналов, как в случае систем на основе каталогов, что приводит к нескольким накладным расходам, возникающим в более позднем дизайне системы при решении таких проблем, как последовательность.

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

История

Идея систем согласования кеш-памяти на основе каталогов зародилась давно. Идея DASH (Dкаталог Аархитектура для SHared-memory) была впервые предложена C.K. Тан[2] в середине 1970-х гг. Однако применение его для согласования кеш-памяти было предложено несколько лет спустя, в частности, в 1978 году, когда исследователи из Стэндфордский Университет предложил первую версию этой системы когерентности, названную Стэнфордский DASH, в газете[3] в котором описана система с трудностями и улучшениями, связанными с такими конструкциями. Помимо этого подхода, было сделано несколько попыток предоставить масштабируемые системы. Например, BBN Бабочка[4] который был представлен в 1985 году, и IBM PR3[5] который был представлен в 1987 году, являются некоторыми примерами масштабируемых многопроцессорные системы. Однако обе эти системы имеют недостаток; Например, у BBN Butterfly нет кешей. Точно так же IBM PR3 не обеспечивает согласованности аппаратного кэша, что ограничивает производительность обеих этих схем, особенно при использовании высокопроизводительных процессоров.[6]

Ограничения других конкурентов упростили выбор систем на основе DASH при разработке систем согласованности кешей и других систем, требующих масштабируемости в узлах на основе кеша. В 1985 году Джеймс Арчибальд[7] и Жан-Лу Баер от Вашингтонский университет опубликовал статью[8] который предлагает более экономичный, расширяемый и модульный вариант подхода «глобального каталога» с точки зрения использования аппаратного обеспечения в проекте.

В 1992 году Дэниел Леноски из Стэнфордского университета опубликовал статью.[9] предлагая усовершенствования в протоколах согласования кеша для систем на основе каталогов. В статье 1996 г.[10] он представил дизайн SGI Origin 2000, семейство серверных компьютеров, использующих согласованность кэша на основе каталогов. Последующие Origin 3000[11] был представлен в июле 2000 года.

Протоколы

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

[12] Обзорная диаграмма схемы согласованности на основе каталогов, показывающая различных участников и сообщения.

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

  • Узел запрашивающего : Этот узел является процессором, который запрашивает чтение / запись блока памяти.
  • Узел каталога : Этот узел хранит информацию о состоянии каждого блока кэша в системе, а запрашивающая сторона направляет свои запросы в узел каталога.
  • Узел владельца: Узел-владелец владеет самым последним состоянием блока кэша, обратите внимание, что каталог может не всегда быть в курсе последних данных.
  • Узел совместного использования: Один или несколько узлов, которые совместно используют копию блока кэша.
Изображение 1: Диаграмма перехода состояний для протокола на основе каталога

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

Узел каталога действует как точка сериализации, и все коммуникации направляются через этот узел для поддержания корректности.

Узел каталога

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

  • Без кеширования (U): Ни один процессор не имеет кэшированных данных, память актуальна.
  • Общий (S): один или несколько процессоров имеют кэшированные данные, память обновлена. В этом состоянии каталог и разделители имеют чистую копию кешированного блока.
  • Эксклюзивный / модифицированный (EM): один процессор (владелец) имеет кэшированные данные; память устарела. Обратите внимание, что каталог не может различить блок, кэшированный в исключительном или измененном состоянии в процессоре, поскольку процессоры могут переходить из эксклюзивного состояния в измененное состояние без какой-либо транзакции шины.

Объяснение перехода между состояниями Справочника Конечный автомат (см. изображение 1) показано ниже в таблице:

Начальное состояниеЗапрос на автобусОтвет / действиеНовое государство
UBusRd или

Автобус RdX

  • Извлечь блок из памяти, поскольку в каталоге есть обновленная копия блока.
  • отправить блок памяти запрашивающей стороне с помощью сообщения (ОтветитьD).
  • если нет разделяющих сторон: запросчик = первый разделяющий, каталог переходит в состояние EM.
ЭМ
ЭМBusRd
  • Отправить вмешательство (Int) Владельцу
S
Автобус RdX
  • Отправить сообщение о недействительности (Инв.) текущему владельцу.
-
SBusRd
  • Ответить запрашивающей стороне блоком памяти (Ответить)
-
Автобус RdX
  • Ответить запрашивающей стороне блоком памяти (Ответить)
  • Сделать недействительным (Инв.) все участники.
ЭМ
BusUpgr
  • Сделать недействительным (Инв.) все участники.
  • Ответьте запрашивающему, что он может обновить. (Ответить)
ЭМ

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

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

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

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

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

использованная литература

  1. ^ а б Солихин, Ян (2009). Основы параллельной компьютерной архитектуры. С. 319–360.
  2. ^ Тан, К.К. «Проектирование кэш-системы в многопроцессорной системе с сильной связью». AFIPS '76 Труды Национальной компьютерной конференции и выставки 7–10 июня 1976 г..
  3. ^ а б "Протокол согласования кэша на основе каталогов для многопроцессорной системы DASH" (PDF). Лаборатория компьютерных систем.
  4. ^ Шмидт, Г. "Параллельный процессор бабочки". В Proc. ICS.
  5. ^ "Исследовательский прототип параллельного процессора IBM PR3: Введение и архитектура". В материалах Международной конференции по параллельной обработке 1985 г..
  6. ^ «Дизайн масштабируемых мультипроцессоров с общей памятью: подход DASH». Лаборатория компьютерных систем, Стэнфордский университет.
  7. ^ "Джеймс Арчибальд". ece.byu.edu. Получено 2016-11-15.
  8. ^ «Экономичное решение проблемы согласованности кеша». ISCA '84 Материалы 11-го ежегодного международного симпозиума по компьютерной архитектуре.
  9. ^ Леноски, Даниэль; Лаудон, Джеймс; Гарачорлоо, Курош; Вебер, Вольф-Дитрих; Гупта, Ануп; Хеннесси, Джон; Горовиц, Марк; Лам, Моника С. (1992-03-01). «Мультипроцессор Stanford Dash». Компьютер. 25 (3): 63–79. Дои:10.1109/2.121510. ISSN  0018-9162.
  10. ^ Лаудон, Джеймс; Леноски, Даниэль (1997-01-01). Источник SGI: масштабируемый сервер ccNUMA. Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре. ISCA '97. Нью-Йорк, Нью-Йорк, США: ACM. С. 241–251. Дои:10.1145/264107.264206. ISBN  978-0897919012.
  11. ^ Corp., Silicon Graphics International. «Домашняя страница поддержки». support1-sgi.custhelp.com. Получено 2016-11-16.
  12. ^ Солихин, Ян (2009). Основы параллельной многоядерной архитектуры. С. 319–361.