Кэш-память центрального процессора

Кэш ЦП: ускорение работы компьютера за счет хранения часто используемых данных. Узнайте о уровнях кэша (L1, L2, L3), SRAM и TLB. Оптимизация производительности!

40 мин чтения

100%

Источник: CPU cache — Wikipedia

Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.

Содержание

Введение

Кэш-память центрального процессора
Кэш-память центрального процессора (CPU) – это аппаратный кэш, используемый центральным процессором (CPU) компьютера для снижения средней стоимости (по времени или энергозатратам) доступа к данным из основной памяти. Кэш представляет собой меньшую, более быструю память, расположенную ближе к ядру процессора, которая хранит копии данных из часто используемых областей основной памяти. Большинство процессоров имеют иерархию нескольких уровней кэша (L1, L2, часто L3 и редко даже L4), с различными кэшами, оптимизированными для инструкций и данных, на первом уровне. Кэш-память обычно реализована на статической оперативной памяти (SRAM), которая в современных процессорах занимает большую часть площади кристалла. Однако SRAM не всегда используется для всех уровней (кэша инструкций или данных), или даже для какого-либо уровня; иногда некоторые последующие или все уровни реализуются с использованием eDRAM. Существуют и другие типы кэшей (которые не включаются в "объем кэша" наиболее важных кэшей, упомянутых выше), такие как буфер трансляции Lookaside (TLB), являющийся частью блока управления памятью (MMU), который имеется в большинстве процессоров.

История

Ранние примеры кэшей CPU включают Atlas 2 и IBM System/360 Model 85 в 1960-х годах. Первые процессоры, использовавшие кэш, имели только один уровень кэша; в отличие от более позднего кэша уровня 1, он не был разделен на L1d (для данных) и L1i (для инструкций). Разделение L1-кэша началось в 1976 году с процессора IBM 801, стало распространенным в конце 1980-х годов, а в 1997 году проникло на рынок встраиваемых процессоров с ARMv5TE. В 2015 году даже SoC стоимостью менее одного доллара использовали разделенный L1-кэш. Они также имеют L2-кэши и, для более крупных процессоров, L3-кэши. L2-кэш обычно не разделяется и служит общим хранилищем для уже разделенного L1-кэша. Каждое ядро многоядерного процессора имеет выделенный L1-кэш и обычно не разделяется между ядрами. L2-кэш и кэши более высоких уровней могут быть общими для ядер. L4-кэш в настоящее время встречается редко и обычно представляет собой динамическую память с произвольным доступом (DRAM) на отдельной матрице или чипе, а не статическую память с произвольным доступом (SRAM). Исключением является использование eDRAM для всех уровней кэша, вплоть до L1. Исторически L1 также размещался на отдельной матрице, однако увеличение размеров матриц позволило интегрировать его, а также другие уровни кэша, за исключением последнего. Каждый дополнительный уровень кэша, как правило, больше и оптимизирован по-разному. Кэши (как и оперативная память исторически) обычно имеют размер, кратный степеням: 2, 4, 8, 16 и т. д. KiB; при достижении размеров в MiB (т.е. для более крупных кэшей, отличных от L1) эта закономерность нарушилась, чтобы обеспечить возможность создания более крупных кэшей без принудительного удвоения размера, например, Intel Core 2 Duo с 3 MiB L2-кэшем в апреле 2008 года. Это произошло гораздо позже для L1-кэшей, поскольку их размер обычно остается небольшим, измеряемым в KiB. IBM zEC12 2012 года выпуска является исключением, получив необычно большой для своего времени 96 KiB L1-кэш данных, и, например, IBM z13 с 96 KiB L1-кэшем инструкций (и 128 KiB L1-кэшем данных), а также процессоры Intel Ice Lake 2018 года выпуска с 48 KiB L1-кэшем данных и 48 KiB L1-кэшем инструкций. В 2020 году некоторые процессоры Intel Atom (с 24 ядрами) имеют размеры кэша, кратные 4,5 MiB и 15 MiB.

Early examples of CPU caches include the Atlas 2 and the IBM System/360 Model 85 in the 1960s. The first CPUs that used a cache had only one level of cache; unlike later level 1 cache, it was not split into L1d (for data) and L1i (for instructions). Split L1 cache started in 1976 with the IBM 801 CPU, became mainstream in the late 1980s, and in 1997 entered the embedded CPU market with the ARMv5TE. In 2015, even sub dollar SoCs split the L1 cache. They also have L2 caches and, for larger processors, L3 caches as well. The L2 cache is usually not split, and acts as a common repository for the already split L1 cache. Every core of a multi core processor has a dedicated L1 cache and is usually not shared between the cores. The L2 cache, and higher level caches, may be shared between the cores. L4 cache is currently uncommon, and is generally dynamic random access memory (DRAM) on a separate die or chip, rather than static random access memory (SRAM). An exception to this is when eDRAM is used for all levels of cache, down to L1. Historically L1 was also on a separate die, however bigger die sizes have allowed integration of it as well as other cache levels, with the possible exception of the last level. Each extra level of cache tends to be bigger and optimized differently. Caches (like for RAM historically) have generally been sized in powers of: 2, 4, 8, 16 etc. KiB; when up to MiB sizes (i. e. for larger non L1), very early on the pattern broke down, to allow for larger caches without being forced into the doubling in size paradigm, with e. g. Intel Core 2 Duo with 3 MiB L2 cache in April 2008. This happened much later for L1 caches, as their size is generally still a small number of KiB. The IBM zEC12 from 2012 is an exception however, to gain unusually large 96 KiB L1 data cache for its time, and e. g. the IBM z13 having a 96 KiB L1 instruction cache (and 128 KiB L1 data cache), and Intel Ice Lake based processors from 2018, having 48 KiB L1 data cache and 48 KiB L1 instruction cache. In 2020, some Intel Atom CPUs (with up to 24 cores) have (multiple of) 4.5 MiB and 15 MiB cache sizes.

Записи в кэше

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

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

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

Написать политику

Если данные записываются в кэш, в какой-то момент они также должны быть записаны в основную память; момент этой записи определяется политикой записи. В кэше с прямой записью (write-through) каждая запись в кэш вызывает немедленную запись в основную память. В качестве альтернативы, в кэше с обратной записью (write-back) или копированием записи (copy-back) записи не отражаются в основной памяти немедленно, а кэш отслеживает, какие блоки были изменены, помечая их как "грязные". Данные в этих блоках записываются обратно в основную память только при вытеснении из кэша. По этой причине промах чтения (read miss) в кэше с обратной записью может потребовать двух обращений к памяти: сначала для записи "грязного" блока в основную память, а затем для чтения нового блока из памяти. Кроме того, запись в область основной памяти, которая ещё не отображена в кэше с обратной записью, может привести к вытеснению уже "грязного" блока, освобождая место в кэше для новой области памяти. Существуют также промежуточные политики. Кэш может использовать прямую запись, но записи могут временно храниться в очереди хранения данных (store data queue), обычно для пакетной обработки нескольких записей (что позволяет снизить время разворота шины и повысить её эффективность). Кэшированные данные в основной памяти могут быть изменены другими сущностями (например, периферийными устройствами, использующими прямой доступ к памяти (DMA), или другим ядром в многоядерном процессоре), в этом случае копия в кэше может устареть. Кроме того, когда центральный процессор (CPU) в многопроцессорной системе обновляет данные в кэше, копии данных в кэшах, связанных с другими CPU, становятся недействительными. Протоколы обмена данными между контроллерами кэша, обеспечивающие согласованность данных, называются протоколами когерентности кэша.

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

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

