Кэш процессора

Кэш ЦП — это аппаратный кеш, используемый центральным процессором (ЦП) компьютера для снижения средних затрат (времени или энергии) на доступ к данным из основной памяти . Кэш — это меньшая по размеру и более быстрая память, расположенная ближе к ядру процессора , в которой хранятся копии данных из часто используемых областей основной памяти . Большинство процессоров имеют иерархию из нескольких уровней кэша (L1, L2, часто L3 и редко даже L4) с различными кэшами для конкретных инструкций и данных на уровне 1. Кэш-память обычно реализуется в виде статической оперативной памяти (SRAM), в современных процессорах это наибольшая часть по площади кристалла, но SRAM не всегда используется для всех уровней (I- или D-кэша), или даже любой уровень, иногда некоторые последние или все уровни реализованы с помощью eDRAM .

Существуют и другие типы кешей (которые не учитываются в «размере кеша» наиболее важных кешей, упомянутых выше), такие как резервный буфер трансляции (TLB), который является частью блока управления памятью (MMU), который имеется у большинства процессоров.

Обзор

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

Многие современные настольные , серверные и промышленные процессоры имеют как минимум три независимых кэша:

Кэш инструкций (I-кэш)

Используется для ускорения выборки исполняемых инструкций.

Кэш данных (D-кэш)

Используется для ускорения получения и хранения данных; кэш данных обычно организован в виде иерархии нескольких уровней кэша (L1, L2 и т. д.; см. также многоуровневые кэши ниже).

Буфер локализации перевода (TLB)

Используется для ускорения преобразования виртуальных адресов в физические как для исполняемых инструкций, так и для данных. Для доступа как к инструкциям, так и к данным может быть предоставлен один TLB или отдельные TLB инструкций (ITLB) и TLB данных (DTLB). Однако кэш TLB является частью блока управления памятью (MMU) и не связан напрямую с кэшами ЦП.

История

Материнская плата компьютера NeXTcube (1990 г.). В нижнем краю изображения, слева от середины, находится процессор Motorola 68040 , работающий на частоте 25 МГц , с двумя отдельными кэшами первого уровня по 4 КиБ каждый на кристалле: один для инструкций и один для данных. Плата не имеет внешнего кэша L2.

Ранние примеры кэшей ЦП включают Atlas 2. и IBM System/360 Model 85. в 1960-е годы. Первые процессоры, использовавшие кеш, имели только один уровень кеша; в отличие от более позднего кеша уровня 1, он не был разделен на L1d (для данных) и L1i (для инструкций). Разделение кэша L1 началось в 1976 году с процессором IBM 801 . стал массовым в конце 1980-х годов, а в 1997 году вышел на рынок встраиваемых процессоров с ARMv5TE. стоимостью менее доллара В 2015 году даже процессоры разделяли кэш L1. У них также есть кэши L2, а для более крупных процессоров — кэши L3. Кэш L2 обычно не разделяется и действует как общий репозиторий для уже разделенного кэша L1. Каждое ядро ​​многоядерного процессора имеет выделенный кэш L1, который обычно не используется совместно ядрами. Кэш L2 и кэши более высокого уровня могут совместно использоваться ядрами. Кэш L4 в настоящее время встречается редко и обычно представляет собой динамическую память с произвольным доступом (DRAM) на отдельном кристалле или кристалле, а не статическую память с произвольным доступом (SRAM). Исключением является ситуация, когда eDRAM используется для всех уровней кэша, вплоть до L1. Исторически L1 также находился на отдельном кристалле, однако большие размеры кристалла позволяли интегрировать его, а также другие уровни кэша, за возможным исключением последнего уровня. Каждый дополнительный уровень кэша имеет тенденцию быть больше и оптимизирован по-разному.

Размер кэшей (как и исторически сложилось) обычно имеет степень: 2, 4, 8, 16 и т. д. КиБ ; при размерах до MiB (т. е. для больших размеров, не относящихся к L1), на очень раннем этапе шаблон нарушился, чтобы обеспечить возможность использования кэшей большего размера без необходимости прибегать к парадигме удвоения размера, например, Intel Core 2 Duo с кешем L2 объемом 3 MiB в апреле 2008 года. С кэшами L1 это произошло намного позже, поскольку их размер, как правило, все еще составляет небольшое количество КиБ. Однако IBM zEC12 2012 года является исключением: он имеет необычно большой для своего времени кэш данных L1 объемом 96 КиБ, а, например, IBM z13 имеет кэш инструкций L1 объемом 96 КиБ (и кеш данных L1 128 КиБ). Intel Ice Lake и процессоры на базе 2018 года выпуска, имеющие 48 КБ кэша данных L1 и 48 КБ кэша инструкций L1. В 2020 году некоторые процессоры Intel Atom (с числом ядер до 24) будут иметь (несколько) размеров кэш-памяти 4,5 МБ и 15 МБ.

Операция

Записи кэша

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

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

Политика

Политика замены

Основная статья: Политики замены кэша

Чтобы освободить место для новой записи в случае промаха в кэше, кэшу, возможно, придется удалить одну из существующих записей. Эвристика, которую он использует для выбора удаляемой записи, называется политикой замены. Фундаментальная проблема любой политики замены заключается в том, что она должна предсказать, какая существующая запись кэша с наименьшей вероятностью будет использоваться в будущем. Прогнозировать будущее сложно, поэтому не существует идеального метода выбора среди множества доступных политик замены. Одна популярная политика замены, «наименее недавно использовавшаяся» (LRU), заменяет запись, к которой обращались реже всего.

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

Написание политик

Основная статья: Кэш (вычисления) § Политики написания

Если данные записываются в кэш, в какой-то момент они также должны быть записаны в основную память; время этой записи называется политикой записи. В кэше со сквозной записью каждая запись в кэш приводит к записи в основную память. Альтернативно, в кэше с обратной записью или копированием записи не сразу отражаются в основной памяти, а вместо этого кэш отслеживает, какие места были перезаписаны, помечая их как «грязные» . Данные в этих местах записываются обратно в основную память только тогда, когда эти данные удаляются из кэша. По этой причине промах чтения в кэше обратной записи может иногда требовать двух обращений к памяти для обслуживания: один для первой записи «грязного» местоположения в основную память, а затем другой для чтения нового местоположения из памяти. Кроме того, запись в область основной памяти, которая еще не отображена в кэше обратной записи, может удалить уже загрязненную область, тем самым освобождая это пространство кэша для новой области памяти.

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

