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

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

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

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

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

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

Адрес 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]

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

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

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

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

Недостатки

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

Пример

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Недостатки

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

Пример

Рассмотрим основную память объемом 16 килобайт, которая организована в виде блоков по 4 байта, и двухсторонний наборно-ассоциативный кэш объемом 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]

См. также

Ссылки

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

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

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

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

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

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

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

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

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

[CK-9] Jump up to: ^а ^б К. Козыракис . «Лекция 3: Расширенные методы кэширования» (PDF) . Архивировано из оригинала (PDF) 7 сентября 2012 г.

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]