Политики размещения кэша

Проектные решения, влияющие на скорость и размер кэша процессора

Политики размещения кэша — это политики, которые определяют, где может быть размещен конкретный блок памяти, когда он попадает в кэш ЦП . Блок памяти не обязательно может быть помещен в произвольное место кэша; он может быть ограничен определенной строкой кэша или набором строк кэша ^[1] в соответствии с политикой размещения кэша. ^{[2] [3]}

Для размещения блока памяти в кеше доступны три различные политики: прямое отображение, полностью ассоциативная и ассоциативная установка. Первоначально это пространство организации кэша описывалось термином «отображение конгруэнтности». ^[4]

Кэш с прямым отображением

В структуре кэша с прямым отображением кэш организован в несколько наборов ^[1] с одной строкой кэша в каждом наборе. В зависимости от адреса блока памяти он может занимать только одну строку кэша. Кэш может быть представлен как матрица-столбец размером n × 1 . ^[5]

Поместить блок в кэш

• Набор определяется битами индекса ^[1] , полученными из адреса блока памяти.
• Блок памяти помещается в идентифицированный набор, а тег ^[1] сохраняется в поле тега, связанном с набором.
• Если строка кэша ранее занята, то новые данные заменяют блок памяти в кэше.

Чтобы найти слово в кэше

• Набор идентифицируется индексными битами адреса.
• Биты тега, полученные из адреса блока памяти, сравниваются с битами тега, связанными с набором. Если тег совпадает, происходит попадание в кэш , и блок кэша возвращается процессору. В противном случае происходит промах в кэше , и блок памяти извлекается из нижней памяти ( основной памяти , диска ).

Преимущества

• Эта политика размещения является энергоэффективной, поскольку позволяет избежать поиска по всем строкам кэша.
• Политика размещения и политика замены проста.
• Для этого требуется дешевое оборудование, поскольку одновременно необходимо проверять только один тег.

Недостаток

• Он имеет более низкую скорость попадания в кэш, поскольку в наборе доступна только одна строка кэша. Каждый раз, когда к тому же набору обращается новая память, строка кэша заменяется, что приводит к конфликту. ^[6]

Пример

Кэш с прямым отображением

Рассмотрим основную память объемом 16 килобайт, которая организована в виде блоков по 4 байта, и кэш прямого отображения объемом 256 байт с размером блока 4 байта. Поскольку объем основной памяти составляет 16 КБ, нам нужно как минимум 14 бит, чтобы однозначно представить адрес памяти.

Поскольку каждый блок кэша имеет размер 4 байта, общее количество наборов в кэше равно 256/4, что соответствует 64 наборам.

Входящий адрес в кэш делится на биты Offset , Index и Tag .

• Смещение соответствует битам, используемым для определения байта, к которому осуществляется доступ из строки кэша. Поскольку строки кэша имеют длину 4 байта, имеется 2 бита смещения .
• Индекс соответствует битам, используемым для определения набора Кэша. В кэше 64 набора, а поскольку 2^6 = 64, индексных битов 6.
• Тег соответствует остальным битам. Это означает, что имеется 14 – (6+2) = 6 бит тега , которые хранятся в поле тега для соответствия адресу при запросе к кэшу.

Ниже приведены адреса памяти и объяснение того, какой строке кэша они соответствуют:

1. Адрес 0x0000(тег - 0b00_0000, индекс - 0b00_0000, смещение - 0b00) соответствует блоку 0 памяти и соответствует набору 0 кэша.
2. Адрес 0x0004(тег - 0b00_0000, индекс - 0b00_0001, смещение - 0b00) соответствует блоку 1 памяти и отображается в набор 1 кэша.
3. Адрес 0x00FF(тег – 0b00_0000, индекс – 0b11_1111, смещение – 0b11) соответствует блоку 63 памяти и отображается в набор 63 кэша.
4. Адрес 0x0100(тег – 0b00_0001, индекс – 0b00_0000, смещение – 0b00) соответствует блоку 64 памяти и отображается в набор 0 кэша.

Полностью ассоциативный кеш

В полностью ассоциативном кэше кэш организован в единый набор кэшей с несколькими строками кэша. Блок памяти может занимать любую из строк кэша. Организацию кэша можно представить в виде матрицы строк размером 1 × m . ^[5]

Поместить блок в кэш

• Строка кэша выбирается на основе связанного с ней допустимого бита ^{[1] .} Если действительный бит равен 0, новый блок памяти может быть помещен в строку кэша, в противном случае его необходимо поместить в другую строку кэша с действительным битом 0.
• Если кеш полностью занят, блок вытесняется, и блок памяти помещается в эту строку кэша.
• Удаление блока памяти из кэша определяется политикой замены. ^[7]