Кэшированные данные из основной памяти могут быть изменены другими объектами (например, периферийными устройствами, использующими прямой доступ к памяти (DMA) или другим ядром многоядерного процессора ), и в этом случае копия в кэше может стать устаревшей или несвежий. Альтернативно, когда ЦП в многопроцессорной системе обновляет данные в кэше, копии данных в кэшах, связанных с другими ЦП, становятся устаревшими. Протоколы связи между менеджерами кэша, обеспечивающие согласованность данных, известны как согласованности кэша протоколы .

Производительность кэша

Измерение производительности кэша стало важным в последнее время, когда разрыв в скорости между производительностью памяти и производительностью процессора увеличивается в геометрической прогрессии. Кэш был введен, чтобы уменьшить этот разрыв в скорости. Таким образом, знание того, насколько хорошо кэш способен преодолеть разрыв в скорости процессора и памяти, становится важным, особенно в высокопроизводительных системах. Частота попаданий в кеш и частота промахов в кеш играют важную роль в определении этой производительности. Для повышения производительности кэша снижение частоты промахов становится одним из необходимых шагов среди других шагов. Уменьшение времени доступа к кешу также повышает его производительность и помогает в оптимизации.

Процессор глохнет

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

Чтобы сохранить занятость ЦП в это время, использовались различные методы, включая выполнение вне очереди , при котором ЦП пытается выполнить независимые инструкции после инструкции, ожидающей данных о промахе в кэше. Другая технология, используемая многими процессорами, — это одновременная многопоточность (SMT), которая позволяет альтернативному потоку использовать ядро ​​ЦП, в то время как первый поток ожидает доступности необходимых ресурсов ЦП.

Ассоциативность

Иллюстрация различных способов кэширования ячеек памяти в определенных местах кеша.

Основная статья: Политики размещения кэша

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

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

В порядке от худшего, но простого к лучшему, но сложному:

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

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

При такой организации кэша каждое место в основной памяти может содержать только одну запись в кэше. Следовательно, кеш с прямым отображением также можно назвать «односторонним ассоциативным кешем». У него нет политики размещения как таковой, поскольку нет выбора, какое содержимое записи кэша следует удалить. Это означает, что если две локации соответствуют одной и той же записи, они могут постоянно вытеснять друг друга. Хотя кэш с прямым отображением и проще, он должен быть намного больше, чем ассоциативный, чтобы обеспечить сопоставимую производительность, и он более непредсказуем. Пусть x — номер блока в кеше, y — номер блока в памяти, а n — количество блоков в кеше, тогда отображение выполняется с помощью уравнения x = y mod n .

Двусторонний набор ассоциативного кэша

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

Спекулятивное исполнение

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

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

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

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

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

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

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

Многоколоночный кеш

По сравнению с кешем с прямым отображением, набор ассоциативного кэша имеет уменьшенное количество бит для индекса набора кэша, который отображается в набор кэша, в котором остается несколько путей или блоков, например, 2 блока для двухстороннего набора ассоциативного кэша и 4 блока для четырехстороннего ассоциативного кэша. По сравнению с кэшем прямого отображения неиспользуемые биты индекса кэша становятся частью битов тега. Например, двусторонний набор ассоциативных кэшей вносит в тег 1 бит, а четырехсторонний набор ассоциативных кэшей вносит в тег 2 бита. Основная идея многостолбцового кэша состоит в том, чтобы использовать индекс набора для сопоставления с набором кэша, как это делает обычный ассоциативный кэш наборов, и использовать добавленные биты тега для индексации пути в наборе. Например, в 4-путевом ассоциативном кэше наборов два бита используются для индексации пути 00, пути 01, пути 10 и пути 11 соответственно. Такая индексация двойного кэша называется «основным сопоставлением местоположений», и ее задержка эквивалентна доступу с прямым сопоставлением. Обширные эксперименты по проектированию многостолбцового кэша. показывает, что коэффициент попадания в основные места достигает 90%. Если сопоставление кэша конфликтует с блоком кэша в основном местоположении, существующий блок кэша будет перемещен в другой путь кэширования в том же наборе, который называется «выбранным местоположением». Поскольку новый индексированный блок кэша является блоком, который использовался последним (MRU), он помещается в основное место в многостолбцовом кэше с учетом временной локальности. Поскольку многоколоночный кэш предназначен для кэша с высокой ассоциативностью, количество способов в каждом наборе велико; таким образом, можно легко найти выбранное место в наборе. Индекс местоположения, выбранный дополнительным оборудованием, сохраняется для основного местоположения в блоке кэша.

Многостолбцовый кеш сохраняет высокий коэффициент попаданий из-за своей высокой ассоциативности и имеет сопоставимую низкую задержку с кэшем с прямым отображением из-за высокого процента попаданий в основных расположениях. Концепции основных локаций и выбранных локаций в многоколоночном кеше использовались в нескольких конструкциях кеша в чипе ARM Cortex R. Кэш-память Intel с прогнозированием пути, Реконфигурируемая многопутевая ассоциативная кэш-память IBM и выбор способа динамической замены кэша Oracle на основе битов табуляции адреса.

Структура записи кэша

Записи строк кэша обычно имеют следующую структуру:

ярлык

блок данных

биты флага

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

«Размер» кэша — это объем данных основной памяти, который он может хранить. Этот размер можно рассчитать как количество байтов, хранящихся в каждом блоке данных, умноженное на количество блоков, хранящихся в кэше. (Биты тега, флага и кода исправления ошибок не включены в размер, хотя они влияют на физическую область кэша.)

Эффективный адрес памяти, который идет вместе со строкой кэша (блоком памяти), разделяется ( от старшего до младшего бита ) на тег, индекс и смещение блока.

ярлык

индекс

смещение блока

Индекс описывает, в какой набор кэша были помещены данные. Длина индекса равна $\lceil \log _{2}(s)\rceil$ биты для наборов кэшей .

