Политики размещения кеша - Cache placement policies
А Кэш процессора - это память, в которой хранятся недавно использованные процессором данные. Блок памяти не может быть размещен в кэше случайным образом и может быть ограничен одним строка кеша или набор строк кеша[1] посредством политика размещения кеша.[2][3] Другими словами, политика размещения кэша определяет, где можно разместить конкретный блок памяти, когда он попадает в кэш.
Для размещения блока памяти в кэше доступны три различные политики: прямое отображение, полностью ассоциативная и ассоциативная по множеству. Первоначально это пространство кеш-организаций описывалось термином «сопоставление конгруэнтности».[4]
Кэш с прямым отображением
В структуре кэша с прямым отображением кеш организован в несколько наборов.[1] с одной строкой кэша на набор. В зависимости от адреса блока памяти он может занимать только одну строку кэша. Кэш может быть оформлен как матрица столбцов (n * 1).[5]
Поместить блок в кеш
- Набор определяется индекс[1] биты, полученные из адреса блока памяти.
- Блок памяти помещается в обозначенный набор, и тег [1] хранится в поле тега, связанном с набором.
- Если строка кэша ранее была занята, то новые данные заменяют блок памяти в кэше.
Для поиска слова в кеше
- Набор идентифицируется индексными битами адреса.
- Биты тега, полученные из адреса блока памяти, сравниваются с битами тега, связанными с набором. Если тег совпадает, значит, есть попадание в кеш и блок кэша возвращается процессору. Еще есть промах в кеше и блок памяти выбирается из нижней памяти (основная память, диск ).
Преимущества
- Эта политика размещения энергоэффективна, поскольку позволяет избежать поиска по всем строкам кэша.
- Политика размещения и политика замены это просто.
- Это требует дешевого оборудования, так как нужно проверять только одну метку за раз.
Недостаток
- У него более низкая частота попаданий в кеш, поскольку в наборе доступна только одна строка кеша. Каждый раз, когда новая память обращается к тому же самому набору, строка кэша заменяется, что приводит к пропуску конфликта.[6]
Пример
Рассмотрим основную память размером 16 килобайт, которая организована как 4-байтовые блоки, и кэш с прямым отображением размером 256 байтов с размером блока 4 байта.
Поскольку размер каждого блока кэша составляет 4 байта, общее количество наборов в кэше составляет 256/4, что равно 64 наборам.
Входящий адрес в кеш делится на биты для Компенсировать, Индекс и Тег.
Смещение соответствует битам, используемым для определения байта, к которому нужно получить доступ из строки кэша.
В этом примере есть 2 бита смещения, которые используются для адресации 4 байтов строки кэша.
Индекс соответствует битам, используемым для определения набора кэша.
В этом примере есть 6 индексных битов, которые используются для адресации 64 наборов кеша.
Тег соответствует оставшимся битам.
В этом примере имеется 14 - (6 + 2) = 6 бит тега, которые хранятся в поле тега, чтобы соответствовать адресу по запросу кеша.
Адрес 0x0000 (тег - 00_0000, индекс - 00_0000, смещение - 00) отображается в блок 0 памяти и занимает набор 0 кеша.
Адрес 0x0004 (тег - 00_0000, индекс - 00_0001, смещение - 00) отображается на блок 1 памяти и занимает набор 1 кеша.
Точно так же адрес 0x00FF (тег - 00_0000, индекс - 11_1111, смещение - 11) отображается на блок 63 памяти и занимает набор 63 кеша.
Адрес 0x0100 (тег - 00_0001, индекс - 00_0000, смещение - 00) отображается на блок 64 памяти и занимает набор 0 кеша.
Полностью ассоциативный кеш
В полностью ассоциативном кэше кэш организован в единый набор кэша с несколькими строками кэша. Блок памяти может занимать любую из строк кэша. Организацию кеша можно представить в виде матрицы строк (1 * m).[5]
Поместить блок в кеш
- Строка кэша выбирается на основе действительного бита[1] связанные с ним. Если действительный бит равен 0, новый блок памяти может быть помещен в строку кэша, иначе он должен быть помещен в другую строку кэша с допустимым битом 0.
- Если кэш полностью занят, блок удаляется, и блок памяти помещается в эту строку кэша.
- Решение об удалении блока памяти из кэша определяется политикой замены.[7]
Для поиска слова в кеше
- Поле Tag адреса памяти сравнивается с битами тега, связанными со всеми строками кэша. Если он совпадает, блок присутствует в кеше и является попаданием в кеш. Если он не совпадает, значит, это промах в кэше, и его необходимо извлечь из нижней памяти.
- На основе смещения выбирается байт и возвращается процессору.
Преимущества
- Полностью ассоциативная структура кэша обеспечивает гибкость размещения блока памяти в любой из строк кэша и, следовательно, полное использование кеша.
- Политика размещения обеспечивает лучшую частоту попаданий в кеш.
- Он предлагает гибкость использования широкого спектра алгоритмы замены если происходит промах кеша.
Недостаток
- Политика размещения выполняется медленно, поскольку требуется время, чтобы перебрать все строки.
- Политика размещения требует много энергии, так как для поиска блока необходимо перебирать весь набор кешей.
- Самый дорогой из всех методов из-за дороговизны оборудования для ассоциативного сравнения.
Пример
Рассмотрим основную память размером 16 килобайт, которая организована как 4-байтовые блоки, и полностью ассоциативный кэш размером 256 байтов и размером блока 4 байта.
Поскольку каждый блок кэша имеет размер 4 байта, общее количество наборов в кэше составляет 256/4, что равно 64 наборам или строкам кэша.
Входящий адрес в кэш делится на биты для смещения и тега.
Смещение соответствует битам, используемым для определения байта, к которому нужно получить доступ из строки кэша.
В этом примере есть 2 бита смещения, которые используются для адресации 4 байтов строки кэша, а оставшиеся 12 бит образуют тег.
Биты тега хранятся в поле тега строки кэша, чтобы соответствовать адресу по запросу кеша.
Поскольку любой блок памяти может быть отображен в любую строку кэша, блок памяти может занимать одну из строк кэша на основе политики замены.
Наборно-ассоциативный кеш
Наборно-ассоциативный кеш - это компромисс между кешем с прямым отображением и полностью ассоциативным кешем.
Наборно-ассоциативный кэш можно представить как матрицу (n * m). Кэш разделен на «n» наборов, и каждый набор содержит «m» строк кэша. Блок памяти сначала отображается на набор, а затем помещается в любую строку кэша набора.
Диапазон кэшей от прямого отображения до полностью ассоциативных - это континуум уровней ассоциативности множеств. (Кэш с прямым отображением является односторонним ассоциативным по множеству и полностью ассоциативным кешем с м строки кеша м-ходовой набор-ассоциативный.)
Многие кэши процессоров в сегодняшних проектах являются либо с прямым отображением, либо с двухсторонней ассоциативной ассоциативностью по множеству, либо с четырехсторонней ассоциативной по множеству.[5]
Поместить блок в кеш
- Набор определяется индексными битами, полученными из адреса блока памяти.
- Блок памяти помещается в доступную строку кэша в идентифицированном наборе, а тег сохраняется в поле тега, связанном с этой строкой. Если все строки кэша в наборе заняты, то новые данные заменяют блок, идентифицированный через политика замены.
Чтобы найти слово в кеше
- Набор определяется индексными битами, полученными из адреса блока памяти.
- Биты тегов сравниваются с тегами всех строк кэша, присутствующих в выбранном наборе. Если тег соответствует какой-либо из строк кэша, это попадание в кеш, и возвращается соответствующая строка. Если тег не соответствует ни одной из строк, это означает промах в кэше, и данные запрашиваются со следующего уровня в иерархии памяти.
Преимущества
- Политика размещения - это компромисс между прямым отображением и полностью ассоциативным кешем.
- Он предлагает гибкость использования алгоритмы замены если происходит промах кеша.
Недостатки
- Политика размещения не будет эффективно использовать все доступные строки кэша и страдает от конфликт мисс.
Пример
Рассмотрим основную память объемом 16 килобайт, которая организована в виде 4-байтовых блоков, и двухсторонний ассоциативный кэш размером 256 байтов с размером блока 4 байта.
Поскольку каждый блок кэша имеет размер 4 байта и является двусторонним набором-ассоциативным, общее количество наборов в кэше составляет 256 / (4 * 2), что равно 32 наборам.
В этом примере есть 2 бита смещения, которые используются для адресации 4 байтов строки кэша; имеется 5 битов индекса, которые используются для адресации 32 наборов кеша; и есть 7 = (14 - (5 + 2)) бит тега, которые хранятся в теге для сопоставления с адресами из запросов кеша.
Адрес 0x0000 (тег - 000_0000, индекс - 0_0000, смещение - 00) отображается на блок 0 памяти и занимает набор 0 кеша. Блок занимает одну из строк кэша набора 0 и определяется политикой замены для кэша.
Адрес 0x0004 (тег - 000_0000, индекс - 0_0001, смещение - 00) отображается на блок 1 памяти и занимает одну из строк кэша набора 1 кэша.
Точно так же адрес 0x00FF (тег - 000_0001, индекс - 1_1111, смещение - 11) отображается на блок 63 памяти и занимает одну из строк кэша набора 31 кэша.
Адрес 0x0100 (тег - 000_0010, индекс - 0_0000, смещение - 00) отображается на блок 64 памяти и занимает одну из строк кэша набора 0 кэша.
Двухсторонний асимметричный ассоциативный кеш
Были предложены другие схемы, такие как перекошенный кеш,[8] где индекс для пути 0 является прямым, как указано выше, но индекс для пути 1 формируется с помощью хэш-функция. Хорошая хеш-функция обладает свойством, что адреса, которые конфликтуют с прямым сопоставлением, имеют тенденцию не конфликтовать при сопоставлении с хеш-функцией, и поэтому менее вероятно, что программа пострадает от неожиданно большого количества конфликтных пропусков из-за патологического доступа. шаблон. Обратной стороной является дополнительная задержка при вычислении хеш-функции.[9] Кроме того, когда приходит время загрузить новую строку и удалить старую, может быть трудно определить, какая существующая строка использовалась наименее недавно, потому что новая строка конфликтует с данными в разных индексах в каждом случае; LRU отслеживание неискаженных кешей обычно выполняется для каждого набора. Тем не менее, асимметрично-ассоциативные кэши имеют большие преимущества перед традиционными ассоциативно-множественными.[10]
Псевдоассоциативный кеш
Настоящий ассоциативный кеш-набор проверяет все возможные способы одновременно, используя что-то вроде память с адресацией по содержанию. Псевдоассоциативный кеш проверяет каждый возможный способ по очереди. Кэш хэш-повторного хеширования и ассоциативный кеш по столбцам являются примерами псевдоассоциативного кеша.
В обычном случае обнаружения попадания в первый тестируемый способ псевдоассоциативный кеш работает так же быстро, как кеш с прямым отображением, но он имеет гораздо более низкую частоту пропусков конфликтов, чем кеш с прямым отображением, ближе к частоте промахов полностью ассоциативного кеша.[9]
Смотрите также
Рекомендации
- ^ а б c d е «Основы кеширования» (PDF).
- ^ «Политики размещения кеша».
- ^ «Правила размещения».
- ^ Маттсон, Р.; Gecsei, J .; Slutz, D. R .; Трейгер, я (1970). «Методы оценки иерархий хранения». Журнал IBM Systems. 9 (2): 78–117. Дои:10.1147 / sj.92.0078.
- ^ а б c Солихин, Ян (2015). Основы параллельной многоядерной архитектуры. Тейлор и Фрэнсис. С. 136–141. ISBN 978-1482211184.
- ^ "Типы промахов кеша" (PDF).
- ^ «Полностью ассоциативный кэш».
- ^ Андре Сезнек (1993). «Случай для двусторонних асимметричных кешей». Новости компьютерной архитектуры ACM SIGARCH. 21 (2): 169–178. Дои:10.1145/173682.165152.
- ^ а б К. Козыракис. «Лекция 3: Расширенные методы кэширования» (PDF). Архивировано из оригинал (PDF) 7 сентября 2012 г.
- ^ Микроархитектура «Асимметрично-ассоциативные кеши имеют ... основные преимущества перед обычными ассоциативно-множественными кэшами».