Чтобы найти слово в кэше

• Поле Tag адреса памяти сравнивается с битами тега, связанными со всеми строками кэша. Если оно соответствует, блок присутствует в кеше и является попаданием в кеш. Если оно не совпадает, то это промах в кэше, и его необходимо извлечь из нижней памяти.
• На основе смещения выбирается байт и возвращается в процессор.

Полностью ассоциативный кеш

Преимущества

• Полностью ассоциативная структура кэша обеспечивает нам гибкость размещения блока памяти в любой из строк кэша и, следовательно, полное использование кэша.
• Политика размещения обеспечивает лучшую частоту попадания в кэш.
• Он предлагает гибкость использования широкого спектра алгоритмов замены в случае промаха в кэше.

Недостатки

• Политика размещения медленная, поскольку для перебора всех строк требуется время. ^{[ оспаривается ]}
• Политика размещения требует много энергии, поскольку ей приходится перебирать весь набор кэша, чтобы найти блок.
• Самый дорогой из всех методов из-за высокой стоимости аппаратуры ассоциативного сравнения.

Пример

Рассмотрим основную память объемом 16 килобайт, которая организована в виде блоков по 4 байта, и полностью ассоциативный кэш объемом 256 байт и размером блока 4 байта. Поскольку объем основной памяти составляет 16 КБ, нам нужно как минимум 14 бит, чтобы однозначно представить адрес памяти.

Общее количество наборов в кэше равно 1, набор содержит 256/4=64 строки кэша, так как блок кэша имеет размер 4 байта.

Входящий адрес в кэш делится на биты смещения и тега.

• Смещение соответствует битам, используемым для определения байта, к которому осуществляется доступ из строки кэша. В примере есть 2 бита смещения, которые используются для адресации 4 байтов строки кэша.
• Тег соответствует остальным битам. Это означает, что имеется 14 – (2) = 12 битов тега , которые хранятся в поле тега для соответствия адресу при запросе к кэшу.

Поскольку любой блок памяти может быть сопоставлен с любой строкой кэша, этот блок памяти может занимать одну из строк кэша в зависимости от политики замены.

Set-ассоциативный кэш

Набор-ассоциативный кеш — это компромисс между кешем с прямым отображением и полностью ассоциативным кешем.

Множественно-ассоциативный кеш можно представить как матрицу размера n × m . Кэш разделен на n наборов, и каждый набор содержит m строк кэша. Блок памяти сначала отображается в набор, а затем помещается в любую строку кэша набора.

Диапазон кэшей от прямого отображения до полностью ассоциативных представляет собой континуум уровней установленной ассоциативности. (Кэш с прямым отображением является односторонним набор-ассоциативным, а полностью ассоциативный кэш с m строками кэша является m -сторонним набор-ассоциативным.)

Многие кэши процессоров в современных конструкциях имеют либо прямое отображение, либо двустороннюю ассоциативность множеств, либо ассоциативность множеств с четырьмя путями. ^[5]

Поместить блок в кэш

• Набор определяется битами индекса, полученными из адреса блока памяти.
• Блок памяти помещается в доступную строку кэша в идентифицированном наборе, а тег сохраняется в поле тега, связанном с этой строкой. Если все строки кэша в наборе заняты, то новые данные заменяют блок, определенный с помощью политики замены .

Чтобы найти слово в кэше

• Набор определяется битами индекса, полученными из адреса блока памяти.
• Биты тега сравниваются с тегами всех строк кэша, присутствующих в выбранном наборе. Если тег соответствует какой-либо из строк кэша, это попадание в кэш и возвращается соответствующая строка. Если тег не соответствует ни одной из строк, то это промах кэша и данные запрашиваются со следующего уровня в иерархии памяти.

Преимущества

• Политика размещения представляет собой компромисс между кэшем с прямым отображением и полностью ассоциативным.
• Он обеспечивает гибкость использования алгоритмов замены в случае промаха кэша.

Недостатки

• Политика размещения не будет эффективно использовать все доступные строки кэша и подвержена конфликтам .

Пример

Рассмотрим основную память объемом 16 килобайт, которая организована в виде блоков по 4 байта, и двусторонний наборно-ассоциативный кэш объемом 256 байт с размером блока 4 байта. Поскольку объем основной памяти составляет 16 КБ, нам нужно как минимум 14 бит, чтобы однозначно представить адрес памяти.

Поскольку каждый блок кэша имеет размер 4 байта и является двухсторонним наборно-ассоциативным, общее количество наборов в кэше равно 256/(4 * 2), что равно 32 наборам.