Смещение блока определяет желаемые данные в блоке сохраненных данных в строке кэша. Обычно эффективный адрес указывается в байтах, поэтому длина смещения блока равна $\lceil \log _{2}(b)\rceil$ бит, где b — количество байтов в блоке данных. Тег содержит старшие биты адреса, которые проверяются по всем строкам в текущем наборе (набор был получен по индексу), чтобы увидеть, содержит ли этот набор запрошенный адрес. Если это так, происходит попадание в кэш. Длина тега в битах следующая:

tag_length = address_length - index_length - block_offset_length

Некоторые авторы называют смещение блока просто «смещением». или «перемещение».

Пример

Исходный процессор Pentium 4 имел четырехпоточный ассоциативный кэш данных L1 размером 8 КиБ с 64-байтовыми блоками кэша. Следовательно, имеется 8 КиБ / 64 = 128 блоков кэша. Количество наборов равно количеству блоков кэша, делённому на количество способов ассоциативности, что приводит к 128/4 = 32 наборам, а значит, и 2. ⁵ = 32 различных индекса. Есть 2 ⁶ = 64 возможных смещения. Поскольку адрес ЦП имеет ширину 32 бита, это подразумевает 32–5–6 = 21 бит для поля тега.

Исходный процессор Pentium 4 также имел восьмипоточный ассоциативный встроенный кэш L2 размером 256 КиБ с блоками кэша по 128 байт. Это подразумевает 32–8–7 = 17 бит для поля тега.

Биты флагов

Кэш инструкций требует только одного бита флага для каждой записи строки кэша: действительный бит. Бит достоверности указывает, загружен ли блок кэша действительными данными.

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

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

Промах в кэше

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

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

Перевод адреса

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

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

Для целей настоящего обсуждения существуют три важные особенности трансляции адресов:

• Задержка: физический адрес доступен из MMU некоторое время, возможно, через несколько циклов, после того, как виртуальный адрес доступен из генератора адресов.
• Псевдонимы: несколько виртуальных адресов могут сопоставляться с одним физическим адресом. Большинство процессоров гарантируют, что все обновления этого единственного физического адреса будут происходить в программном порядке. Чтобы обеспечить эту гарантию, процессор должен гарантировать, что в любой момент времени в кэше находится только одна копия физического адреса.
• Детализация: виртуальное адресное пространство разбито на страницы. Например, виртуальное адресное пространство размером 4 ГиБ можно разделить на 1 048 576 страниц размером 4 КиБ, каждая из которых может быть отображена независимо. Может поддерживаться несколько размеров страниц; дополнительную информацию см . в виртуальной памяти .

Одна из первых систем виртуальной памяти, IBM M44/44X , требовала доступа к таблице сопоставлений, хранящейся в основной памяти, перед каждым программным доступом к основной памяти. Без кэша и с памятью таблицы сопоставления, работающей с той же скоростью, что и основная память, это эффективно снижает скорость доступа к памяти вдвое. Две ранние машины, которые использовали для отображения таблицу страниц в основной памяти, IBM System/360 Model 67 и GE 645 , имели небольшую ассоциативную память в качестве кэша для доступа к таблице страниц в памяти. Обе машины предшествовали первой машине с кэшем основной памяти, IBM System/360 Model 85 , поэтому первым аппаратным кэшем, используемым в компьютерной системе, был не кэш данных или инструкций, а скорее TLB.

Кэши можно разделить на четыре типа в зависимости от того, соответствует ли индекс или тег физическим или виртуальным адресам:

• Физически индексированные кэши с физическими тегами (PIPT) используют физический адрес как для индекса, так и для тега. Хотя это просто и позволяет избежать проблем с псевдонимами, это также медленно, поскольку необходимо найти физический адрес (что может привести к промаху TLB и доступу к основной памяти), прежде чем этот адрес можно будет найти в кеше.
• Виртуально индексированные кэши с виртуальными тегами (VIVT) используют виртуальный адрес как для индекса, так и для тега. Эта схема кэширования может привести к гораздо более быстрому поиску, поскольку не нужно сначала обращаться к MMU для определения физического адреса для данного виртуального адреса. Однако VIVT страдает от проблем с псевдонимами, когда несколько разных виртуальных адресов могут ссылаться на один и тот же физический адрес. В результате такие адреса будут кэшироваться отдельно, несмотря на обращение к одной и той же памяти, что приведет к проблемам с когерентностью. Хотя решения этой проблемы существуют они не работают для стандартных протоколов когерентности. Другая проблема — омонимы, когда один и тот же виртуальный адрес соответствует нескольким разным физическим адресам. Невозможно различить эти сопоставления, просто взглянув на сам виртуальный индекс, хотя потенциальные решения включают в себя: очистку кеша после переключения контекста , принудительное неперекрытие адресных пространств, маркировку виртуального адреса идентификатором адресного пространства (ASID ). Кроме того, существует проблема, заключающаяся в том, что сопоставления виртуального и физического могут измениться, что потребует очистки строк кэша, поскольку виртуальные устройства перестанут быть действительными. Все эти проблемы отсутствуют, если теги используют физические адреса (VIPT).
• Виртуально индексированные кэши с физическими тегами (VIPT) используют виртуальный адрес для индекса и физический адрес в теге. Преимущество по сравнению с PIPT заключается в более низкой задержке, поскольку строку кэша можно просматривать параллельно с трансляцией TLB, однако тег нельзя сравнивать до тех пор, пока не станет доступен физический адрес. Преимущество перед VIVT заключается в том, что, поскольку тег имеет физический адрес, кэш может обнаруживать омонимы. Теоретически VIPT требует больше битов тегов, поскольку некоторые биты индекса могут различаться между виртуальными и физическими адресами (например, бит 12 и выше для страниц размером 4 КиБ) и должны быть включены как в виртуальный индекс, так и в физический тег. На практике это не проблема, поскольку во избежание проблем с когерентностью кэши VIPT спроектированы так, чтобы не иметь таких индексных битов (например, путем ограничения общего количества бит для индекса и смещения блока до 12 для страниц размером 4 КиБ). ; это ограничивает размер кэшей VIPT размером страницы, умноженным на ассоциативность кэша.
• Физически индексированные кэши с виртуальными тегами (PIVT) в литературе часто утверждаются как бесполезные и несуществующие. Однако MIPS R6000 использует этот тип кэша как единственную известную реализацию. R6000 реализован на основе логики с эмиттерной связью , которая представляет собой чрезвычайно быструю технологию, не подходящую для больших объемов памяти, таких как TLB . R6000 решает эту проблему, помещая память TLB в зарезервированную часть кэша второго уровня, имеющую крошечный высокоскоростной «срез» TLB на кристалле. Кэш индексируется по физическому адресу, полученному из среза TLB. Однако, поскольку срез TLB транслирует только те биты виртуального адреса, которые необходимы для индексации кэша, и не использует никаких тегов, могут возникнуть ложные попадания в кэш, что решается путем маркировки виртуальным адресом.

