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

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

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

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

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

В структуре кэша с прямым отображением кэш организован в несколько наборов ^[1] с одной строкой кэша на набор. На основе адреса блока памяти он может занимать только одну строку кэша. Кэш может быть представлен в виде матрицы столбцов $n$ $\times 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 бит тега , которые хранятся в поле тега для сопоставления адреса при запросе кэша.

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

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

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

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

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

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

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

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

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

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

Недостатки

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

Пример

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

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

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

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

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

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

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

Ассоциативный кэш можно представить как матрицу $n \times 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 бит , которые хранятся в поле тега для сопоставления адреса при запросе кэша.

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

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

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

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

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

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

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

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

Ссылки

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

[:0-1] «Основы кэширования» (PDF) .

[2] "Политики размещения кэша". Архивировано из оригинала 21 февраля 2020 г.

[3] "Политика размещения". Архивировано из оригинала 14 августа 2020 г.

[4] Мэттсон, Р. Л .; Гечеи, Дж.; Слютц, Д. Р.; Трейгер, И. (1970). «Методы оценки иерархий хранения». IBM Systems Journal . 9 (2): 78–117. doi :10.1147/sj.92.0078.

[:1-5] Солихин, Ян (2015). Основы параллельной многоядерной архитектуры . Тейлор и Фрэнсис. стр. 136–141. ISBN 978-1482211184.

[6] «Типы промахов кэша» (PDF) .

[7] "Полностью ассоциативный кэш". Архивировано из оригинала 24 декабря 2017 г.

[Seznec-8] Андре Сезнец (1993). «Дело в пользу двусторонних перекошенных ассоциативных кэшей». ACM SIGARCH Computer Architecture News . 21 (2): 169–178. doi : 10.1145/173682.165152 .

[CK-9] C. Kozyrakis . "Лекция 3: Продвинутые методы кэширования" (PDF) . Архивировано из оригинала (PDF) 7 сентября 2012 г.

[10] Микроархитектура «Кэши с искаженной ассоциативностью имеют ... значительные преимущества по сравнению с обычными кэшами с множественной ассоциативностью».