Set-Associative Cache

Входящий адрес в кэш делится на биты смещения, индекса и тега.

• Смещение соответствует битам, используемым для определения байта, к которому осуществляется доступ из строки кэша. Поскольку строки кэша имеют длину 4 байта, имеется 2 бита смещения .
• Индекс соответствует битам, используемым для определения набора Кэша. В кэше 32 набора, а поскольку 2^5 = 32, индексных битов 5.
• Тег соответствует остальным битам. Это означает, что в поле тега хранится 14 – (5+2) = 7 бит , которые соответствуют адресу при запросе к кэшу.

Ниже приведены адреса памяти и объяснение того, какой строке кэша и в каком наборе они соответствуют:

1. Адрес 0x0000(тег - 0b000_0000, индекс - 0b0_0000, смещение - 0b00) соответствует блоку 0 памяти и соответствует набору 0 кэша. Блок занимает строку кэша в наборе 0, определяемую политикой замены кэша.
2. Адрес 0x0004(тег - 0b000_0000, индекс - 0b0_0001, смещение - 0b00) соответствует блоку 1 памяти и отображается в набор 1 кэша. Блок занимает строку кэша в наборе 1, определяемую политикой замены кэша.
3. Адрес 0x00FF(тег – 0b000_0001, индекс – 0b1_1111, смещение – 0b11) соответствует блоку 63 памяти и отображается в набор 31 кэша. Блок занимает строку кэша в наборе 31, определяемую политикой замены кэша.
4. Адрес 0x0100(тег – 0b000_0010, индекс – 0b0_0000, смещение – 0b00) соответствует блоку 64 памяти и отображается в набор 0 кэша. Блок занимает строку кэша в наборе 0, определяемую политикой замены кэша.

Двусторонний перекошенный ассоциативный кеш

Были предложены и другие схемы, такие как асимметричный кэш ^[8] , где индекс для пути 0 является прямым, как указано выше, но индекс для пути 1 формируется с помощью хэш-функции . Хорошая хэш-функция обладает свойством, заключающимся в том, что адреса, конфликтующие с прямым сопоставлением, обычно не конфликтуют при сопоставлении с хеш-функцией, поэтому менее вероятно, что программа пострадает от неожиданно большого количества конфликтных промахов из-за патологического доступа. шаблон. Обратной стороной является дополнительная задержка при вычислении хэш-функции. ^[9] Кроме того, когда приходит время загрузить новую строку и удалить старую, может быть сложно определить, какая существующая строка использовалась реже всего в последнее время, поскольку новая строка конфликтует с данными по разным индексам во всех отношениях; Отслеживание LRU для нескошенных кэшей обычно выполняется для каждого набора. Тем не менее, асимметрично-ассоциативные кэши имеют большие преимущества перед обычными множественно-ассоциативными кэшами. ^[10]

Псевдоассоциативный кеш

Настоящий множественно-ассоциативный кеш проверяет все возможные способы одновременно, используя что-то вроде памяти с адресацией по содержимому . Псевдоассоциативный кеш проверяет каждый возможный путь по одному. Кэш-перехеширование и ассоциативный кеш по столбцам являются примерами псевдоассоциативного кеша.

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

Смотрите также

• Ассоциативность
• Политика замены кэша
• Иерархия кэша
• Написание политик
• Раскраска кэша

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

1. «Основы кэширования» (PDF) .
2. «Политика размещения кэша». Архивировано из оригинала 21 февраля 2020 года.
3. «Политика размещения». Архивировано из оригинала 14 августа 2020 года.
4. Мэттсон, РЛ ; Гечеи, Дж.; Слуц, ДР; Трейгер, я (1970). «Методы оценки иерархий хранения». IBM Systems Journal . 9 (2): 78–117. дои : 10.1147/sj.92.0078.
5. Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Тейлор и Фрэнсис. стр. 136–141. ISBN 978-1482211184.
6. «Типы промахов в кэше» (PDF) .
7. «Полностью ассоциативный кеш». Архивировано из оригинала 24 декабря 2017 года.
8. Андре Сезнек (1993). «Дело в пользу двусторонних асимметрично-ассоциативных кэшей». Новости компьютерной архитектуры ACM SIGARCH . 21 (2): 169–178. дои : 10.1145/173682.165152 .
9. К. Козиракис. «Лекция 3: Расширенные методы кэширования» (PDF) . Архивировано из оригинала (PDF) 7 сентября 2012 года.
10. Микроархитектура «Перекошенные ассоциативные кеши имеют ... большие преимущества перед обычными ассоциативными кешами».