Скорость этого повторения ( задержка загрузки ) имеет решающее значение для производительности ЦП, поэтому большинство современных кэшей уровня 1 виртуально индексируются, что, по крайней мере, позволяет поиску TLB MMU выполняться параллельно с выборкой данных из кэш-ОЗУ.

Но виртуальное индексирование — не лучший выбор для всех уровней кэша. Стоимость работы с виртуальными псевдонимами растет вместе с размером кэша, и в результате большинство кэшей уровня 2 и выше физически индексируются.

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

Проблемы с омонимами и синонимами

Кэш, основанный на виртуальном индексировании и тегировании, становится несогласованным после того, как один и тот же виртуальный адрес отображается в разные физические адреса ( омонимы ), что можно решить, используя физический адрес для тегирования или сохраняя идентификатор адресного пространства в строке кэша. Однако последний подход не помогает решить проблему синонимов , при которой несколько строк кэша в конечном итоге хранят данные для одного и того же физического адреса. Запись в такие места может привести к обновлению только одного места в кэше, в результате чего в остальных останутся противоречивые данные. Эту проблему можно решить, используя непересекающиеся структуры памяти для разных адресных пространств, иначе кэш (или его часть) должен очищаться при изменении сопоставления.

Виртуальные теги и подсказки

Большим преимуществом виртуальных тегов является то, что для ассоциативного кэша они позволяют продолжить сопоставление тегов до того, как будет выполнен виртуальный перевод в физический. Однако проверки согласованности и выселения представляют собой физический адрес для действий. Аппаратное обеспечение должно иметь некоторые средства преобразования физических адресов в индекс кэша, как правило, путем хранения физических тегов, а также виртуальных тегов. Для сравнения: кэш с физическими тегами не требует хранения виртуальных тегов, что проще. Когда сопоставление виртуального и физического удаляется из TLB, записи кэша с этими виртуальными адресами придется каким-то образом сбрасывать. Альтернативно, если записи кэша разрешены на страницах, не сопоставленных TLB, тогда эти записи придется сбрасывать, когда права доступа на этих страницах изменяются в таблице страниц.

Операционная система также может гарантировать, что никакие виртуальные псевдонимы не будут одновременно находиться в кэше. Операционная система обеспечивает эту гарантию, обеспечивая цветовую раскраску страницы, как описано ниже. Некоторые ранние процессоры RISC (SPARC, RS/6000) использовали этот подход. В последнее время он не использовался, поскольку стоимость оборудования для обнаружения и удаления виртуальных псевдонимов упала, а сложность программного обеспечения и снижение производительности из-за идеальной раскраски страниц возросли.

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

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

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

Возможно, максимальное сокращение количества виртуальных подсказок можно найти в Pentium 4 (ядра Willamette и Northwood). В этих процессорах виртуальная подсказка фактически состоит из двух бит, а кеш имеет четырехканальный ассоциативный набор. По сути, аппаратное обеспечение поддерживает простую перестановку виртуального адреса с индексом кэша, так что никакой памяти с адресацией по содержимому для выбора правильного из четырех способов выборки не требуется (CAM).

Раскраска страниц

Основная статья: Раскраска кэша

Большие физически индексированные кэши (обычно вторичные кэши) сталкиваются с проблемой: операционная система, а не приложение, контролирует, какие страницы конфликтуют друг с другом в кэше. Различия в распределении страниц от одной программы к другой приводят к различиям в шаблонах конфликтов кэша, что может привести к очень большим различиям в производительности программы. Эти различия могут очень затруднить получение согласованного и воспроизводимого времени для выполнения эталонного теста.

Чтобы понять проблему, рассмотрим процессор с физически индексированным кэшем уровня 2 с прямым отображением объемом 1 МБ и страницами виртуальной памяти размером 4 КБ. Последовательные физические страницы сопоставляются с последовательными местоположениями в кэше до тех пор, пока после 256 страниц шаблон не будет перенесен. Мы можем пометить каждую физическую страницу цветом от 0 до 255, чтобы указать, в каком месте кэша она может находиться. Места на физических страницах, имеющие разные цвета, не могут конфликтовать в кеше.

Программисты, пытающиеся максимально использовать кэш, могут организовать шаблоны доступа своих программ так, чтобы в любой момент времени нужно было кэшировать только 1 МБ данных, что позволяет избежать нехватки емкости. Но они также должны гарантировать, что шаблоны доступа не содержат конфликтных промахов. Один из способов решить эту проблему — разделить виртуальные страницы, используемые программой, и назначить им виртуальные цвета таким же образом, как раньше физические цвета назначались физическим страницам. Затем программисты могут организовать шаблоны доступа своего кода так, чтобы никакие две страницы с одинаковым виртуальным цветом не использовались одновременно. Существует обширная литература по таким оптимизациям (например, оптимизации гнезд циклов ), в основном исходящая от сообщества высокопроизводительных вычислений (HPC) .

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

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

Если операционная система может гарантировать, что каждая физическая страница отображается только в один виртуальный цвет, то виртуальных псевдонимов не существует, и процессор может использовать виртуально индексированные кэши без необходимости дополнительных проверок виртуальных псевдонимов во время обработки ошибок. Альтернативно, ОС может сбрасывать страницу из кеша всякий раз, когда она меняет один виртуальный цвет на другой. Как упоминалось выше, этот подход использовался в некоторых ранних разработках SPARC и RS/6000.