Стойки процессора

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

Прямое отображение кэша

В данной организации кэша каждая ячейка основной памяти может быть помещена только в одну запись кэша. Следовательно, кэш с прямым отображением также можно назвать "однопутевой ассоциативной кэш-памятью". Он не имеет политики размещения как таковой, поскольку отсутствует выбор, содержимое какой записи кэша вытеснить. Это означает, что если две ячейки памяти отображаются в одну и ту же запись, они могут постоянно вытеснять друг друга. Хотя кэш с прямым отображением проще, для достижения сопоставимой производительности он должен быть значительно больше, чем ассоциативный кэш, и его работа менее предсказуема. Пусть x – номер блока в кэше, y – номер блока в памяти, а n – количество блоков в кэше, тогда отображение выполняется с помощью уравнения .

Ассоциативный кэш с двусторонним набором

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

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

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

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

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

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

Истинный ассоциативный кэш тестирует все возможные способы одновременно, используя нечто вроде памяти с адресным доступом по содержимому. Псевдоассоциативный кэш проверяет каждый возможный способ последовательно, один за другим. Кэш с повторным вычислением хэша и столбцово-ассоциативный кэш являются примерами псевдоассоциативного кэша. В типичном случае, когда совпадение найдено при проверке первого способа, псевдоассоциативный кэш работает так же быстро, как и кэш с прямым отображением, но имеет значительно более низкий уровень промахов из-за конфликтов, чем кэш с прямым отображением, приближаясь к уровню промахов полностью ассоциативного кэша. При этом используется индекс множества для отображения в набор кэша, как в обычном ассоциативном кэше множества, а добавленные биты тега используются для выбора способа в этом наборе. Например, в 4-х способовом ассоциативном кэше два бита используются для выбора способа 00, способа 01, способа 10 и способа 11 соответственно. Эта двойная индексация кэша называется "основным отображением местоположения", и её задержка эквивалентна доступу к кэшу с прямым отображением. Широкие исследования в области многоколоночного проектирования кэшей, такие как предсказание способов в кэш-памяти Intel, реконфигурируемая многопутевая ассоциативная кэш-память IBM и динамический выбор замены кэша Oracle на основе битов тега адреса, подтверждают эффективность данного подхода.

Пример

Оригинальный процессор 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 бит для поля тега. Первая машина для вызова страниц, Ferranti Atlas, не работала по стандартным протоколам когерентности. Другая проблема – это омонимы, когда один и тот же виртуальный адрес отображается на несколько различных физических адресов. Невозможно различить эти отображения, просто взглянув на сам виртуальный индекс, хотя возможные решения включают: очистку кэша после переключения контекста, принуждение к тому, чтобы адресные пространства не перекрывались, маркировку виртуального адреса идентификатором адресного пространства (ASID). Кроме того, существует проблема, что виртуальные – физические отображения могут измениться, что потребует очистки кэш-линий, поскольку виртуальные адреса (VA) больше не будут действительными. Все эти проблемы отсутствуют, если теги используют физические адреса (VIPT). Кэши с виртуальной индексацией и физическими тегами (VIPT) используют виртуальный адрес для индекса и физический адрес в теге. Преимущество перед PIPT заключается в более низкой задержке, поскольку кэш-линия может быть проверена параллельно с переводом TLB, однако тег не может быть сравнен до тех пор, пока физический адрес не будет доступен. Преимущество над VIVT заключается в том, что, поскольку тег имеет физический адрес, кэш может обнаруживать омонимы. Теоретически, VIPT требует больше битов тега, потому что некоторые биты индекса могут отличаться между виртуальными и физическими адресами (например, бит 12 и выше для страниц 4 КБ) и должны быть включены как в виртуальный индекс, так и в физический тег. На практике это не является проблемой, потому что, чтобы избежать проблем с когерентностью, VIPT-кэши проектируются таким образом, чтобы не иметь таких битов индекса (например, путем ограничения общего количества битов для индекса и смещения блока до 12 для страниц 4 КБ); это ограничивает размер VIPT-кэшей размером страницы, умноженным на ассоциативность кэша. В литературе часто утверждается, что физически индексированные, виртуально помеченные (PIVT) кэши бесполезны и не существуют. Однако MIPS R6000 использует этот тип кэша в качестве единственной известной реализации. R6000 реализован в логике с эмиттерной связью (emitter coupled logic), которая является чрезвычайно быстрой технологией, не подходящей для больших памятей, таких как TLB. R6000 решает проблему, поместив память TLB в зарезервированную часть кэша второго уровня, имея крошечный, высокоскоростной "срез" TLB на чипе. Кэш индексируется по физическому адресу, полученному из среза TLB. Однако, поскольку срез TLB переводит только те биты виртуального адреса, которые необходимы для индексации кэша, и не использует никаких тегов, могут возникнуть ложные попадания кэша, что решается путем маркировки с использованием виртуального адреса. Скорость этого обращения (латентность загрузки) имеет решающее значение для производительности ЦП, и поэтому большинство современных кэшей уровня 1 фактически используют виртуальную индексацию, что, по крайней мере, позволяет поиску TLB MMU проводиться параллельно с извлечением данных из кэша RAM. Но виртуальная индексация не является лучшим выбором для всех уровней кэша. Стоимость обработки виртуальных алиасов растет с размером кэша, и в результате большинство кэшей уровня 2 и более крупных физически индексируются. Кэши исторически использовали как виртуальные, так и физические адреса для кэш-тегов, хотя виртуальная маркировка сейчас не распространена. Если поиск TLB может завершиться до поиска кэша RAM, то физический адрес доступен вовремя для сравнения тегов, и нет необходимости в виртуальной маркировке. Большие кэши, как правило, физически маркируются, и только небольшие, с очень низкой задержкой кэши виртуально маркируются. В недавних процессорах общего назначения виртуальная маркировка была заменена vhints, как описано ниже.

