Кэш микропроцессора — кэш (сверхоперативная память), используемый микропроцессором компьютера для уменьшения среднего времени доступа к компьютерной памяти. Является одним из верхних уровней иерархии памяти. Кэш использует небольшую, очень быструю память (обычно типа SRAM), которая хранит копии часто используемых данных из основной памяти. Если большая часть запросов в память будет обрабатываться кэшем, средняя задержка обращения к памяти будет приближаться к задержкам работы кэша.
Когда процессору нужно обратиться в память для чтения или записи данных, он сначала проверяет, доступна ли их копия в кэше. В случае успеха проверки процессор производит операцию используя кэш, что быстрее использования более медленной основной памяти. Подробнее о задержках памяти см. Задержки (англ. SDRAM latency) SDRAM: tCAS, tRCD, tRP, tRAS.
Большинство современных микропроцессоров для компьютеров и серверов имеют как минимум три независимых кэша: кэш инструкций для ускорения загрузки машинного кода, кэш данных для ускорения чтения и записи данных и буфер ассоциативной трансляции (TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных. Кэш данных часто реализуется в виде многоуровневого кэша (L1, L2, L3).
Увеличение размера кэш-памяти может положительно влиять на производительность почти всех приложений, хотя в некоторых случаях эффект незначителен. Работа кэш-памяти обычно прозрачна для программиста, однако для её эффективного использования в некоторых случаях применяются специальные алгоритмические приёмы, изменяющие порядок обхода данных в ОЗУ или повышающие их локальность (например, при блочном умножении матриц).
Данный раздел описывает типичный кэш данных и некоторые виды кэшей инструкций; TLB может быть устроен сложнее, а кэш инструкций — проще. На диаграмме справа изображены основная и кэш-память. Каждая строка — группа ячеек памяти содержит данные, организованные в кэш-линии. Размер каждой кэш-линии может различаться в разных процессорах, но для большинства x86-процессоров он составляет 64 байта. Размер кэш-линии обычно больше размера данных, к которому возможен доступ из одной машинной команды (типичные размеры от 1 до 16 байт). Каждая группа данных в памяти размером в 1 кэш-линию имеет порядковый номер. Для основной памяти этот номер является адресом памяти с отброшенными младшими битами. В кэше каждой кэш-линии дополнительно ставится в соответствие тег, который является адресом продублированных в этой кэш-линии данных в основной памяти.
При доступе процессора в память сначала производится проверка, хранит ли кэш запрашиваемые из памяти данные. Для этого производится сравнение адреса запроса со значениями всех тегов кэша, в которых эти данные могут храниться. Случай совпадения с тегом какой-либо кэш-линии называется попаданием в кэш (англ. cache hit), обратный же случай называется кэш-промахом (англ. cache miss). Попадание в кэш позволяет процессору немедленно произвести чтение или запись данных в кэш-линии с совпавшим тегом. Отношение количества попаданий в кэш к общему количеству запросов к памяти называют рейтингом попаданий (англ. hit rate), оно является мерой эффективности кэша для выбранного алгоритма или программы.
В случае промаха в кэше выделяется новая запись, в тег которой записывается адрес текущего запроса, а в саму кэш-линию — данные из памяти после их прочтения либо данные для записи в память. Промахи по чтению задерживают исполнение, поскольку они требуют запроса данных в более медленной основной памяти. Промахи по записи могут не давать задержку, поскольку записываемые данные сразу могут быть сохранены в кэше, а запись их в основную память можно произвести в фоновом режиме. Работа кэшей инструкций во многом похожа на вышеприведенный алгоритм работы кэша данных, но для инструкций выполняются только запросы на чтение. Кэши инструкций и данных могут быть разделены для увеличения производительности (принцип, используемый в Гарвардской архитектуре) или объединены для упрощения аппаратной реализации.
Для добавления данных в кэш после кэш-промаха может потребоваться вытеснение (англ. evict) ранее записанных данных. Для выбора замещаемой строки кэша используется эвристика, называемая политика замещения (англ. replacement policy). Основной проблемой алгоритма является предсказание, какая строка вероятнее всего не потребуется для последующих операций. Качественные предсказания сложны, и аппаратные кэши используют простые правила, такие, как LRU. Пометка некоторых областей памяти как некэшируемых (англ. non cacheable) улучшает производительность за счёт запрета кэширования редко используемых данных. Промахи для такой памяти не создают копию данных в кэше.
При записи данных в кэш должен существовать определенный момент времени, когда они будут записаны в основную память. Это время контролируется политикой записи (англ. write policy). Для кэшей со сквозной записью (англ. write-through) любая запись в кэш приводит к немедленной записи в память. Другой тип кэшей, обратная запись англ. write-back (иногда также называемый copy-back), откладывает запись на более позднее время. В таких кэшах отслеживается состояние кэш-линеек ещё не сброшенных в память (пометка битом «грязный» англ. dirty). Запись в память производится при вытеснении подобной строки из кэша. Таким образом, промах в кэше, использующем политику обратной записи, может потребовать двух операций доступа в память, один для сброса состояния старой строки и другой — для чтения новых данных.
Существуют также смешанные политики. Кэш может быть со сквозной записью (англ. write-through), но для уменьшения количества транзакций на шине записи могут временно помещаться в очередь и объединяться друг с другом.
Данные в основной памяти могут изменяться не только процессором, но и периферией, использующей прямой доступ к памяти, или другими процессорами в многопроцессорной системе. Изменение данных приводит к устареванию их копии в кэше (состояние stale). В другой реализации, когда один процессор изменяет данные в кэше, копии этих данных в кэшах других процессоров будут помечены как stale. Для поддержания содержимого нескольких кэшей в актуальном состоянии используется специальный протокол кэш когерентности.
Типичная структура записи в кэшеБлок данных тег бит актуальности
Блок данных (кэш-линия) содержит непосредственную копию данных из основной памяти. Бит актуальности означает, что данная запись содержит актуальную (самую свежую) копию.
Структура адресатег индекс смещение
Адрес памяти разделяется (от старших бит к младшим) на Тег, индекс и смещение. Длина поля индекса равна бит и соответствует ряду (строке) кэша, используемой для записи. Длина смещения равна .
Ассоциативность является компромиссом. Проверка большего числа записей требует больше энергии, площади чипа, и, потенциально, времени. Если бы существовало 10 мест, в которые алгоритм вытеснения мог бы отобразить место в памяти, тогда проверка наличия этого места в кэше потребовала бы просмотра 10 записей в кэше. С другой стороны, кэши с высокой ассоциативностью подвержены меньшему количеству промахов (см. ниже "конфликтующие промахи") и процессор тратит меньше времени на чтения из медленной основной памяти. Существует эмпирическое наблюдение, что удвоение ассоциативности (от прямого отображения к 2-канальной или от 2- к 4-канальной) имеет примерно такое же влияние на интенсивность попаданий (hit rate), что и удвоение размера кэша. Увеличение ассоциативности свыше 4 каналов приносит меньший эффект для уменьшения количества промахов (miss rate) и обычно производится по другим причинам, например, из-за пересечения виртуальных адресов.
В порядке ухудшения (увеличения длительности проверки на попадание) и улучшения (уменьшения количества промахов): кэш прямого отображения (англ. direct mapped cache) — наилучшее время попадания и, соответственно, лучший вариант для больших кэшей; 2-канальный множественно-ассоциативный кэш англ. 2-way set associative cache; 2-канальный skewed ассоциативный кэш (англ. «the best tradeoff for …. caches whose sizes are in the range 4K-8K bytes» — André Seznec); 4-канальный множественно-ассоциативный кэш (англ. 4-way set associative cache); полностью ассоциативный кэш, англ. fully associative cache — наилучший (самый низкий) процент промахов (miss rate) и лучший вариант при чрезвычайно высоких затратах при промахе (miss penalty).
Промах по чтению из кэша инструкций. Обычно дает очень большую задержку, поскольку процессор не может продолжать исполнение программы (по крайней мере, текущего потока исполнения) и вынужден простаивать в ожидании загрузки инструкции из памяти.
Промах по чтению из кэша данных. Обычно дает меньшую задержку, поскольку инструкции, не зависящие от запрошенных данных, могут продолжать исполняться, пока запрос обрабатывается в основной памяти. После получения данных из памяти можно продолжать исполнение зависимых инструкций.
Промах по записи в кэш данных. Обычно дает наименьшую задержку, поскольку запись может быть поставлена в очередь и последующие инструкции практически не ограничены в своих возможностях. Процессор может продолжать свою работу, кроме случаев промаха по записи с полностью заполненной очередью.
Compulsory misses — промахи, вызванные первым упоминанием запрошенного адреса. Размеры кэшей и их ассоциативность не влияют на количество данных промахов. Предвыборка (prefetching), как программная, так и аппаратная, может помочь, так же, как и увеличение размера кэш-линии (в качестве вида аппаратной предвыборки). Такие промахи иногда называются "холодными". Capacity misses — промахи, вызванные исключительно конечным размером кэша, происходящие вне зависимости от степени ассоциативности или размера кэш-линии. График таких промахов относительно размера кэша может дать некоторую меру временной локальности (temporal locality) некоторого набора запросов в память. Стоит заметить, что не существует понятия полного кэша, пустого кэша или почти полного кэша, так как кэши процессора почти все время имеют кэш-линии в занятом состоянии, и, значит, практически каждое заведение новой линии потребует гашения уже занятой. Conflict misses — промахи, вызванные конфликтом. Их можно избежать, если бы кэш не вытеснил запись ранее. Можно дополнительно разделить на промахи, вызванные отображением (конкретным значением ассоциативности) и промахи замещения, которые вызваны конкретным алгоритмом выбора записей для замещения.
Большая часть процессоров общего назначения реализует какой-либо вариант виртуальной памяти. Кратко говоря, каждая программа, исполняющаяся на машине, видит собственное упрощенное адресное пространство, содержащее код и данные только этой программы. Любая программа использует свое виртуальное адресное пространство вне зависимости от его местоположения в физической памяти.
Наличие виртуальной памяти требует от процессора проведения трансляции виртуальных (математических) адресов, используемых программой, в физические адреса, соответствующие реальному местоположению в ОЗУ. Часть процессора, проводящая это преобразование, называется устройство управления памятью (MMU). Для ускорения трансляций в MMU добавлен кэш недавно использованных отображений (соответствий виртуальных и физических адресов), называемый Translation Lookaside Buffer (TLB).
Для дальнейшего описания важны три особенности процесса трансляции адресов: Задержка: Физический адрес будет получен от MMU только спустя некоторое время, вплоть до нескольких тактов, после подачи на вход MMU виртуального адреса с генератора адресов. Эффект наложения: Несколько виртуальных адресов могут соответствовать одному физическому. В большинстве процессоров гарантируется, что все записи по физическому адресу будут совершены в порядке, заданном программой. Для выполнения этого свойства требуется проверка, что только один экземпляр копии данных с физического адреса находится в данный момент в кэше. Единица отображения: Виртуальное адресное пространство разбито на страницы — блоки памяти фиксированного размера, начинающиеся с адресов, кратных их размеру. Например, 4 ГБ адресного пространства можно разделить на 1048576 страниц по 4 КБ, для каждой из которых возможно независимое соответствие физическим страницам. В современных процессорах часто поддерживается использование одновременно нескольких размеров страниц, например, 4 КБ и 2 МБ для x86-64, а в некоторых современных AMD-процессорах ещё и 1 ГБ.
Важно также заметить, что первые системы виртуальной памяти были очень медленными, потому что они требовали проверки таблицы страниц (хранимой в основной ОЗУ) перед любым программным обращением в память. Без использования кэширования для отображений такие системы уменьшают скорость работы с памятью примерно в 2 раза. Поэтому использование TLB очень важно и иногда его добавление в процессоры предшествовало появлению обычных кэшей данных и инструкций.
По отношению к виртуальной адресации кэши данных и инструкций могут быть поделены на 4 типа. Адреса в кэшах используются для двух разных целей: индексирования и тегирования. Physically indexed, physically tagged (PIPT) — физически индексируемые и физически тегируемые. Такие кэши просты и избегают проблем с наложением (aliasing), но они медленны, так как перед обращением в кэш требуется запрос физического адреса в TLB. Этот запрос может вызвать промах в TLB и дополнительное обращение в основную память перед тем, как наличие данных будет проверено в кэше. Virtually indexed, virtually tagged (VIVT) — виртуально индексируемые и виртуально тегируемые. И для тегирования, и для индекса используется виртуальный адрес. Благодаря этому проверки наличия данных в кэше происходят быстрее, не требуя обращения к MMU. Однако возникает проблема наложения, когда несколько виртуальных адресов соответствуют одному и тому же физическому. В этом случае данные будут закэшированы дважды, что сильно усложняет поддержку когерентности. Другой проблемой являются омонимы, ситуации, когда один и тот же виртуальный адрес (например, в разных процессах) отображается различные физические адреса. Становится невозможным различить такие отображения исключительно по виртуальному индексу. Возможные решения: сброс кэша при переключении между задачами (context switch), требование непересечения адресных пространств процессов, тегирование виртуальных адресов идентификатором адресного пространства (address space ID, ASID) или использование физических тегов. Также возникает проблема при изменении отображения виртуальных адресов в физические, что требует сброса кэш-линий, для которых изменилось отображение. Virtually indexed, physically tagged (VIPT) — виртуально индексируемые и физически тегируемые. Для индекса используется виртуальный адрес, а для тега — физический. Преимуществом над первым типом является меньшая задержка, поскольку можно искать кэш-линию одновременно с трансляцией адресов в TLB, однако сравнение тега задерживается до получения физического адреса. Преимуществом над вторым типом является обнаружение омонимов (homonyms), так как тег содержит физический адрес. Для данного типа требуется больше бит для тега, поскольку индексные биты используют иной тип адресации. Physically indexed, virtually tagged — физически индексируемые и виртуально тегированные кэши считаются бесполезными и маргинальными и представляют исключительно академический интерес[5].
Скорость этих действий (задержка загрузки из памяти) критически важна для производительности процессоров, и поэтому большинство современных L1-кэшей являются виртуально индексируемыми, что как минимум позволяет блоку MMU производить запрос в TLB одновременно с запросом данных их кэш-памяти.
Но виртуальная индексация не является лучшим выбором для других уровней кэша. Стоимость обнаружения пересечения виртуальных адресов (aliasing) растет с увеличением размера кэша и, в результате, большинство реализаций L2 и более дальних от процессора уровней кэша используют индексирование по физическим адресам
Достаточно длительное время кэши использовали для тегов как физические, так и виртуальные адреса, хотя виртуальное тегирование в настоящее время встречается очень редко. Если TLB-запрос заканчивается раньше запроса в кэш-память, физический адрес будет доступен для сравнения с тегом к моменту, когда это будет необходимо, и, следовательно, виртуальное тегирование не потребуется. Большие кэши чаще тегируются физическими адресами, и только небольшие быстродействующие кэши используют для тегов виртуальные адреса. В современных процессорах общего назначения, виртуальное тегирование заменено на механизм vhints, описанный далее.
Суперскалярные ЦПУ осуществляют доступ к памяти из нескольких этапов конвейера: чтение инструкции (instruction fetch), трансляция виртуальных адресов в физические, чтение данных (data fetch). Очевидным решением является использование различных физических кэшей для каждого из этих случаев, чтобы не было борьбы за доступ к одному из физических ресурсов с разных стадий конвейера. Таким образом, наличие конвейера обычно приводит к наличию, по крайней мере, трёх раздельных кэшей: кэш инструкций, кэш трансляций TLB и кэш данных, каждый из которых специализирован на своей задаче.
Конвейерные процессоры, использующие раздельные кэши для данных и для инструкций (такие процессоры сейчас повсеместны), называются процессорами с Гарвардской архитектурой. Изначально данный термин применялся для компьютеров, у которых инструкции и данные разделены полностью и хранятся в различных устройствах памяти. Однако такое полное разделение не оказалось популярным, и большинство современных компьютеров имеют одно устройство основной памяти, поэтому могут считаться машинами с архитектурой фон Неймана.
Одной из проблем является фундаментальная проблема баланса между задержками кэша и интенсивностью попаданий. Большие кэши имеют более высокий процент попаданий но, вместе с тем, и большую задержку. Чтобы ослабить противоречие между этими двумя параметрами, большинство компьютеров использует несколько уровней кэша, когда после маленьких и быстрых кэшей находятся более медленные большие кэши (в настоящий момент — суммарно до 3 уровней в иерархии кэшей).
В единичных случаях реализуют 4 уровня кеш-памяти[6][7].
Многоуровневые кэши обычно работают в последовательности от меньших кэшей к большим. Сначала происходит проверка наименьшего и наибыстрейшего кэша первого уровня (L1), в случае попадания процессор продолжает работу на высокой скорости. Если меньший кэш дал промах, проверяется следующий, чуть больший и более медленный кэш второго уровня (L2), и так далее, пока не будет запроса к основному ОЗУ.
По мере того, как разница задержек между ОЗУ и быстрейшим кэшем увеличивается, в некоторых процессорах увеличивают количество уровней кэша (в некоторых — до 3х уровней на кристалле). К примеру, процессор Alpha 21164 в 1995 году имел накристалльный кэш 3го уровня в 96 КБ; IBM POWER4 в 2001 году имел до четырёх кэшей L3 по 32 МБ на отдельных кристаллах, используемых совместно несколькими ядрами; Itanium 2 в 2003 году имел 6 МБ кэш L3 на кристалле; Xeon MP под кодом «Tulsa» в 2006 году — 16 МБ кэша L3 на кристалле, общий на 2 ядра; Phenom II в 2008 году — до 6 МБ универсального L3 кэша; Intel Core i7 в 2008 году — 8 МБ накристалльного кэша L3, являющимся инклюзивным и разделяемым между всеми ядрами. Польза от кэша L3 зависит от характера обращений программы в память.
Наконец, с другой стороны иерархии памяти находится регистровый файл самого микропроцессора, который можно рассматривать как небольшой и самый быстрый кэш в системе со специальными свойствами (например, статическое планирование компилятором при распределении регистров, когда он располагает данные из ОЗУ на регистр). Подробнее см. loop nest optimization. Регистровые файлы также могут иметь иерархию: Cray-1 (в 1976 году) имел 8 адресных «A»-регистров и 8 скалярных «S»-регистров общего назначения. Также машина содержала набор из 64 адресных «B» и 64 скалярных «T» регистров, обращение к которым было дольше, но все же значительно быстрее основной ОЗУ. Эти регистры были введены по причине отсутствия в машине кэша данных (хотя кэш команд в машине имелся)
Одной из проблем является фундаментальная проблема баланса между задержками кэша и интенсивностью попаданий. Большие кэши имеют более высокий процент попаданий но, вместе с тем, и большую задержку. Чтобы ослабить противоречие между этими двумя параметрами, большинство компьютеров использует несколько уровней кэша, когда после маленьких и быстрых кэшей находятся более медленные большие кэши (в настоящий момент — суммарно до 3 уровней в иерархии кэшей).
В единичных случаях реализуют 4 уровня кеш-памяти[6][7].
Многоуровневые кэши обычно работают в последовательности от меньших кэшей к большим. Сначала происходит проверка наименьшего и наибыстрейшего кэша первого уровня (L1), в случае попадания процессор продолжает работу на высокой скорости. Если меньший кэш дал промах, проверяется следующий, чуть больший и более медленный кэш второго уровня (L2), и так далее, пока не будет запроса к основному ОЗУ.
По мере того, как разница задержек между ОЗУ и быстрейшим кэшем увеличивается, в некоторых процессорах увеличивают количество уровней кэша (в некоторых — до 3х уровней на кристалле). К примеру, процессор Alpha 21164 в 1995 году имел накристалльный кэш 3го уровня в 96 КБ; IBM POWER4 в 2001 году имел до четырёх кэшей L3 по 32 МБ[8] на отдельных кристаллах, используемых совместно несколькими ядрами; Itanium 2 в 2003 году имел 6 МБ кэш L3 на кристалле; Xeon MP под кодом «Tulsa» в 2006 году — 16 МБ кэша L3 на кристалле, общий на 2 ядра; Phenom II в 2008 году — до 6 МБ универсального L3 кэша; Intel Core i7 в 2008 году — 8 МБ накристалльного кэша L3, являющимся инклюзивным и разделяемым между всеми ядрами. Польза от кэша L3 зависит от характера обращений программы в память.
Наконец, с другой стороны иерархии памяти находится регистровый файл самого микропроцессора, который можно рассматривать как небольшой и самый быстрый кэш в системе со специальными свойствами (например, статическое планирование компилятором при распределении регистров, когда он располагает данные из ОЗУ на регистр). Подробнее см. loop nest optimization. Регистровые файлы также могут иметь иерархию: Cray-1 (в 1976 году) имел 8 адресных «A»-регистров и 8 скалярных «S»-регистров общего назначения. Также машина содержала набор из 64 адресных «B» и 64 скалярных «T» регистров, обращение к которым было дольше, но все же значительно быстрее основной ОЗУ. Эти регистры были введены по причине отсутствия в машине кэша данных (хотя кэш команд в машине имелся)
Victim cache или Victim buffer) (дословно Кэш жертв) — это небольшой специализированный кэш, хранящий те кэш-линии, которые были недавно вытеснены из основного кэша микропроцессора при их замещении. Данный кэш располагается между основным кэшем и его англ. refill path. Обычно кэш жертв является полностью ассоциативным и служит для уменьшения количества конфликтных промахов (conflict miss). Многие часто используемые программы не требуют полного ассоциативного отображения для всех попыток доступа к памяти. По статистике только небольшая доля обращений к памяти потребует высокой степени ассоциативности. Именно для таких обращений служит кэш жертв, предоставляющий высокую ассоциативность для подобных редких запросов. Был предложен Norman Jouppi (DEC) в 1990. Размер такого кеша может составлять от 4 до 16 кеш-линий.
Одним из наиболее экстремальных случаев специализации кэшей можно считать кэш трасс (англ. trace cache), используемый в процессорах Intel Pentium 4. Кэш трасс — это механизм для увеличения пропускной способности загрузки инструкций и для уменьшения тепловыделения (в случае Pentium 4) за счёт хранения декодированных трасс инструкций. Таким образом этот кэш исключал работу декодера при повторном исполнении недавно выполнявшегося кода.
Одной из ранних публикацией о кэше трасс была статья коллектива авторов (Eric Rotenberg, Steve Bennett и Jim Smith), вышедшая в 1996 году под названием «Trace Cache: a Low Latency Approach to High Bandwidth Instruction Fetching.» (Кэш трасс: низколатентный подход для обеспечения высокой пропускной способности загрузки инструкций).
Кэш трасс сохраняет декодированные инструкции либо после их декодирования, либо после окончания их исполнения. Обобщая, инструкции добавляются в кэш трасс в группах, представляющих собой либо базовые блоки, либо динамические трассы. Динамическая трасса (путь исполнения) состоит только из инструкций, результаты которых были значимы (использовались впоследствии), и удаляет инструкции, которые находятся в не исполняющихся ветвях, кроме того, динамическая трасса может быть объединением нескольких базовых блоков. Такая особенность позволяет устройству подгрузки инструкций в процессоре загружать сразу несколько базовых блоков без необходимости заботиться о наличии ветвлений в потоке исполнения.
Линии трасс хранятся в кэше трасс по адресам, соответствующим счётчику инструкций первой машинной команды из трассы, к которым добавлен набор признаков предсказания ветвлений. Такая адресация позволяет хранить различные трассы исполнения, начинающиеся с одного адреса, но представляющие различные ситуации по результату предсказания ветвлений. На стадии подгрузки инструкции (instruction fetch) конвейера инструкций для проверки попадания в кэш трасс используется как текущий счётчик инструкций (program counter), так и состояние предсказателя ветвлений. Если попадание свершилось, линия трассы непосредственно подается на конвейер без необходимости опрашивать обычный кэш (L2) или основное ОЗУ. Кэш трасс подает машинные команды на вход конвейера, пока не кончится линия трассы, либо пока не произойдет ошибка предсказания в конвейере. В случае промаха кэш трасс начинает строить следующую линию трассы, загружая машинный код из кэша или из памяти.
Похожие кэши трасс использовались в Pentium 4 для хранения декодированных микроопераций и микрокода, реализующего сложные x86-инструкции. Smith, Rotenberg and Bennett’s paper См полный текст работы в Citeseer.