Техника раскраски программных страниц использовалась для эффективного разделения общего кэша последнего уровня (LLC) в многоядерных процессорах. Это управление LLC на основе операционной системы в многоядерных процессорах было принято Intel.

Иерархия кэша в современном процессоре

Иерархия памяти сервера AMD Bulldozer

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

Хотя все блоки кэша в конкретном кэше имеют одинаковый размер и одинаковую ассоциативность, обычно кэши «нижнего уровня» (называемые кэшем уровня 1) имеют меньшее количество блоков, меньший размер блока и меньшее количество блоков в кэше. установлены, но имеют очень короткое время доступа. Кэши «более высокого уровня» (т. е. уровень 2 и выше) имеют постепенно большее количество блоков, больший размер блока, больше блоков в наборе и относительно большее время доступа, но все равно работают намного быстрее, чем основная память.

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

Специализированные кэши

Конвейерные процессоры обращаются к памяти из нескольких точек конвейера : выборка инструкций, преобразование виртуальных адресов в физические и выборка данных (см. классический RISC-конвейер ). Естественным решением является использование разных физических кэшей для каждой из этих точек, чтобы ни один физический ресурс не был запланирован для обслуживания двух точек конвейера. Таким образом, в конвейере естественным образом образуется как минимум три отдельных кэша (инструкций, TLB и данных), каждый из которых специализируется на своей конкретной роли.

Тайник жертвы

Основная статья: Тайник жертв

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

от Intel Кристаллвелл Вариант процессоров Haswell представил встроенный кеш- память eDRAM уровня 4 емкостью 128 МБ, который служит кэшем-жертвой для кэша уровня 3 процессора. В микроархитектуре Skylake кэш 4-го уровня больше не работает как кэш жертвы.

Трассировка кэша

Основная статья: Кэш трассировки

Одним из наиболее крайних примеров специализации кэша является кэш трассировки (также известный как кэш трассировки выполнения ), обнаруженный в микропроцессорах Intel Pentium 4 . Кэш трассировки — это механизм увеличения пропускной способности выборки команд и снижения энергопотребления (в случае Pentium 4) за счет хранения следов инструкций , которые уже были выбраны и декодированы.

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

Объединенный кэш записи (WCC)

Запись объединяющего кэша Это специальный кэш, который является частью кэша L2 в AMD Bulldozer микроархитектуре . Хранилища из обоих кэшей L1D в модуле проходят через WCC, где они буферизуются и объединяются. Задача WCC — сократить количество операций записи в кэш L2.

Кэш микроопераций (μop или uop)

( Кэш микроопераций кэш µop , кеш uop или UC ) представляет собой специализированный кэш, в котором хранятся микрооперации декодированных инструкций, полученных непосредственно от декодеров инструкций или из кэша инструкций. Когда инструкцию необходимо декодировать, кэш µop проверяется на предмет ее декодированной формы, которая используется повторно, если она кэширована; если он недоступен, инструкция декодируется, а затем кэшируется.

Одной из первых работ, описывающих кэш µop как альтернативный интерфейс для семейства процессоров Intel P6, является статья 2001 года «Кэш микроопераций: интерфейс с учетом энергопотребления для ISA с переменной длиной инструкций» . Позже Intel включила кэши µop в свои процессоры Sandy Bridge и в последующие микроархитектуры, такие как Ivy Bridge и Haswell . AMD реализовала кэш µop в своей микроархитектуре Zen .

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

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

Кэш инструкций целевой ветви

Кэш целевой ветки или кэш инструкций целевой ветки — название, используемое в микропроцессорах ARM . представляет собой специализированный кэш, в котором хранятся первые несколько инструкций в месте назначения выбранной ветки. Это используется маломощными процессорами, которым не нужен обычный кэш инструкций, поскольку система памяти способна доставлять инструкции достаточно быстро, чтобы удовлетворить ЦП без него. Однако это применимо только к последовательным инструкциям; для перезапуска выборки инструкций по новому адресу по-прежнему требуется несколько циклов задержки, что приводит к появлению нескольких циклов «пузыря» конвейера после передачи управления. Кэш цели ветвления предоставляет инструкции для этих нескольких циклов, избегая задержки после большинства выполненных ветвей.

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

Умный кэш

Интеллектуальный кэш — это метод кэширования уровня 2 или 3 для нескольких исполнительных ядер, разработанный Intel .

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

Многоуровневые кэши

См. также: Иерархия кэша.

Другая проблема — фундаментальный компромисс между задержкой кэша и частотой попаданий. Кеши большего размера имеют более высокую частоту попаданий, но более длительную задержку. Чтобы решить эту проблему, многие компьютеры используют несколько уровней кэша: небольшие быстрые кэши подкреплены более крупными и медленными кэшами. Многоуровневые кэши обычно работают, сначала проверяя самый быстрый кэш, уровень 1 ( L1 ); если он попадает, процессор продолжает работать на высокой скорости. следующий самый быстрый кеш, уровень 2 ( L2 Если этот меньший кеш отсутствует, перед доступом к внешней памяти проверяется ) и так далее.

Поскольку разница в задержке между основной памятью и самым быстрым кэшем стала больше, некоторые процессоры начали использовать до трех уровней встроенного кэша. Чувствительные к цене конструкции использовали это для переноса всей иерархии кэша на кристалл, но к 2010-м годам некоторые из самых высокопроизводительных проектов вернулись к использованию больших внешних кэшей, которые часто реализуются в eDRAM и монтируются на многокристальном модуле. , в качестве четвертого уровня кэша. В редких случаях, например, в процессоре мэйнфрейма IBM z15 (2019 г.), все уровни вплоть до L1 реализуются с помощью eDRAM, полностью заменяя SRAM (для кэша SRAM по-прежнему используется для регистров). Apple на базе ARM M1 имеет кэш-память L1 объемом 192 КиБ для каждого из четырех высокопроизводительных ядер, что является необычно большим объемом; однако четыре высокоэффективных ядра имеют только 128 КиБ.

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