The original Pentium 4 processor had a four way set associative L1 data cache of 8 KiB in size, with 64 byte cache blocks. Hence, there are 8 KiB / 64 = 128 cache blocks. The number of sets is equal to the number of cache blocks divided by the number of ways of associativity, what leads to 128 / 4 = 32 sets, and hence 25 = 32 different indices. There are 26 = 64 possible offsets. Since the CPU address is 32 bits wide, this implies 32 5 6 = 21 bits for the tag field. The original Pentium 4 processor also had an eight way set associative L2 integrated cache 256 KiB in size, with 128 byte cache blocks. This implies 32 8 7 = 17 bits for the tag field. refn|The very first paging machine, the Ferranti Atlas they do not work for standard coherence protocols. Another problem is homonyms, where the same virtual address maps to several different physical addresses. It is not possible to distinguish these mappings merely by looking at the virtual index itself, though potential solutions include: flushing the cache after a context switch, forcing address spaces to be non overlapping, tagging the virtual address with an address space ID (ASID). Additionally, there is a problem that virtual to physical mappings can change, which would require flushing cache lines, as the VAs would no longer be valid. All these issues are absent if tags use physical addresses (VIPT). Virtually indexed, physically tagged (VIPT) caches use the virtual address for the index and the physical address in the tag. The advantage over PIPT is lower latency, as the cache line can be looked up in parallel with the TLB translation, however the tag cannot be compared until the physical address is available. The advantage over VIVT is that since the tag has the physical address, the cache can detect homonyms. Theoretically, VIPT requires more tags bits because some of the index bits could differ between the virtual and physical addresses (for example bit 12 and above for 4 KiB pages) and would have to be included both in the virtual index and in the physical tag. In practice this is not an issue because, in order to avoid coherency problems, VIPT caches are designed to have no such index bits (e. g., by limiting the total number of bits for the index and the block offset to 12 for 4 KiB pages); this limits the size of VIPT caches to the page size times the associativity of the cache. Physically indexed, virtually tagged (PIVT) caches are often claimed in literature to be useless and non existing. However, the MIPS R6000 uses this cache type as the sole known implementation. The R6000 is implemented in emitter coupled logic, which is an extremely fast technology not suitable for large memories such as a TLB. The R6000 solves the issue by putting the TLB memory into a reserved part of the second level cache having a tiny, high speed TLB "slice" on chip. The cache is indexed by the physical address obtained from the TLB slice. However, since the TLB slice only translates those virtual address bits that are necessary to index the cache and does not use any tags, false cache hits may occur, which is solved by tagging with the virtual address. The speed of this recurrence (the load latency) is crucial to CPU performance, and so most modern level 1 caches are virtually indexed, which at least allows the MMU's TLB lookup to proceed in parallel with fetching the data from the cache RAM. But virtual indexing is not the best choice for all cache levels. The cost of dealing with virtual aliases grows with cache size, and as a result most level 2 and larger caches are physically indexed. Caches have historically used both virtual and physical addresses for the cache tags, although virtual tagging is now uncommon. If the TLB lookup can finish before the cache RAM lookup, then the physical address is available in time for tag compare, and there is no need for virtual tagging. Large caches, then, tend to be physically tagged, and only small, very low latency caches are virtually tagged. In recent general purpose CPUs, virtual tagging has been superseded by vhints, as described below.

Проблемы одноименных и синонимных слов

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

Виртуальные теги и винты

Большим преимуществом виртуальных тегов является то, что для ассоциативных кэшей они позволяют выполнять сопоставление тегов до завершения преобразования виртуального адреса в физический. Однако, запросы на когерентность и вытеснения оперируют физическим адресом. Аппаратному обеспечению необходимы средства преобразования физических адресов в индекс кэша, как правило, путем хранения как физических, так и виртуальных тегов. Для сравнения, кэш с физическими тегами не нуждается в хранении виртуальных тегов, что упрощает его реализацию. Когда виртуальное отображение удаляется из TLB, записи кэша, соответствующие этим виртуальным адресам, должны быть каким-либо образом сброшены. Альтернативно, если разрешено хранение записей кэша на страницах, не отображенных в TLB, то эти записи должны быть сброшены при изменении прав доступа к этим страницам в таблице страниц. Операционная система также может гарантировать, что в кэше одновременно не будет находиться несколько виртуальных алиасов. Операционная система обеспечивает это, применяя раскраску страниц, которая описана ниже. Некоторые ранние RISC-процессоры (SPARC, RS/6000) использовали этот подход. В последнее время он не применяется, поскольку стоимость аппаратной реализации обнаружения и вытеснения виртуальных алиасов снизилась, а сложность программного обеспечения и снижение производительности при идеальной раскраске страниц возросли. Важно различать две функции тегов в ассоциативном кэше: они используются для определения, какой блок набора выбрать, и для определения, произошло попадание в кэш или промах. Вторая функция должна быть всегда корректной, но первая может делать предположения и иногда ошибаться. Некоторые процессоры (например, ранние SPARC) имеют кэши с виртуальными и физическими тегами. Виртуальные теги используются для выбора блока, а физические теги – для определения попадания или промаха. Такой кэш сочетает в себе преимущества в плане задержки, свойственные кэшам с виртуальными тегами, и простоту программного интерфейса кэшей с физическими тегами. Однако, это требует дополнительных затрат на дублирование тегов. Кроме того, при обработке промаха необходимо проверять альтернативные блоки линии кэша на наличие виртуальных алиасов и вытеснять любые найденные совпадения. Дополнительная площадь (и некоторая задержка) могут быть уменьшены за счет хранения виртуальных подсказок с каждой записью кэша вместо виртуальных тегов. Эти подсказки являются подмножеством или хешем виртуального тега и используются для выбора блока кэша, из которого извлекаются данные, и физического тега. Как и в случае с кэшем с виртуальными тегами, может возникнуть совпадение по виртуальной подсказке, но несовпадение по физическому тегу, в этом случае запись кэша с соответствующей подсказкой должна быть вытеснена, чтобы последующие обращения к кэшу по этому адресу имели только одно совпадение по подсказке. Поскольку виртуальные подсказки имеют меньше битов, чем виртуальные теги, отличающие их друг от друга, кэш с виртуальными подсказками подвержен большему количеству конфликтов промахов, чем кэш с виртуальными тегами. Возможно, максимальное сокращение виртуальных подсказок можно найти в процессорах Pentium 4 (ядра Willamette и Northwood). В этих процессорах виртуальная подсказка фактически состоит из двух битов, а кэш является четырехпутевым ассоциативным. Фактически, аппаратное обеспечение поддерживает простую перестановку от виртуального адреса к индексу кэша, поэтому не требуется энергонезависимая память (CAM) для выбора правильного из четырех блоков.

