Согласованность на основе каталогов
Согласованность на основе каталогов — это механизм решения проблемы согласованности кэша в распределенной общей памяти (DSM), также известной как неравномерный доступ к памяти (NUMA). Другой популярный способ — использование специального типа компьютерной шины между всеми узлами в качестве «общей шины» (она же системная шина ). [1] Когерентность на основе каталогов использует специальный каталог для обслуживания вместо общей шины в протоколах когерентности на основе шины. Обе эти конструкции используют соответствующую среду (т. е. каталог или шину) в качестве инструмента, облегчающего связь между различными узлами и гарантирующего правильную работу протокола когерентности на всех взаимодействующих узлах. При согласованности кэша на основе каталогов это делается с помощью этого каталога для отслеживания состояния всех блоков кэша , причем статус каждого блока включает в себя, в каком « состоянии » согласованности кэша находится этот блок, и какие узлы при этом совместно используют этот блок. время, которое можно использовать для устранения необходимости транслировать все сигналы всем узлам и отправлять их только тем узлам, которые заинтересованы в этом одном блоке.
Ниже приведены несколько преимуществ и недостатков протокола когерентности кэша на основе каталогов:
- Масштабируемость : это одна из самых сильных мотиваций для перехода к проектам на основе каталогов. Короче говоря, масштабируемость — это то, насколько хорошо конкретная система справляется с растущим объемом работы, которую она должна выполнять. По этому критерию системы на основе шины не могут преуспеть из-за ограничений, возникающих при наличии общей шины, которую все узлы используют одновременно. Для относительно небольшого числа узлов шинные системы могут работать хорошо. Однако по мере роста количества узлов в этом плане могут возникнуть некоторые проблемы. Тем более, что одновременно использовать шину разрешено только одному узлу, что существенно ухудшит производительность всей системы. С другой стороны, при использовании систем на основе каталогов таких узких мест, ограничивающих масштабируемость системы, не будет.
- Простота : это один из пунктов, в которых шинная система превосходит других. Поскольку структура шины сама по себе может служить организатором всего трафика, проходящего через систему, и обеспечивать атомарность всех проходящих сигналов, не будет необходимости прилагать больше усилий для обеспечения атомарности и упорядочения между сигналами, как в данном случае. в системах на основе каталогов, что приводит к некоторым накладным расходам, с которыми приходится сталкиваться при более позднем проектировании системы при решении таких проблем, как согласованность .
Из приведенного выше обсуждения следует, что использование систем на основе шины кажется более привлекательным для относительно небольших систем. Однако системы на основе каталогов становятся критически важными, когда система масштабируется и количество узлов растет. существует своего рода компромисс между простотой и масштабируемостью. Таким образом , при сравнении схем когерентности кэша на основе шины и каталога [1]
История
[ редактировать ]Идея систем когерентности кэша на основе каталогов возникла давно. Идея DASH ( каталогов архитектура для . SH -памяти) была впервые предложена С.К. Тангом [2] в середине 1970-х годов. Однако применить его к когерентности кэша было предложено несколько лет спустя, в 1978 году, когда исследователи из Стэнфордского университета первую версию этой системы когерентности под названием Stanford DASH . предложили в статье [3] в котором описывалась система с трудностями и улучшениями, связанными с такими конструкциями. Помимо этого подхода, было предпринято несколько попыток создать масштабируемую систему. Например, ББН Баттерфляй. [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 года.
Протоколы
[ редактировать ]В отличие от протоколов согласованности snoopy , в подходе когерентности на основе каталогов информация о том, в каких кэшах имеется копия блока, сохраняется в структуре, называемой каталогом . В схеме на основе каталогов участвующие кэши не передают запросы всем другим общим кэшам блока для поиска кэшированных копий, вместо этого они запрашивают каталог, чтобы получить информацию о том, какой блок имеет кэшированные копии, и отправляет только этим конкретным процессорам и следовательно, экономия трафика по сравнению со отслеживающим протоколом велика. В хорошо оптимизированных приложениях большая часть совместного использования данных предназначена только для данных, предназначенных только для чтения, и мало общего для данных, которые часто читаются и записываются. В таких приложениях подход с использованием каталогов может привести к существенной экономии трафика по сравнению с подходом широковещательной передачи/отслеживания.
Как показано на диаграмме потока данных, участниками распределенной системы с общей памятью, реализующей протокол согласованности на основе каталогов, являются:
- Узел-запросчик : этот узел является процессором, который запрашивает чтение/запись блока памяти.
- Узел каталога : этот узел хранит информацию о состоянии каждого блока кэша в системе, и запрашивающая сторона направляет свои запросы к узлу каталога.
- Узел-владелец : Узел-владелец владеет самым последним состоянием блока кэша. Обратите внимание, что каталог не всегда может быть обновлен с последними данными.
- Узел-разделитель : один или несколько узлов, которые совместно используют копию блока кэша.
Узлы запросчика и владельца поддерживают переход состояния аналогично протоколам слежения за когерентностью, таким как протокол MESI . Однако, в отличие от реализации на основе шины, где узлы взаимодействуют с использованием общей шины, реализация на основе каталогов использует модель передачи сообщений для обмена информацией, необходимой для поддержания согласованности кэша .
Узел каталога действует как точка сериализации, и все сообщения направляются через этот узел для обеспечения корректности.
Узел каталога
[ редактировать ]Узел каталога отслеживает общее состояние блока кэша во всей системе кэша для всех процессоров. Он может находиться в трех состояниях:
- Без кэширования (U) : ни один процессор не имеет кэшированных данных, память актуальна.
- Общий (S) : один или несколько процессоров имеют кэшированные данные и актуальную память. В этом каталоге состояния и у участников есть чистая копия кэшированного блока.
- Эксклюзивный/модифицированный (EM) : один процессор (владелец) кэширует данные; память устарела. Обратите внимание, что каталог не может отличить блок, кэшированный в процессоре в эксклюзивном или измененном состоянии, поскольку процессоры могут переходить из эксклюзивного состояния в модифицированное состояние без какой-либо транзакции шины.
Объяснение конечного автомата перехода состояний каталога (см. изображение 1) приведено ниже в таблице:
| Исходное состояние | Запрос автобуса | Реакция/Действие | Новое государство |
|---|---|---|---|
| В | Автобусная дорога или
АвтобусRdX |
|
В |
| В | Автобусная улица |
|
С |
| АвтобусRdX |
|
- | |
| С | Автобусная улица |
|
- |
| АвтобусRdX |
|
В | |
| BusUpgr |
|
В |
Помимо состояния кэша, каталог должен отслеживать, какие процессоры имеют данные в общем состоянии. Это необходимо для отправки запросов на аннулирование и вмешательство в кэши отдельных процессоров, у которых блок кэша находится в общем состоянии. Вот некоторые из популярных подходов к реализации:
- Полный битовый вектор : поддерживается битовое поле для каждого процессора в узле каталога. Накладные расходы на хранилище масштабируются в зависимости от количества процессоров.
- Ограниченный указатель: при этом подходе информация о каталоге в ограниченном количестве блоков хранится в каталоге, чтобы уменьшить накладные расходы на хранение.
Описанный выше протокол является базовой реализацией, и условия гонки могут возникнуть из-за того, что каталог может быть не синхронизирован с кэшами, а также сообщения между процессорами могут перекрываться. Доступны более сложные реализации, такие как масштабируемый когерентный интерфейс , который имеет несколько состояний.
БРОСАТЬСЯ [3] Протокол когерентности кэша — это еще один протокол, использующий схему когерентности на основе каталогов. Протокол DASH использует кластерный подход, при котором процессоры внутри кластера поддерживаются согласованными с помощью схемы отслеживания на основе шины, в то время как кластеры соединяются по принципу каталогов. Несмотря на то, что различные протоколы используют разные реализации для отслеживания блоков кэша, концепция каталога остается неизменной.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б Солихин, Ян (2009). Основы архитектуры параллельных компьютеров . стр. 319–360.
- ^ Тан, К.К. «Проектирование системы кэширования в тесно связанной многопроцессорной системе». AFIPS '76 Материалы Национальной компьютерной конференции и выставки 7–10 июня 1976 г.
- ^ Jump up to: а б «Протокол когерентности кэша на основе каталогов для мультипроцессора DASH» (PDF) . Лаборатория компьютерных систем .
- ^ Шмидт, GE «Параллельный процессор Butterfly». В Proc. Из ИКС .
- ^ «Прототип исследовательского параллельного процессора IBM PR3: введение и архитектура». В материалах Международной конференции по параллельной обработке 1985 года .
- ^ «Проектирование масштабируемых мультипроцессоров с общей памятью: подход DASH». Лаборатория компьютерных систем Стэнфордского университета .
- ^ «Джеймс Арчибальд» . ece.byu.edu . Архивировано из оригинала 2 августа 2017 г. Проверено 15 ноября 2016 г.
- ^ «Экономичное решение проблемы когерентности кэша». ISCA '84 Материалы 11-го ежегодного международного симпозиума по компьютерной архитектуре .
- ^ Леноски, Дэниел; Лаудон, Джеймс; Гарачорлоо, Курош; Вебер, Вольф-Дитрих; Гупта, Ануп; Хеннесси, Джон; Горовиц, Марк; Лам, Моника С. (1 марта 1992 г.). «Мультипроцессор Stanford Dash». Компьютер . 25 (3): 63–79. дои : 10.1109/2.121510 . ISSN 0018-9162 . S2CID 9731523 .
- ^ Лаудон, Джеймс; Леноски, Дэниел (1 января 1997 г.). «Происхождение SGI». Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре - ISCA '97 . ИСКА '97. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 241–251. дои : 10.1145/264107.264206 . ISBN 978-0897919012 . S2CID 692050 .
- ^ Корпорация Silicon Graphics International. «Главная страница поддержки» . support1-sgi.custhelp.com . Архивировано из оригинала 13 апреля 2018 г. Проверено 16 ноября 2016 г.
- ^ Солихин, Ян (2009). Основы параллельной многоядерной архитектуры . стр. 319–361.