• Alpha 21164 (1995) имела внешнюю кэш-память L3 от 1 до 64 МБ.
• AMD K6-III (1999) имел кэш-память L3 на материнской плате.
• IBM POWER4 (2001) имел внекристальные кэши L3 объемом 32 МБ на процессор, которые использовались несколькими процессорами.
• Itanium 2 кэш уровня 3 (L3) емкостью 6 МБ унифицированный (2003) имел встроенный ; Модуль Itanium 2 (2003) MX 2 включал в себя два процессора Itanium 2 вместе с общим кэшем L4 емкостью 64 МБ на многочиповом модуле , который был совместим по выводам с процессором Madison.
• Продукт Intel Xeon MP под кодовым названием «Tulsa» (2006 г.) имеет 16 МБ встроенной кэш-памяти L3, разделяемой между двумя ядрами процессора.
• AMD Phenom (2007 г.) с 2 МБ кэш-памяти L3.
• AMD Phenom II (2008 г.) имеет встроенную унифицированную кэш-память L3 объемом до 6 МБ.
• Intel Core i7 (2008 г.) имеет встроенный унифицированный кэш L3 емкостью 8 МБ, который является общим для всех ядер.
• Процессоры Intel Haswell со встроенной графикой Intel Iris Pro имеют 128 МБ eDRAM, действующей по сути как кэш L4.

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

Файлы регистров иногда также имеют иерархию: Cray-1 (около 1976 г.) имел восемь регистров адреса «A» и восемь регистров скалярных данных «S», которые обычно можно было использовать. Также существовал набор из 64 регистров адреса «B» и 64 регистров скалярных данных «T», доступ к которым требовал больше времени, но был быстрее, чем основная память. Регистры «B» и «T» были предусмотрены, потому что Cray-1 не имел кэша данных. (Однако у Cray-1 был кэш инструкций.)

Многоядерные чипы

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

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

Общий кеш высшего уровня, который вызывается перед доступом к памяти, обычно называется кешем последнего уровня (LLC). Дополнительные методы используются для повышения уровня параллелизма, когда LLC распределяется между несколькими ядрами, включая разделение его на несколько частей, которые обращаются к определенным диапазонам адресов памяти и могут быть доступны независимо.

Отдельный против единого

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

Эксклюзивный против инклюзивного

Многоуровневые кэши представляют новые дизайнерские решения. Например, в некоторых процессорах все данные в кэше L1 также должны находиться где-то в кэше L2. Эти кэши называются строго инклюзивными . Другие процессоры (например, AMD Athlon ) имеют эксклюзивные кэши: данные гарантированно находятся не более чем в одном из кэшей L1 и L2, но никогда в обоих. Тем не менее, другие процессоры (например, Intel Pentium II , III и 4 ) не требуют, чтобы данные из кэша L1 также находились в кэше L2, хотя часто это может быть так. Для этой промежуточной политики не существует общепринятого названия; два общих названия: «неисключительные» и «частично включающие».

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

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

Еще одним преимуществом инклюзивного кэша является то, что больший кэш может использовать более крупные строки кэша, что уменьшает размер тегов вторичного кэша. (Эксклюзивные кэши требуют, чтобы оба кэша имели строки кэша одинакового размера, чтобы строки кэша можно было менять местами при промахе L1 или попадании L2.) Если вторичный кэш на порядок больше основного, а данные кэша являются на порядок больше, чем теги кэша, эта сохраненная область тегов может быть сопоставима с дополнительной областью, необходимой для хранения данных кэша L1 в L2.

Блокнот памяти

Основная статья: Блокнот памяти

Блокнотная память (SPM), также известная как блокнот, блокнот RAM или локальное хранилище в компьютерной терминологии, представляет собой высокоскоростную внутреннюю память, используемую для временного хранения вычислений, данных и другой незавершенной работы.

Пример: К8

Чтобы проиллюстрировать как специализацию, так и многоуровневое кэширование, ниже представлена ​​иерархия кэша ядра K8 процессора AMD Athlon 64 .

Иерархия кэша ядра K8 в процессоре AMD Athlon 64

K8 имеет четыре специализированных кэша: кэш инструкций, TLB инструкций , TLB данных и кэш данных. Каждый из этих кешей специализирован:

• Кэш инструкций хранит копии 64-байтовых строк памяти и извлекает 16 байт за каждый цикл. Каждый байт в этом кэше хранится в десяти битах, а не в восьми, причем дополнительные биты обозначают границы инструкций (это пример предварительного декодирования). Кэш имеет только защиту четности, а не ECC , поскольку четность меньше, и любые поврежденные данные могут быть заменены свежими данными, полученными из памяти (в которой всегда есть актуальная копия инструкций).
• Инструкция TLB сохраняет копии записей таблицы страниц (PTE). При выборке инструкций каждого цикла виртуальный адрес преобразуется через этот TLB в физический адрес. Каждая запись занимает в памяти четыре или восемь байтов. Поскольку K8 имеет переменный размер страницы, каждый из TLB разделен на две части: одна для хранения PTE, отображающих страницы размером 4 КиБ, и одна для хранения PTE, отображающих страницы размером 4 или 2 МБ. Разделение позволяет упростить полностью ассоциативную схему согласования в каждой секции. Операционная система сопоставляет различные разделы виртуального адресного пространства с PTE разного размера.
• TLB данных имеет две копии, которые содержат идентичные записи. Две копии позволяют два доступа к данным за цикл для преобразования виртуальных адресов в физические адреса. Как и инструкция TLB, этот TLB разделен на два типа записей.
• Кэш данных хранит копии 64-байтовых строк памяти. Он разделен на 8 банков (каждый из которых хранит 8 КиБ данных) и может извлекать два 8-байтовых данных за каждый цикл, если эти данные находятся в разных банках. Существует две копии тегов, поскольку каждая 64-байтовая строка распределена по всем восьми банкам. Каждая копия тега обрабатывает один из двух доступов за цикл.

