В компьютерной инженерии когерентность кэша на основе каталогов — это тип механизма когерентности кэша , где каталоги используются для управления кэшами вместо отслеживания шины . Методы отслеживания шины плохо масштабируются из-за использования широковещательной передачи . Эти методы могут использоваться для нацеливания как на производительность , так и на масштабируемость систем каталогов. [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]
Формат ограниченного указателя использует заданное количество указателей для отслеживания процессоров, которые кэшируют данные. Когда новый процессор кэширует блок, из пула выбирается свободный указатель, указывающий на этот процессор. Существует несколько вариантов обработки случаев, когда количество разделяющих устройств превышает количество свободных указателей. Один из методов — сделать недействительным одного из разделяющих устройств, используя его указатель для нового запрашивающего устройства, хотя это может быть затратно в случаях, когда блок имеет большое количество читателей, например, блокировку. Другой метод — иметь отдельный пул свободных указателей, доступных для всех блоков. Этот метод обычно эффективен, поскольку количество блоков, совместно используемых большим количеством процессоров, обычно не очень велико. [ необходима цитата ]
{{cite journal}}: Цитировать журнал требует |journal=( помощь )