The great advantage of virtual tags is that, for associative caches, they allow the tag match to proceed before the virtual to physical translation is done. However, coherence probes and evictions present a physical address for action. The hardware must have some means of converting the physical addresses into a cache index, generally by storing physical tags as well as virtual tags. For comparison, a physically tagged cache does not need to keep virtual tags, which is simpler. When a virtual to physical mapping is deleted from the TLB, cache entries with those virtual addresses will have to be flushed somehow. Alternatively, if cache entries are allowed on pages not mapped by the TLB, then those entries will have to be flushed when the access rights on those pages are changed in the page table. It is also possible for the operating system to ensure that no virtual aliases are simultaneously resident in the cache. The operating system makes this guarantee by enforcing page coloring, which is described below. Some early RISC processors (SPARC, RS/6000) took this approach. It has not been used recently, as the hardware cost of detecting and evicting virtual aliases has fallen and the software complexity and performance penalty of perfect page coloring has risen. It can be useful to distinguish the two functions of tags in an associative cache: they are used to determine which way of the entry set to select, and they are used to determine if the cache hit or missed. The second function must always be correct, but it is permissible for the first function to guess, and get the wrong answer occasionally. Some processors (e. g. early SPARCs) have caches with both virtual and physical tags. The virtual tags are used for way selection, and the physical tags are used for determining hit or miss. This kind of cache enjoys the latency advantage of a virtually tagged cache, and the simple software interface of a physically tagged cache. It bears the added cost of duplicated tags, however. Also, during miss processing, the alternate ways of the cache line indexed have to be probed for virtual aliases and any matches evicted. The extra area (and some latency) can be mitigated by keeping virtual hints with each cache entry instead of virtual tags. These hints are a subset or hash of the virtual tag, and are used for selecting the way of the cache from which to get data and a physical tag. Like a virtually tagged cache, there may be a virtual hint match but physical tag mismatch, in which case the cache entry with the matching hint must be evicted so that cache accesses after the cache fill at this address will have just one hint match. Since virtual hints have fewer bits than virtual tags distinguishing them from one another, a virtually hinted cache suffers more conflict misses than a virtually tagged cache. Perhaps the ultimate reduction of virtual hints can be found in the Pentium 4 (Willamette and Northwood cores). In these processors the virtual hint is effectively two bits, and the cache is four way set associative. Effectively, the hardware maintains a simple permutation from virtual address to cache index, so that no content addressable memory (CAM) is necessary to select the right one of the four ways fetched.

Цвет страницы

Большие физически индексированные кэши (обычно вторичные кэши) сталкиваются с проблемой: операционная система, а не приложение, контролирует, какие страницы конфликтуют друг с другом в кэше. Различия в выделении страниц от одного запуска программы к другому приводят к различиям в шаблонах коллизий в кэше, что может привести к очень большим различиям в производительности программы. Эти различия могут сильно затруднить получение согласованного и воспроизводимого времени выполнения для эталонного теста. Чтобы понять проблему, рассмотрим процессор с 1 МиБ физически индексированным кэшем второго уровня и страницами виртуальной памяти размером 4 КиБ. Последовательные физические страницы отображаются в последовательные ячейки в кэше, пока после 256 страниц шаблон не повторится. Мы можем присвоить каждой физической странице «цвет» от 0 до 255, чтобы указать, куда в кэше она может быть помещена. Ячейки в физических страницах с разными цветами не могут конфликтовать в кэше. Программисты, стремящиеся максимально эффективно использовать кэш, могут организовать шаблоны доступа своих программ таким образом, чтобы в любой момент времени требовалось кэшировать только 1 МиБ данных, тем самым избегая промахов по емкости. Но они также должны обеспечить, чтобы шаблоны доступа не приводили к коллизионным промахам. Один из способов решения этой проблемы — разделить виртуальные страницы, используемые программой, и назначить им виртуальные цвета так же, как физические цвета были назначены физическим страницам ранее. Затем программисты могут организовать шаблоны доступа своего кода таким образом, чтобы одновременно не использовались две страницы с одним и тем же виртуальным цветом. Существует обширная литература, посвященная таким оптимизациям (например, оптимизации вложенных циклов), в основном из сообщества высокопроизводительных вычислений (HPC). Проблема в том, что, хотя все страницы, используемые в любой момент времени, могут иметь разные виртуальные цвета, некоторые могут иметь одинаковые физические цвета. Фактически, если операционная система случайным образом и равномерно назначает физические страницы виртуальным страницам, весьма вероятно, что некоторые страницы будут иметь один и тот же физический цвет, и тогда ячейки из этих страниц будут конфликтовать в кэше (это парадокс дней рождения). Решение состоит в том, чтобы операционная система пыталась назначить различные физические цвета различным виртуальным цветам — метод, называемый раскраской страниц. Хотя фактическое соответствие между виртуальным и физическим цветами не влияет на производительность системы, сложные соответствия трудно отслеживать и дают мало преимуществ, поэтому большинство подходов к раскраске страниц просто пытаются сохранить физические и виртуальные цвета страниц одинаковыми. Если операционная система может гарантировать, что каждая физическая страница отображается только в один виртуальный цвет, то виртуальных алиасов не будет, и процессор сможет использовать виртуально индексированные кэши без необходимости дополнительных проверок на виртуальные алиасы при обработке промахов. В качестве альтернативы, ОС может вытеснять страницу из кэша всякий раз, когда она меняет один виртуальный цвет на другой. Как упоминалось выше, этот подход использовался в некоторых ранних конструкциях SPARC и RS/6000. Метод раскраски страниц программного обеспечения был использован для эффективного разделения общего кэша последнего уровня (LLC) в многоядерных процессорах. Этот метод управления LLC на основе операционной системы был принят Intel.

Large physically indexed caches (usually secondary caches) run into a problem: the operating system rather than the application controls which pages collide with one another in the cache. Differences in page allocation from one program run to the next lead to differences in the cache collision patterns, which can lead to very large differences in program performance. These differences can make it very difficult to get a consistent and repeatable timing for a benchmark run. To understand the problem, consider a CPU with a 1 MiB physically indexed direct mapped level 2 cache and 4 KiB virtual memory pages. Sequential physical pages map to sequential locations in the cache until after 256 pages the pattern wraps around. We can label each physical page with a color of 0–255 to denote where in the cache it can go. Locations within physical pages with different colors cannot conflict in the cache. Programmers attempting to make maximum use of the cache may arrange their programs' access patterns so that only 1 MiB of data need be cached at any given time, thus avoiding capacity misses. But they should also ensure that the access patterns do not have conflict misses. One way to think about this problem is to divide up the virtual pages the program uses and assign them virtual colors in the same way as physical colors were assigned to physical pages before. Programmers can then arrange the access patterns of their code so that no two pages with the same virtual color are in use at the same time. There is a wide literature on such optimizations (e. g. loop nest optimization), largely coming from the High Performance Computing (HPC) community. The snag is that while all the pages in use at any given moment may have different virtual colors, some may have the same physical colors. In fact, if the operating system assigns physical pages to virtual pages randomly and uniformly, it is extremely likely that some pages will have the same physical color, and then locations from those pages will collide in the cache (this is the birthday paradox). The solution is to have the operating system attempt to assign different physical color pages to different virtual colors, a technique called page coloring. Although the actual mapping from virtual to physical color is irrelevant to system performance, odd mappings are difficult to keep track of and have little benefit, so most approaches to page coloring simply try to keep physical and virtual page colors the same. If the operating system can guarantee that each physical page maps to only one virtual color, then there are no virtual aliases, and the processor can use virtually indexed caches with no need for extra virtual alias probes during miss handling. Alternatively, the OS can flush a page from the cache whenever it changes from one virtual color to another. As mentioned above, this approach was used for some early SPARC and RS/6000 designs. The software page coloring technique has been used to effectively partition the shared Last level Cache (LLC) in multicore processors. This operating system based LLC management in multicore processors has been adopted by Intel.

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