K8 также имеет многоуровневый кэш. Существуют TLB инструкций и данных второго уровня, которые хранят только PTE, отображающие 4 КиБ. Кэш инструкций и данных, а также различные TLB могут заполняться из большого унифицированного кэша L2. Этот кеш является эксклюзивным как для кэшей инструкций L1, так и для кэшей данных, что означает, что любая 8-байтовая строка может находиться только в одном из кэша инструкций L1, кэша данных L1 или кэша L2. Однако строка в кэше данных может иметь PTE, который также находится в одном из TLB — операционная система отвечает за поддержание согласованности TLB, сбрасывая их части при обновлении таблиц страниц в памяти.

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

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

Больше иерархий

Другие процессоры имеют другие типы предсказателей (например, предиктор обхода сохранения-загрузки в DEC Alpha 21264 ), и различные специализированные предсказатели, вероятно, будут процветать в будущих процессорах.

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

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

День ОЗУ

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

Выполнение

Основная статья: Алгоритмы кэширования

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

Самый простой кеш — это виртуально индексированный кеш с прямым отображением. Виртуальный адрес вычисляется с помощью сумматора, соответствующая часть адреса извлекается и используется для индексации SRAM, которая возвращает загруженные данные. Данные выравниваются по байтам в устройстве сдвига байтов и оттуда передаются к следующей операции. Во внутреннем цикле нет необходимости проверять теги – более того, теги даже не нужно читать. На более позднем этапе конвейера, но до того, как инструкция загрузки будет удалена, тег загруженных данных должен быть прочитан и сверен с виртуальным адресом, чтобы убедиться, что произошло попадание в кэш. В случае промаха кеш обновляется запрошенной строкой кэша, и конвейер перезапускается.

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

Путь чтения для двустороннего ассоциативного кэша

Прилегающая диаграмма предназначена для пояснения способа использования различных полей адреса. Бит адреса 31 является наиболее значимым, бит 0 — наименее значимым. На диаграмме показаны SRAM, индексирование и мультиплексирование для двухстороннего наборно-ассоциативного, виртуально индексированного и виртуально тегированного кэша емкостью 4 КиБ со строками длиной 64 байта (B), 32-битной шириной чтения и 32-битным виртуальным адресом.

Поскольку размер кэша составляет 4 КиБ и он имеет 64 строки B, в кеше всего 64 строки, и мы читаем по две за раз из SRAM-памяти тегов, которая имеет 32 строки, каждая из которых содержит пару 21-битных тегов. Хотя для индексации тегов и SRAM данных можно использовать любую функцию битов виртуального адреса с 31 по 6, проще всего использовать младшие биты.

Аналогичным образом, поскольку размер кэша составляет 4 КиБ, путь чтения составляет 4 байт, а для каждого доступа считывается двумя способами, SRAM данных имеет размер 512 строк по 8 байт.

Более современный кеш может иметь размер 16 КиБ, 4-сторонний набор-ассоциативный, виртуально индексируемый, виртуально хинтованный и физически помеченный, с 32 строками B, 32-битной шириной чтения и 36-битными физическими адресами. Повторение пути чтения для такого кэша очень похоже на путь выше. Вместо тегов считываются vhints и сопоставляются с подмножеством виртуального адреса. Позже в конвейере виртуальный адрес преобразуется в физический адрес с помощью TLB, и считывается физический тег (только один, поскольку vhint указывает, какой путь из кэша следует читать). Наконец, физический адрес сравнивается с физическим тегом, чтобы определить, произошло ли попадание.

В некоторых конструкциях SPARC скорость кэшей L1 повышена за счет нескольких задержек на вентилях за счет объединения сумматора виртуальных адресов в декодерах SRAM. См. декодер с адресацией суммы .

История

Ранняя история технологии кэширования тесно связана с изобретением и использованием виртуальной памяти. Из-за нехватки и стоимости полупроводниковой памяти первые мэйнфреймы 1960-х годов использовали сложную иерархию физической памяти, отображаемую на плоское пространство виртуальной памяти, используемое программами. Технологии памяти будут охватывать полупроводники, магнитные сердечники, барабаны и диски. Виртуальная память, видимая и используемая программами, будет плоской, а кэширование будет использоваться для извлечения данных и инструкций в самую быструю память перед доступом к процессору. Были проведены обширные исследования для оптимизации размеров кэша. Было обнаружено, что оптимальные значения во многом зависят от используемого языка программирования: для Алгола требуется наименьший размер кэша, а для Фортрана и Кобола — наибольший размер кэша.

На заре развития микрокомпьютерных технологий доступ к памяти был лишь немного медленнее, чем доступ к регистрам . Но с 1980-х гг. Разрыв в производительности между процессором и памятью растет. Микропроцессоры развивались гораздо быстрее, чем память, особенно с точки зрения их рабочей частоты , поэтому память стала узким местом в производительности . Хотя технически было возможно сделать всю основную память такой же быстрой, как процессор, был выбран более экономически выгодный путь: использовать много низкоскоростной памяти, но также ввести небольшую высокоскоростную кэш-память, чтобы уменьшить разрыв в производительности. Это обеспечило на порядок большую емкость — за ту же цену — лишь с небольшим снижением совокупной производительности.

Первые реализации TLB

Первое задокументированное использование TLB было на GE 645. и IBM 360/67 , оба из которых использовали ассоциативную память в качестве TLB.

Первый кэш инструкций

Первое задокументированное использование кэша инструкций было на CDC 6600 .

Первый кэш данных

Первое задокументированное использование кэша данных было в IBM System/360 Model 85.

В микропроцессорах 68k

68010 . , выпущенный в 1982 году, имеет «режим цикла», который можно рассматривать как крошечный кэш инструкций особого случая, который ускоряет циклы, состоящие только из двух инструкций Модель 68020 , выпущенная в 1984 году, заменила ее типичным кэшем инструкций размером 256 байт, став первым процессором серии 68k, имеющим настоящую встроенную кэш-память.

68030 ( MMU , выпущенный в 1987 году, по сути представляет собой ядро ​​68020 с дополнительным 256-байтовым кэшем данных, встроенным блоком управления памятью ), сжатием процесса и добавленным пакетным режимом для кэшей.

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

