Согласованность кэша на основе каталогов - Directory-based cache coherence

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

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

Схема формата каталога полного битового вектора, где E = Exclusive, S = Shared, M = Modified и U = Uncached

В полном битовом векторном формате для каждого возможного строка кеша в объем памяти, а кусочек используется для отслеживания того, каждый ли процессор эта строка хранится в тайник.[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]

Рекомендации

  1. ^ а б Рейнхарт, Стивен; Басу, Аркаправа; Бекманн, Брэдфорд; Хилл, Марк (11.07.2013). «Согласованность каталогов CMP: одна степень детализации не подходит для всех» (PDF). Цитировать журнал требует | журнал = (помощь)
  2. ^ а б c d е Солихин, Ян (09.10.2015). Основы параллельной многоядерной архитектуры. Роли, Северная Каролина: ООО «Солихин Паблишинг энд Консалтинг». С. 331–335. ISBN  978-1-4822-1118-4.
  3. ^ а б Лаудон, Джеймс; Леноски, Даниэль (1997-06-01). SGI Origin: масштабируемая система ccNUMA. Материалы 24-го ежегодного международного симпозиума по компьютерной архитектуре.
  4. ^ Со, Дэ-Вха; Чо, Чон Ван (1993-01-01). «Схема согласованности кэша на основе каталогов с использованием двоичного дерева с балансировкой чисел». Микропроцессоры и микропрограммирование. 37 (1): 37–40. Дои:10.1016/0165-6074(93)90011-9.
  5. ^ Chaiken, D .; Поля, С .; Курихара, К .; Агарвал, А. (01.06.1990). «Согласованность кэша на основе каталогов в крупномасштабных мультипроцессорах». Компьютер. 23 (6): 49–58. CiteSeerX  10.1.1.461.8404. Дои:10.1109/2.55500. ISSN  0018-9162.