Современные процессоры имеют несколько взаимодействующих кэш-памятей, расположенных на одном кристалле. Работа конкретной кэш-памяти полностью определяется размером кэша, размером блока кэша, количеством блоков в ассоциативном наборе, политикой замещения блоков в ассоциативном наборе и политикой записи в кэш (прямая запись или запись с возвратом). В варианте Intel Crystalwell процессоров Haswell была внедрена 128 МИБ eDRAM кэш-памяти 4-го уровня, которая функционирует как кэш жертв для кэш-памяти 3-го уровня процессоров. В микроархитектуре Skylake кэш 4-го уровня больше не используется в качестве кэша жертв.

Скрытие следов

Одним из наиболее ярких примеров специализации кэша является кэш трассировки (также известный как кэш трассировки исполнения), реализованный в микропроцессорах Intel Pentium 4. Кэш трассировки – это механизм для увеличения пропускной способности выборки инструкций и снижения энергопотребления (в случае Pentium 4) за счет хранения трасс инструкций, которые уже были выбраны и декодированы. Кэш трассировки хранит инструкции либо после их декодирования, либо после завершения их выполнения. Как правило, инструкции добавляются в кэш трассировки группами, представляющими отдельные базовые блоки или динамические трассы инструкций. Кэш трассировки Pentium 4 хранит микрооперации, полученные в результате декодирования инструкций x86, обеспечивая также функциональность кэша микроопераций. Благодаря этому, при повторном обращении к инструкции, не требуется ее повторное декодирование в микрооперации. WCC – это специальный кэш, являющийся частью кэша L2 в микроархитектуре AMD Bulldozer. Записи из обоих кэшей L1D в модуле проходят через WCC, где они буферизуются и объединяются. Задача WCC заключается в уменьшении количества операций записи в кэш L2.

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

Микрооперационный кэш (μop cache, uop cache или UC) — это специализированный кэш, который хранит микрооперации декодированных инструкций, полученные непосредственно от декодеров инструкций или из кэша инструкций. Когда требуется декодировать инструкцию, микрооперационный кэш проверяется на наличие её декодированной формы, которая повторно используется при наличии в кэше; в противном случае инструкция декодируется и затем кэшируется. Одной из первых работ, описывающих микрооперационный кэш как альтернативный фронтенд для семейства процессоров Intel P6, является статья 2001 года "Micro Operation Cache: A Power Aware Frontend for Variable Instruction Length ISA". Впоследствии Intel включила микрооперационные кэши в процессоры Sandy Bridge и последующие микроархитектуры, такие как Ivy Bridge и Haswell. AMD реализовала микрооперационный кэш в своей микроархитектуре Zen. Извлечение полных предварительно декодированных инструкций устраняет необходимость многократного декодирования сложных инструкций переменной длины в более простые микрооперации фиксированной длины и упрощает процесс предсказания, извлечения, вращения и выравнивания извлечённых инструкций. Микрооперационный кэш эффективно снимает нагрузку с аппаратного обеспечения для извлечения и декодирования, тем самым снижая энергопотребление и повышая производительность фронтенда по поставке декодированных микроопераций. Микрооперационный кэш также повышает производительность за счёт более стабильной подачи декодированных микроопераций в бэкенд и устранения различных узких мест в логике извлечения и декодирования процессора.

Кэш задач целевой ветви

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

Умный кэш

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

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

Другой вопрос — фундаментальный компромисс между задержкой кэша и коэффициентом попадания. Кэши большего размера имеют более высокий коэффициент попадания, но и большую задержку. Для решения этой проблемы многие компьютеры используют несколько уровней кэша: небольшие быстрые кэши, подкрепленные более крупными и медленными. Многоуровневые кэши обычно работают следующим образом: сначала проверяется самый быстрый кэш, уровень 1 (L1); если произошел доступ (hit), процессор продолжает работу на высокой скорости. Если этот меньший кэш не содержит нужных данных (miss), проверяется следующий по скорости кэш, уровень 2 (L2), и так далее, прежде чем обращаться к внешней памяти. Поскольку разница в задержке между основной памятью и самым быстрым кэшем увеличилась, некоторые процессоры начали использовать до трех уровней кэша на кристалле. Экономичные решения использовали это для размещения всей иерархии кэша на кристалле, но к 2010 году некоторые из самых производительных решений вернулись к использованию больших внекристальных кэшей, которые часто реализуются на eDRAM и монтируются на многочиповом модуле в качестве четвертого уровня кэша. В редких случаях, например, в центральном процессоре IBM z15 (2019), все уровни, вплоть до L1, реализованы на eDRAM, полностью заменяя SRAM (для кэша SRAM по-прежнему используется для регистров). Apple M1 на базе ARM имеет 192 КБ кэша L1 для каждого из четырех высокопроизводительных ядер, что является необычно большим объемом; однако четыре высокоэффективных ядра имеют только 128 КБ. Преимущества кэшей L3 и L4 зависят от характера доступа приложения к данным. Примеры продуктов, использующих кэши L3 и L4, включают следующее: Alpha 21164 (1995) имел от 1 до 64 МБ внекристального кэша L3. AMD K6 III (1999) использовал кэш L3 на основе материнской платы. IBM POWER4 (2001) имел внекристальные кэши L3 объемом 32 МБ на процессор, совместно используемые несколькими процессорами. Itanium 2 (2003) имел 6 МБ унифицированного кэша уровня 3 (L3) на кристалле; модуль Itanium 2 (2003) MX 2 включал два процессора Itanium 2 вместе с общим 64 МБ кэшем L4 на многочиповом модуле, который был совместим с процессором Madison. Продукт Intel Xeon MP с кодовым названием "Tulsa" (2006) имеет 16 МБ кэша L3 на кристалле, совместно используемого между двумя ядрами процессора. AMD Phenom (2007) с 2 МБ кэша L3. AMD Phenom II (2008) имеет до 6 МБ унифицированного кэша L3 на кристалле. Intel Core i7 (2008) имеет 8 МБ унифицированного кэша L3 на кристалле, который является инклюзивным и совместно используется всеми ядрами. Процессоры Intel Haswell с интегрированной графикой Intel Iris Pro имеют 128 МБ eDRAM, фактически функционирующей как кэш L4. Наконец, на другом конце иерархии памяти сам файл регистров ЦП можно рассматривать как самый маленький и самый быстрый кэш в системе, с особенностью, что его планирование осуществляется программно, как правило, компилятором, поскольку он выделяет регистры для хранения значений, полученных из основной памяти, например, для оптимизации вложенных циклов. Однако, с переименованием регистров, большинство назначений регистров компилятором перераспределяются динамически аппаратным обеспечением во время выполнения в банк регистров, что позволяет процессору устранять ложные зависимости данных и, таким образом, снижать риски конвейера. Файлы регистров иногда также имеют иерархию: Cray 1 (около 1976) имел восемь адресных ("A") и восемь скалярных ("S") регистров, которые обычно были доступны. Также был набор из 64 адресных ("B") и 64 скалярных ("T") регистров, доступ к которым занимал больше времени, но был быстрее, чем доступ к основной памяти. Регистры "B" и "T" были предусмотрены, поскольку Cray 1 не имел кэша данных. (Однако Cray 1 имел кэш инструкций.)

