В вычислительной технике , каталог на основе когерентность кэша - памяти является типом механизма когерентности кэша , в котором каталоги используются для управления кэшами в месте Snoopy методов из - за их масштабируемость. Методы слежения за автобусом плохо масштабируются из-за использования широковещательной передачи . Эти методы можно использовать как для повышения производительности, так и для масштабируемости систем каталогов. [1]
Полный битовый векторный формат
В формате полного битового вектора для каждой возможной строки кэша в памяти используется бит, чтобы отслеживать, хранится ли эта строка в кэше каждого отдельного процессора . [2] Полный битовый векторный формат является самой простой структурой для реализации, но наименее масштабируемой. [1] SGI Origin 2000 использует комбинацию полного битового вектора и грубого битового вектора в зависимости от количества процессоров. [3]
Каждая запись каталога должна иметь 1 бит для каждого процессора на строку кэша, а также биты для отслеживания состояния каталога. Это приводит к тому, что общий требуемый размер составляет (количество процессоров) × количество строк кэша , имея отношение накладных расходов хранения (количество процессоров) / (размер блока кэша × 8) .
Можно заметить, что служебные данные каталога линейно масштабируются с количеством процессоров. Хотя это может быть хорошо для небольшого числа процессоров, при реализации в больших системах требования к размеру каталога становятся чрезмерными. Например, при размере блока 32 байта и 1024 процессорах коэффициент накладных расходов хранилища становится 1024 / (32 × 8) = 400%. [2]
Грубый битовый векторный формат
Грубый формат битового вектора имеет структуру, аналогичную формату полного битового вектора, хотя вместо отслеживания одного бита на процессор для каждой строки кэша каталог группирует несколько процессоров в узлы , сохраняя, хранится ли строка кэша в узле, а не в линия. Это улучшает требования к размеру за счет экономии трафика шины (количество процессоров на узел) × (общее количество строк) бит пространства. [3] Таким образом, накладные расходы остаются прежними, просто количество процессоров заменяется количеством групп процессоров. Когда запрос шины сделан для строки кэша, которая есть у одного процессора в группе, каталог транслирует сигнал в каждый процессор в узле, а не только в кеши, которые его содержат, что приводит к ненужному трафику на узлы, у которых нет данных. кешировано. [2]
В этом случае запись каталога использует 1 бит для группы процессоров для каждой строки кэша. Для того же примера, что и для формата Full Bit Vector, если мы рассматриваем 1 бит для 8 процессоров как группу, то накладные расходы на хранилище будут 128 / (32 × 8) = 50%. Это значительное улучшение по сравнению с форматом Full Bit Vector.
Формат разреженного каталога
Кэш хранит только небольшое подмножество блоков в основной памяти в определенное время. Следовательно, большая часть записей в каталоге будет принадлежать некэшированным блокам. В формате разреженного каталога потери сокращаются за счет сохранения в каталоге только кэшированных блоков. [2] Рассмотрим процессор с размером кэша 64 КБ, размером блока 32 байта и размером основной памяти 4 МБ. Максимальное количество записей, которое каталог может иметь в формате разреженного каталога, составляет 2048. Если в каталоге есть запись для всех блоков в памяти, количество записей в каталоге будет 131072. Таким образом, очевидно, что улучшение хранилища предоставленный разреженным форматом каталогов очень важно.
Числовой формат двоичного дерева
В этом формате каталог децентрализован и распределяется между кешами, совместно использующими блок памяти. Различные кеши, которые совместно используют блок памяти, организованы в виде двоичного дерева . Кэш, который первым обращается к блоку памяти, является корневым узлом . Каждый блок памяти имеет информацию о корневом узле (HEAD) и поле счетчика совместного использования (SC). В поле SC указано количество кешей, совместно использующих блок. Каждая запись кэша имеет указатели на следующие совместно используемые кеши, известные как L-CHD и R-CHD. Условием для этого каталога является то, что двоичное дерево должно быть сбалансировано по количеству, то есть количество узлов в левом поддереве должно быть равно или на единицу больше, чем количество узлов в правом поддереве. Все поддеревья также должны быть сбалансированы по количеству. [4]
Связанный формат каталога
В этом формате память содержит указатель каталога на последний кэш, который обращался к блоку, и каждый кеш имеет указатель на предыдущий кеш, который обращался к блоку. Поэтому, когда процессор отправляет запрос на запись в блок в памяти, он отправляет недействительные данные по цепочке указателей. В этом каталоге при замене блока кеша нам нужно пройти по списку , чтобы изменить каталог, что увеличивает задержку . Чтобы предотвратить это, сейчас широко используются двусвязные списки , в которых каждая кешированная копия имеет указатели на предыдущий и следующий кеш, который обращается к блоку. [5]
Ограниченный формат указателя
Формат ограниченного указателя использует заданное количество указателей для отслеживания процессоров, кэширующих данные. Когда новый процессор кэширует блок, из пула выбирается свободный указатель, указывающий на этот процессор. Есть несколько вариантов обработки случаев, когда количество участников превышает количество свободных указателей. Один из методов состоит в том, чтобы аннулировать одного из разделяющих ресурсов, используя его указатель для нового запрашивающего, хотя это может быть дорогостоящим в случаях, когда блок имеет большое количество читателей, например, блокировка. Другой метод - иметь отдельный пул свободных указателей, доступных для всех блоков. Этот метод обычно эффективен, поскольку количество блоков, совместно используемых большим количеством процессоров, обычно не очень велико. [2]
Рекомендации
- ^ a b Рейнхарт, Стивен; Басу, Аркаправа; Бекманн, Брэдфорд; Хилл, Марк (11.07.2013). «Согласованность каталогов CMP: одна степень детализации не подходит для всех» (PDF) . Цитировать журнал требует
|journal=
( помощь ) - ^ а б в г д Солихин, Ян (09.10.2015). Основы параллельной многоядерной архитектуры . Роли, Северная Каролина: Solihin Publishing and Consulting, LLC. С. 331–335. ISBN 978-1-4822-1118-4.
- ^ а б Лаудон, Джеймс; Леноски, Даниэль (1997-06-01). SGI Origin: сервер ccNUMA с высокой степенью масштабируемости . Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре.
- ^ Со, Дэ-Вха; Чо, Чон Ван (1993-01-01). «Схема согласованности кэша на основе каталогов с использованием двоичного дерева с балансировкой чисел». Микропроцессоры и микропрограммирование . 37 (1): 37-40. DOI : 10.1016 / 0165-6074 (93) 90011-9 .
- ^ Chaiken, D .; Поля, С .; Курихара, К .; Агарвал, А. (01.06.1990). «Согласованность кэша на основе каталогов в крупномасштабных мультипроцессорах». Компьютер . 23 (6): 49–58. CiteSeerX 10.1.1.461.8404 . DOI : 10.1109 / 2.55500 . ISSN 0018-9162 .