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

В компьютерной инженерии согласованность кэша на основе каталогов — это тип механизма согласованности кэша , где каталоги используются для управления кэшами вместо отслеживания шины . Методы слежения за шиной плохо масштабируются из-за использования широковещательной передачи . Эти методы можно использовать для повышения производительности и масштабируемости систем каталогов. ^[1]

Полный бит-векторный формат

В полнобитовом векторном формате для каждой возможной строки кэша в памяти процессор эту используется бит, чтобы отслеживать, имеет ли каждый отдельный строку , хранящуюся в его кэше . ^{[ нужна ссылка ]} Полнобитовый векторный формат — самая простая в реализации структура, но наименее масштабируемая. ^[1] SGI Origin 2000 использует комбинацию полного битового вектора и грубого битового вектора в зависимости от количества процессоров. ^[2]

Каждая запись каталога должна хранить по 1 биту на процессор в каждой строке кэша, а также биты для отслеживания состояния каталога. Это приводит к тому, что общий требуемый размер составляет (количество процессоров)×количество строк кэша , при этом накладных расходов коэффициент на хранение равен (количество процессоров)/(размер блока кэша×8) .

Можно заметить, что издержки каталогов линейно масштабируются в зависимости от количества процессоров. Хотя это может быть приемлемо для небольшого числа процессоров, при реализации в больших системах требования к размеру каталога становятся чрезмерными. Например, при размере блока 32 байта и 1024 процессорах коэффициент служебных данных при хранении становится 1024/(32×8) = 400%. ^{[ нужна ссылка ]}

Грубый битовый векторный формат

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

В этом случае запись каталога использует 1 бит для группы процессоров для каждой строки кэша. Для того же примера, что и для формата Full Bit Vector, если мы рассматриваем 1 бит для 8 процессоров как группу, то накладные расходы на хранение составят 128/(32×8)=50%. Это значительное улучшение по сравнению с форматом Full Bit Vector.

Разреженный формат каталога

Кэш хранит только небольшое подмножество блоков в основной памяти в определенный момент времени. Следовательно, большинство записей в каталоге будут принадлежать некэшированным блокам. В формате разреженного каталога потери сокращаются за счет хранения в каталоге только кэшированных блоков. ^{[ нужна ссылка ]} Рассмотрим процессор с размером кэша 64 КБ, размером блока 32 байта и объемом основной памяти 4 МБ. Максимальное количество записей, которые каталог может иметь в формате разреженного каталога, равно 2048. Если в каталоге есть записи для всех блоков памяти, количество записей в каталоге будет 131072. Таким образом, очевидно, что улучшение хранения предоставляемый разреженным форматом каталога, очень важен.

Формат сбалансированного по числам двоичного дерева

В этом формате каталог децентрализован и распределен между кэшами, которые совместно используют блок памяти. Различные кэши, использующие общий блок памяти, организованы в виде двоичного дерева . Кэш, который первым обращается к блоку памяти, является корневым узлом . Каждый блок памяти имеет информацию о корневом узле (HEAD) и поле счетчика совместного использования (SC). Поле SC содержит количество кэшей, которые совместно используют этот блок. Каждая запись кэша имеет указатели на следующие общие кэши, известные как L-CHD и R-CHD. Условием для этого каталога является то, что двоичное дерево должно быть сбалансировано по количеству, т.е. количество узлов в левом поддереве должно быть равно или на единицу больше, чем количество узлов в правом поддереве. Все поддеревья также должны быть сбалансированы по количеству. ^[3]

Формат связанного каталога

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

Ограниченный формат указателя

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

Ссылки

^ Перейти обратно: ^а ^б Рейнхарт, Стивен; Басу, Аркаправа; Бекманн, Брэдфорд; Хилл, Марк (11 июля 2013 г.). «Связность каталога CMP: одна степень детализации не подходит всем» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
^ Перейти обратно: ^а ^б Лаудон, Джеймс; Леноски, Дэниел (1 июня 1997 г.). SGI Origin: высокомасштабируемый сервис ccNUMA . Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре.
^ Со, Дэ-Ва; Чо, Юнг Ван (1 января 1993 г.). «Схема когерентности кэша на основе каталогов с использованием сбалансированного по числам двоичного дерева». Микропроцессинг и микропрограммирование . 37 (1): 37–40. дои : 10.1016/0165-6074(93)90011-9 .
^ Чайкен, Д.; Филдс, К.; Курихара, К.; Агарвал, А. (1 июня 1990 г.). «Когерентность кэша на основе каталогов в крупномасштабных мультипроцессорах». Компьютер 23 (6): 49–58. CiteSeerX 10.1.1.461.8404 . дои : 10.1109/2.55500 . ISSN 0018-9162 . S2CID 683311 .

[CMPAMDUWPaper-1] Перейти обратно: ^а ^б Рейнхарт, Стивен; Басу, Аркаправа; Бекманн, Брэдфорд; Хилл, Марк (11 июля 2013 г.). «Связность каталога CMP: одна степень детализации не подходит всем» (PDF) . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )

[SGI2000OriginPaper-2] Перейти обратно: ^а ^б Лаудон, Джеймс; Леноски, Дэниел (1 июня 1997 г.). SGI Origin: высокомасштабируемый сервис ccNUMA . Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре.

[3] Со, Дэ-Ва; Чо, Юнг Ван (1 января 1993 г.). «Схема когерентности кэша на основе каталогов с использованием сбалансированного по числам двоичного дерева». Микропроцессинг и микропрограммирование . 37 (1): 37–40. дои : 10.1016/0165-6074(93)90011-9 .

[4] Чайкен, Д.; Филдс, К.; Курихара, К.; Агарвал, А. (1 июня 1990 г.). «Когерентность кэша на основе каталогов в крупномасштабных мультипроцессорах». Компьютер 23 (6): 49–58. CiteSeerX 10.1.1.461.8404 . дои : 10.1109/2.55500 . ISSN 0018-9162 . S2CID 683311 .

[1]

[2]

[3]

[4]