Another issue is the fundamental tradeoff between cache latency and hit rate. Larger caches have better hit rates but longer latency. To address this tradeoff, many computers use multiple levels of cache, with small fast caches backed up by larger, slower caches. Multi level caches generally operate by checking the fastest cache, level 1 (L1), first; if it hits, the processor proceeds at high speed. If that smaller cache misses, the next fastest cache, level 2 (L2), is checked, and so on, before accessing external memory. As the latency difference between main memory and the fastest cache has become larger, some processors have begun to utilize as many as three levels of on chip cache. Price sensitive designs used this to pull the entire cache hierarchy on chip, but by the 2010s some of the highest performance designs returned to having large off chip caches, which is often implemented in eDRAM and mounted on a multi chip module, as a fourth cache level. In rare cases, such as in the mainframe CPU IBM z15 (2019), all levels down to L1 are implemented by eDRAM, replacing SRAM entirely (for cache, SRAM is still used for registers). The ARM based Apple M1 has a 192 KiB L1 cache for each of the four high performance cores, an unusually large amount; however the four high efficiency cores only have 128 KiB. The benefits of L3 and L4 caches depend on the application's access patterns. Examples of products incorporating L3 and L4 caches include the following:

Alpha 21164 (1995) had 1 to 64 MiB off chip L3 cache. AMD K6 III (1999) had motherboard based L3 cache. IBM POWER4 (2001) had off chip L3 caches of 32 MiB per processor, shared among several processors. Itanium 2 (2003) had a 6 MiB unified level 3 (L3) cache on die; the Itanium 2 (2003) MX 2 module incorporated two Itanium 2 processors along with a shared 64 MiB L4 cache on a multi chip module that was pin compatible with a Madison processor. Intel's Xeon MP product codenamed "Tulsa" (2006) features 16 MiB of on die L3 cache shared between two processor cores. AMD Phenom (2007) with 2 MiB of L3 cache. AMD Phenom II (2008) has up to 6 MiB on die unified L3 cache. Intel Core i7 (2008) has an 8 MiB on die unified L3 cache that is inclusive, shared by all cores. Intel Haswell CPUs with integrated Intel Iris Pro Graphics have 128 MiB of eDRAM acting essentially as an L4 cache. Finally, at the other end of the memory hierarchy, the CPU register file itself can be considered the smallest, fastest cache in the system, with the special characteristic that it is scheduled in software—typically by a compiler, as it allocates registers to hold values retrieved from main memory for, as an example, loop nest optimization. However, with register renaming most compiler register assignments are reallocated dynamically by hardware at runtime into a register bank, allowing the CPU to break false data dependencies and thus easing pipeline hazards. Register files sometimes also have hierarchy: The Cray 1 (circa 1976) had eight address "A" and eight scalar data "S" registers that were generally usable. There was also a set of 64 address "B" and 64 scalar data "T" registers that took longer to access, but were faster than main memory. The "B" and "T" registers were provided because the Cray 1 did not have a data cache. (The Cray 1 did, however, have an instruction cache.)

Чипы многоядерные

При рассмотрении чипа с несколькими ядрами возникает вопрос, должны ли кэши быть общими или локальными для каждого ядра. Реализация общего кэша неизбежно усложняет разводку и схему. Однако, наличие одного кэша на чип, а не на каждое ядро, значительно уменьшает требуемое пространство, что позволяет использовать кэш большего объема. Как правило, совместное использование кэша 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, что и делает инклюзивный кэш.

Память для скретчпада

Скретчпад память (SPM), также известная как скретчпад, скретчпад ОЗУ или локальная память в компьютерной терминологии, представляет собой высокоскоростную внутреннюю память, используемую для временного хранения вычислений, данных и другой информации в процессе обработки.

Пример: K8

Для иллюстрации как специализации, так и многоуровневого кэширования, приведена иерархия кэша ядра K8 в процессоре AMD Athlon 64. K8 имеет четыре специализированных кэша: кэш инструкций, кэш инструкций TLB, кэш данных TLB и кэш данных. Каждый из этих кэшей специализирован: кэш инструкций хранит копии 64-байтовых строк памяти и извлекает 16 байт за цикл. Каждый байт в этом кэше хранится в десяти битах, а не в восьми, при этом дополнительные биты обозначают границы инструкций (это пример предварительного декодирования). Кэш имеет только защиту по четности (parity), а не ECC, потому что parity занимает меньше места, и любые поврежденные данные могут быть заменены свежими данными, извлеченными из памяти (которая всегда содержит актуальную копию инструкций). Кэш инструкций 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 имеет довольно сложный механизм предсказания ветвлений, с таблицами, которые помогают предсказывать, будут ли выполнены ветвления, и другими таблицами, которые предсказывают цели ветвлений и переходов. Часть этой информации связана с инструкциями как в кэше инструкций первого уровня, так и в унифицированном вторичном кэше. K8 использует интересный прием для хранения информации о предсказаниях вместе с инструкциями во вторичном кэше. Строки во вторичном кэше защищены от случайного повреждения данных (например, от попадания альфа-частицы) либо с помощью ECC, либо с помощью parity, в зависимости от того, были ли эти строки вытеснены из первичных кэшей данных или инструкций. Поскольку код parity занимает меньше бит, чем код ECC, строки из кэша инструкций имеют несколько свободных бит. Эти биты используются для кэширования информации о предсказании ветвлений, связанной с этими инструкциями. В результате предсказатель ветвлений имеет более эффективную таблицу истории и, следовательно, более высокую точность.

To illustrate both specialization and multi level caching, here is the cache hierarchy of the K8 core in the AMD Athlon 64 CPU. The K8 has four specialized caches: an instruction cache, an instruction TLB, a data TLB, and a data cache. Each of these caches is specialized:

The instruction cache keeps copies of 64 byte lines of memory, and fetches 16 bytes each cycle. Each byte in this cache is stored in ten bits rather than eight, with the extra bits marking the boundaries of instructions (this is an example of predecoding). The cache has only parity protection rather than ECC, because parity is smaller and any damaged data can be replaced by fresh data fetched from memory (which always has an up to date copy of instructions). The instruction TLB keeps copies of page table entries (PTEs). Each cycle's instruction fetch has its virtual address translated through this TLB into a physical address. Each entry is either four or eight bytes in memory. Because the K8 has a variable page size, each of the TLBs is split into two sections, one to keep PTEs that map 4 KiB pages, and one to keep PTEs that map 4 MiB or 2 MiB pages. The split allows the fully associative match circuitry in each section to be simpler. The operating system maps different sections of the virtual address space with different size PTEs. The data TLB has two copies which keep identical entries. The two copies allow two data accesses per cycle to translate virtual addresses to physical addresses. Like the instruction TLB, this TLB is split into two kinds of entries. The data cache keeps copies of 64 byte lines of memory. It is split into 8 banks (each storing 8 KiB of data), and can fetch two 8 byte data each cycle so long as those data are in different banks. There are two copies of the tags, because each 64 byte line is spread among all eight banks. Each tag copy handles one of the two accesses per cycle. The K8 also has multiple level caches. There are second level instruction and data TLBs, which store only PTEs mapping 4 KiB. Both instruction and data caches, and the various TLBs, can fill from the large unified L2 cache. This cache is exclusive to both the L1 instruction and data caches, which means that any 8 byte line can only be in one of the L1 instruction cache, the L1 data cache, or the L2 cache. It is, however, possible for a line in the data cache to have a PTE which is also in one of the TLBs—the operating system is responsible for keeping the TLBs coherent by flushing portions of them when the page tables in memory are updated. The K8 also caches information that is never stored in memory—prediction information. These caches are not shown in the above diagram. As is usual for this class of CPU, the K8 has fairly complex
branch prediction, with tables that help predict whether branches are taken and other tables which predict the targets of branches and jumps. Some of this information is associated with instructions, in both the level 1 instruction cache and the unified secondary cache. The K8 uses an interesting trick to store prediction information with instructions in the secondary cache. Lines in the secondary cache are protected from accidental data corruption (e. g. by an alpha particle strike) by either ECC or parity, depending on whether those lines were evicted from the data or instruction primary caches. Since the parity code takes fewer bits than the ECC code, lines from the instruction cache have a few spare bits. These bits are used to cache branch prediction information associated with those instructions. The net result is that the branch predictor has a larger effective history table, and so has better accuracy.

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

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

