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

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

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

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

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

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

Чтобы поместить блок в кэш

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

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

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

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

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

Недостаток

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

Пример

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

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

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

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

• Смещение соответствует битам, используемым для определения байта, к которому будет осуществляться доступ из строки кэша. Поскольку строки кэша имеют длину 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]

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

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

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

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

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

Недостатки

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

Пример

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

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

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

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

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

Наборно-ассоциативный кэш

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

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

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

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

Чтобы поместить блок в кэш

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

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

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

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

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

Недостатки

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

Пример

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

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

Наборно-ассоциативный кэш

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

• Смещение соответствует битам, используемым для определения байта, к которому будет осуществляться доступ из строки кэша. Поскольку строки кэша имеют длину 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. doi :10.1147/sj.92.0078.
5. Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Тейлор и Фрэнсис. стр. 136–141. ISBN 978-1482211184.
6. «Типы промахов кэша» (PDF) .
7. "Полностью ассоциативный кэш". Архивировано из оригинала 24 декабря 2017 г.
8. Андре Сезнец (1993). «Дело в пользу двусторонних перекошенных ассоциативных кэшей». ACM SIGARCH Computer Architecture News . 21 (2): 169–178. doi : 10.1145/173682.165152 .
9. C. Kozyrakis . "Лекция 3: Продвинутые методы кэширования" (PDF) . Архивировано из оригинала (PDF) 7 сентября 2012 г.
10. Микроархитектура «Кэши с искаженной ассоциативностью имеют ... значительные преимущества по сравнению с обычными кэшами с множественной ассоциативностью».