68060 . , выпущенный в 1994 году, имеет следующее: кэш данных 8 КиБ (четырехсторонняя ассоциативность), кэш инструкций 8 КиБ (четырехсторонняя ассоциативность), 96-байтовый буфер инструкций FIFO, кэш ветвей на 256 записей и 64 записи Буфер MMU кэша трансляции адресов (четырехсторонний ассоциативный).

В микропроцессорах x86

Пример материнской платы с микропроцессором i386 (33 МГц), кэшем 64 КиБ (25 нс; 8 микросхем в левом нижнем углу), 2 МиБ DRAM (70 нс; 8 SIMM справа от кэша) и контроллером кэша. ( Austek A38202; справа от процессора)

Когда микропроцессоры x86 достигли тактовой частоты 20 МГц и выше в 386 , в системах начали использоваться небольшие объемы быстрой кэш-памяти для повышения производительности. Это произошло потому, что DRAM, используемая для основной памяти, имела значительную задержку, до 120 нс, а также циклы обновления. Кэш был построен из более дорогих, но значительно более быстрых SRAM ячеек памяти , задержки которых в то время составляли около 10–25 нс. Ранние кэши были внешними по отношению к процессору и обычно располагались на материнской плате в виде восьми или девяти DIP- устройств, помещенных в разъемы, чтобы использовать кэш в качестве дополнительной опции или функции обновления.

Некоторые версии процессора Intel 386 могут поддерживать внешний кэш объемом от 16 до 256 КиБ.

В процессоре 486 кэш-память емкостью 8 КиБ была интегрирована непосредственно в кристалл ЦП. Этот кеш был назван кешем уровня 1 или L1, чтобы отличать его от более медленного кэша материнской платы или кеша уровня 2 (L2). Эти кэши на материнской плате были намного больше, наиболее распространенный размер составлял 256 КиБ. Были некоторые системные платы, на которых были разъемы для дочерней карты Intel 485Turbocache с 64 или 128 Кбайт кэш-памяти. Популярность кэша на материнской плате сохранялась в эпоху Pentium MMX , но он устарел из-за появления SDRAM и растущего несоответствия между тактовой частотой шины и тактовой частотой процессора, из-за чего кэш на материнской плате был лишь немного быстрее основной памяти.

Следующее развитие реализации кэша в микропроцессорах x86 началось с Pentium Pro , в котором вторичный кэш был помещен в тот же корпус, что и микропроцессор, и работал на той же частоте, что и микропроцессор.

Кэш-память на материнской плате пользовалась продолжительной популярностью благодаря процессорам AMD K6-2 и AMD K6-III , которые все еще использовали Socket 7 , который ранее использовался Intel для кэшей на материнской плате. K6-III включал встроенный кэш L2 емкостью 256 КиБ и использовал встроенный кэш в качестве кэша третьего уровня, получившего название L3 (производились материнские платы с встроенным кэшем объемом до 2 МБ). После того, как Socket 7 устарел, кэш материнской платы исчез из систем x86.

Трехуровневые кэши были снова использованы сначала с появлением нескольких ядер процессора, когда к кристаллу ЦП был добавлен кэш L3. В новых поколениях процессоров общий размер кэша становится все больше, и в последнее время (по состоянию на 2011 год) нередко можно обнаружить размеры кэша 3-го уровня, составляющие десятки мегабайт.

Intel представила встроенный кэш уровня 4 с Haswell микроархитектурой . Кристалвелл Процессоры Haswell, оснащенные вариантом GT3e встроенной графики Intel Iris Pro, фактически имеют 128 МБ встроенной памяти DRAM ( eDRAM ) в том же корпусе. Этот кэш L4 динамически распределяется между встроенным графическим процессором и процессором и служит кэшем-жертвой для кэша L3 процессора.

В микропроцессорах ARM

Процессор Apple M1 имеет кэш-память L1 инструкций объемом 128 или 192 КиБ для каждого ядра (важно для задержки/однопоточной производительности), в зависимости от типа ядра. Это необычно большой кэш L1 для любого типа процессора (не только для ноутбука); Общий размер кэш-памяти не является необычно большим (общий объем более важен для пропускной способности) для ноутбука, а в мэйнфреймах IBM доступны гораздо большие общие размеры (например, L3 или L4).

Текущие исследования

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

Компьютерным архитекторам доступно несколько инструментов, которые помогут найти компромисс между временем цикла кэша, энергией и площадью; симулятор кэша CACTI и симулятор набора команд SimpleScalar — это два варианта с открытым исходным кодом.

Многопортовый кэш

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

См. также

• Предиктор ветвей
• Кэш (вычисления)
• Алгоритмы кэширования
• Согласованность кэша
• Инструкции по управлению кэшем
• Иерархия кэша
• Политики размещения кэша
• Предварительная выборка кэша
• Dinero (симулятор кэша от системы Университета Висконсина )
• Инструкция
• Местоположение ссылки
• Мемоизация
• Иерархия памяти
• Микрооперация
• Распределение без записи
• Блокнот ОЗУ
• Декодер с суммарной адресацией
• Буфер записи

Внешние ссылки

• Память, часть 2: Кеши ЦП - статья Ульриха Дреппера на lwn.net, подробно описывающая кеши ЦП.
• Оценка ассоциативности в кэшах ЦП - Хилл и Смит (1989) - представляет емкость, конфликты и обязательную классификацию.
• Производительность кэша для тестов SPEC CPU2000 – Hill and Cantin (2003) – Этот справочный документ обновлялся несколько раз. В нем подробно и наглядно представлены результаты моделирования для достаточно широкого набора тестов и организаций кэша.
• Иерархия памяти в системах на основе кэша. Архивировано 15 сентября 2009 г. в Wayback Machine - Рууд ван дер Пас, 2002 г., Sun Microsystems - вводная статья по кэшированию памяти ЦП.
• Учебник по кэшу – Пол Генуа, PE, 2004, Freescale Semiconductor, еще одна вводная статья.
• 8-канальный ассоциативный кеш , написанный на VHDL.
• Понимание кэширования и производительности ЦП – статья Джона Стоукса об Ars Technica
• Обзор процессора IBM POWER4 — статья Павла Данилова на ixbtlabs
• Что такое кэш-память и ее виды!
• Кэширование памяти – лекция Принстонского университета