Определительная оперативная память

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

Реализация

Читание из кэша — наиболее распространенная операция ЦП, требующая более одного цикла. Время выполнения программы обычно очень чувствительно к задержке при попадании в кэш данных первого уровня. Значительные усилия по проектированию, а также часто энергопотребление и площадь кристалла тратятся на то, чтобы сделать кэши максимально быстрыми. Самый простой кэш — это виртуально индексированный кэш с прямым отображением. Виртуальный адрес вычисляется с помощью сумматора, соответствующая часть адреса извлекается и используется для индексации SRAM, которая возвращает загруженные данные. Данные выравниваются в байтовом сдвигателе и затем передаются на следующую операцию. Внутреннем цикле нет необходимости в проверке тегов, фактически теги даже не нужно читать. Позже в конвейере, но до завершения инструкции загрузки, тег загруженных данных должен быть прочитан и проверен по виртуальному адресу, чтобы убедиться в наличии попадания в кэш. В случае промаха кэш обновляется запрошенной линией кэша, и конвейер перезапускается. Ассоциативный кэш более сложен, поскольку для определения того, какую запись кэша выбрать, необходимо прочитать некоторую форму тега. Ассоциативный кэш первого уровня с N-путевым набором обычно считывает все N возможных тегов и N данных параллельно, а затем выбирает данные, связанные с соответствующим тегом. Кэши второго уровня иногда экономят энергию, сначала считывая теги, чтобы считывать только один элемент данных из SRAM данных. Прилагаемая диаграмма призвана прояснить способ использования различных полей адреса. Бит 31 является старшим, а бит 0 — младшим. На диаграмме показаны SRAM, индексация и мультиплексирование для кэша размером 4 КБ, 2-путевого набора, виртуально индексированного и виртуально помеченного, с 64-байтными (B) линиями, 32-битной шириной чтения и 32-битным виртуальным адресом. Поскольку кэш имеет размер 4 КБ и содержит 64-байтные линии, в кэше всего 64 строки, и мы читаем по две строки одновременно из SRAM тегов, который имеет 32 строки, каждая из которых содержит пару 21-битных тегов. Хотя любая функция виртуальных битов адреса 31–6 может быть использована для индексации SRAM тегов и данных, проще всего использовать младшие биты. Аналогично, поскольку кэш составляет 4 КБ и имеет 4-байтный путь чтения и считывает два пути для каждого доступа, SRAM данных имеет размер 512 строк и ширину 8 байт. Более современный кэш может быть 16 КБ, 4-путевым ассоциативным набором, виртуально индексированным, виртуально подсказанным и физически помеченным, с 32-байтными линиями, 32-битной шириной чтения и 36-битными физическими адресами. Путь чтения для такого кэша выглядит очень похоже на описанный выше. Вместо тегов считываются vhints (виртуальные подсказки) и сопоставляются с подмножеством виртуального адреса. Позже в конвейере виртуальный адрес преобразуется в физический адрес с помощью TLB, и считывается физический тег (только один, поскольку vhint указывает, какой путь кэша читать). Наконец, физический адрес сравнивается с физическим тегом, чтобы определить, произошло ли попадание. Некоторые конструкции SPARC повысили скорость своих кэшей L1 на несколько задержек вентилей, объединив сумматор виртуальных адресов с декодерами SRAM. См. сумматор-адресованный декодер.

Cache reads are the most common CPU operation that takes more than a single cycle. Program execution time tends to be very sensitive to the latency of a level 1 data cache hit. A great deal of design effort, and often power and silicon area are expended making the caches as fast as possible. The simplest cache is a virtually indexed direct mapped cache. The virtual address is calculated with an adder, the relevant portion of the address extracted and used to index an SRAM, which returns the loaded data. The data is byte aligned in a byte shifter, and from there is bypassed to the next operation. There is no need for any tag checking in the inner loopin fact, the tags need not even be read. Later in the pipeline, but before the load instruction is retired, the tag for the loaded data must be read, and checked against the virtual address to make sure there was a cache hit. On a miss, the cache is updated with the requested cache line and the pipeline is restarted. An associative cache is more complicated, because some form of tag must be read to determine which entry of the cache to select. An N way set associative level 1 cache usually reads all N possible tags and N data in parallel, and then chooses the data associated with the matching tag. Level 2 caches sometimes save power by reading the tags first, so that only one data element is read from the data SRAM. The adjacent diagram is intended to clarify the manner in which the various fields of the address are used. Address bit 31 is most significant, bit 0 is least significant. The diagram shows the SRAMs, indexing, and multiplexing for a 4 KiB, 2 way set associative, virtually indexed and virtually tagged cache with 64 byte (B) lines, a 32 bit read width and 32 bit virtual address. Because the cache is 4 KiB and has 64 B lines, there are just 64 lines in the cache, and we read two at a time from a Tag SRAM which has 32 rows, each with a pair of 21 bit tags. Although any function of virtual address bits 31 through 6 could be used to index the tag and data SRAMs, it is simplest to use the least significant bits. Similarly, because the cache is 4 KiB and has a 4 B read path, and reads two ways for each access, the Data SRAM is 512 rows by 8 bytes wide. A more modern cache might be 16 KiB, 4 way set associative, virtually indexed, virtually hinted, and physically tagged, with 32 B lines, 32 bit read width and 36 bit physical addresses. The read path recurrence for such a cache looks very similar to the path above. Instead of tags, vhints are read, and matched against a subset of the virtual address. Later on in the pipeline, the virtual address is translated into a physical address by the TLB, and the physical tag is read (just one, as the vhint supplies which way of the cache to read). Finally the physical address is compared to the physical tag to determine if a hit has occurred. Some SPARC designs have improved the speed of their L1 caches by a few gate delays by collapsing the virtual address adder into the SRAM decoders. See sum addressed decoder.

История

Ранняя история технологии кэширования тесно связана с изобретением и использованием виртуальной памяти. Из-за дефицита и высокой стоимости полупроводниковых памяти, ранние мэйнфреймы 1960-х годов использовали сложную иерархию физической памяти, отображаемую на плоское виртуальное адресное пространство, используемое программами. Используемые технологии памяти охватывали полупроводники, магнитные сердечники, барабаны и диски. Виртуальная память, с которой работали программы, была представлена как плоская структура, а кэширование использовалось для предварительной загрузки данных и инструкций в самую быструю память перед обращением к ним со стороны процессора. Были проведены обширные исследования для оптимизации размеров кэша. Было обнаружено, что оптимальные значения сильно зависят от используемого языка программирования: Algol требовал наименьшего кэша, а Fortran и Cobol – наибольшего. На заре развития микрокомпьютерных технологий доступ к памяти был лишь незначительно медленнее доступа к регистрам. Однако, начиная с 1980-х годов, разрыв в производительности между процессором и памятью начал расти. Микропроцессоры развивались гораздо быстрее, чем память, особенно в отношении тактовой частоты, что сделало память узким местом производительности. Хотя технически было возможно сделать всю основную память такой же быстрой, как процессор, был выбран более экономически выгодный путь: использовать большой объем медленной памяти, но также добавить небольшой объем быстрой кэш-памяти для уменьшения разрыва в производительности. Это обеспечило в разы большую емкость за ту же цену, с лишь незначительным снижением общей производительности.

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

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

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

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

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

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

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

68010, выпущенный в 1982 году, имеет "режим цикла", который можно рассматривать как небольшой специализированный кэш инструкций, ускоряющий циклы, состоящие всего из двух инструкций. 68020, выпущенный в 1984 году, заменил его типичным кэшем инструкций объемом 256 байт, став первым процессором серии 68k с полноценной кэш-памятью на кристалле. 68030, выпущенный в 1987 году, по сути представляет собой ядро 68020 с добавленным кэшем данных на 256 байт, блоком управления памятью (MMU) на кристалле, уменьшенным техпроцессом и добавленным режимом пакетной передачи данных для кэшей. 68040, выпущенный в 1990 году, имеет раздельные кэши инструкций и данных объемом четыре килобайта каждый. 68060, выпущенный в 1994 году, имеет следующие характеристики: кэш данных 8 КиБ (четырехканальный ассоциативный), кэш инструкций 8 КиБ (четырехканальный ассоциативный), FIFO-буфер инструкций на 96 байт, кэш переходов на 256 записей и буфер кэша трансляции адресов MMU на 64 записи (четырехканальный ассоциативный).

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

Поскольку микропроцессоры x86 достигли тактовой частоты 20 МГц и выше в 386, небольшие объемы быстрой кэш-памяти стали использоваться в системах для повышения производительности. Это было связано с тем, что DRAM, используемая для основной памяти, имела значительную задержку, до 120 нс, а также требовала циклов обновления. Кэш строился из более дорогих, но значительно более быстрых ячеек памяти SRAM, которые в то время имели задержки около 10–25 нс. Ранние кэши были внешними по отношению к процессору и обычно располагались на материнской плате в виде восьми или девяти DIP-корпусов, устанавливаемых в разъемы для включения кэша в качестве дополнительной или опциональной функции. Некоторые версии процессора Intel 386 могли поддерживать 16–256 КиБ внешнего кэша. С процессором 486 кэш объемом 8 КиБ был интегрирован непосредственно в кристалл процессора. Этот кэш назывался кэшем уровня 1 или L1, чтобы отличить его от более медленного кэша на материнской плате, или кэша уровня 2 (L2). Кэши на материнской плате были значительно больше, наиболее распространенным размером был 256 КиБ. Некоторые системные платы содержали разъемы для дочерней карты Intel 485 Turbocache, которая имела 64 или 128 Кбайт кэш-памяти. Популярность кэша на материнской плате сохранялась в эпоху Pentium MMX, но была вытеснена появлением SDRAM и растущим разрывом между тактовыми частотами шины и процессора, из-за чего кэш на материнской плате стал лишь незначительно быстрее основной памяти. Следующий этап развития реализации кэша в микропроцессорах x86 начался с Pentium Pro, который разместил вторичный кэш в том же корпусе, что и микропроцессор, с той же частотой. Кэши на материнской плате оставались популярными благодаря процессорам AMD K6-2 и AMD K6-III, которые все еще использовали Socket 7, ранее использовавшийся Intel с кэшем на материнской плате. K6-III включал 256 КиБ кэша L2 на кристалле и использовал бортовой кэш в качестве кэша третьего уровня, названного L3 (производились материнские платы с до 2 МиБ бортового кэша). После устаревания Socket 7 кэш на материнской плате исчез из систем x86. Кэши трех уровней вновь стали использоваться с появлением многоядерных процессоров, где кэш L3 был добавлен непосредственно в кристалл процессора. Стало обычной практикой увеличение общего объема кэша в новых поколениях процессоров, и в последнее время (по состоянию на 2011 год) нередко встречаются кэши уровня 3 объемом в десятки мегабайт. Intel представила кэш 4-го уровня в корпусе процессора с микроархитектурой Haswell. Crystalwell.

As the x86 microprocessors reached clock rates of 20 MHz and above in the 386, small amounts of fast cache memory began to be featured in systems to improve performance. This was because the DRAM used for main memory had significant latency, up to 120 ns, as well as refresh cycles. The cache was constructed from more expensive, but significantly faster, SRAM memory cells, which at the time had latencies around 10–25 ns. The early caches were external to the processor and typically located on the motherboard in the form of eight or nine DIP devices placed in sockets to enable the cache as an optional extra or upgrade feature. Some versions of the Intel 386 processor could support 16 to 256 KiB of external cache. With the 486 processor, an 8 KiB cache was integrated directly into the CPU die. This cache was termed Level 1 or L1 cache to differentiate it from the slower on motherboard, or Level 2 (L2) cache. These on motherboard caches were much larger, with the most common size being 256 KiB. There were some system boards that contained sockets for the Intel 485Turbocache daughtercard which had either 64 or 128 Kbyte of cache memory. The popularity of on motherboard cache continued through the Pentium MMX era but was made obsolete by the introduction of SDRAM and the growing disparity between bus clock rates and CPU clock rates, which caused on motherboard cache to be only slightly faster than main memory. The next development in cache implementation in the x86 microprocessors began with the Pentium Pro, which brought the secondary cache onto the same package as the microprocessor, clocked at the same frequency as the microprocessor. On motherboard caches enjoyed prolonged popularity thanks to the AMD K6 2 and AMD K6 III processors that still used Socket 7, which was previously used by Intel with on motherboard caches. K6 III included 256 KiB on die L2 cache and took advantage of the on board cache as a third level cache, named L3 (motherboards with up to 2 MiB of on board cache were produced). After the Socket 7 became obsolete, on motherboard cache disappeared from the x86 systems. The three level caches were used again first with the introduction of multiple processor cores, where the L3 cache was added to the CPU die. It became common for the total cache sizes to be increasingly larger in newer processor generations, and recently (as of 2011) it is not uncommon to find Level 3 cache sizes of tens of megabytes. Intel introduced a Level 4 on package cache with the Haswell microarchitecture. Crystalwell

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

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

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