Кэш микропроце́ссора — кэш (сверхоперативная память), используемый микропроцессором компьютера для уменьшения среднего времени доступа к компьютерной памяти. Является одним из верхних уровней иерархии памяти. Кэш использует небольшую, очень быструю память (обычно типа SRAM), которая хранит копии часто используемых данных из основной памяти. Если большая часть запросов в память будет обрабатываться кэшем, средняя задержка обращения к памяти будет приближаться к задержкам работы кэша.
Когда процессору нужно обратиться в память для чтения или записи данных, он сначала проверяет, доступна ли их копия в кэше. В случае успеха проверки процессор производит операцию, используя кэш, что значительно быстрее использования более медленной основной памяти. Подробнее о задержках памяти см. Латентность SDRAM: tCAS, tRCD, tRP, tRAS.
Данные между кэшем и памятью передаются блоками фиксированного размера, также называемыми линиями кэша () или блоками кэша.
Большинство современных микропроцессоров для компьютеров и серверов имеет как минимум три независимых кэша: кэш инструкций для ускорения загрузки машинного кода, кэш данных для ускорения чтения и записи данных, и буфер ассоциативной трансляции (TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных. Кэш данных часто реализуется в виде многоуровневого кэша (L1, L2, L3, L4).
Увеличение размера кэш-памяти может положительно влиять на производительность почти всех приложений, хотя в некоторых случаях эффект незначителен. Работа кэш-памяти обычно прозрачна для программиста, однако для её эффективного использования в некоторых случаях применяются специальные алгоритмические приёмы, изменяющие порядок обхода данных в ОЗУ или повышающие их локальность (например, при блочном умножении матриц)Intel 64 and IA-32 Architectures Software Developer’s Manual. Volume 1: Basic Architecture. Order number 253665-021..
Принцип работы
Данный раздел описывает типичный кэш данных и некоторые виды кэшей инструкций; буфер ассоциативной трансляции (TLB) может быть устроен сложнее, а кэш инструкций — проще. На диаграмме справа изображены основная и кэш-память. Каждая строка — группа ячеек памяти содержит данные, организованные в кэш-линии. Размер каждой кэш-линии может различаться в разных процессорах, но для большинства x86-процессоров он составляет 64 байта. Размер кэш-линии обычно больше размера данных, к которому возможен доступ из одной машинной команды (типичные размеры от 1 до 16 байт). Каждая группа данных в памяти размером в 1 кэш-линию имеет порядковый номер. Для основной памяти этот номер является адресом памяти с отброшенными младшими битами. В кэше каждой кэш-линии дополнительно ставится в соответствие тег, который является адресом продублированных в этой кэш-линии данных в основной памяти.
При доступе процессора в память сначала производится проверка, хранит ли кэш запрашиваемые из памяти данные. Для этого производится сравнение адреса запроса со значениями всех тегов кэша, в которых эти данные могут храниться. Случай совпадения с тегом какой-либо кэш-линии называется попаданием в кэш (), обратный же случай называется кэш-промахом (). Попадание в кэш позволяет процессору немедленно произвести чтение или запись данных в кэш-линии с совпавшим тегом. Отношение количества попаданий в кэш к общему количеству запросов к памяти называют рейтингом попаданий (), оно является мерой эффективности кэша для выбранного алгоритма или программы.
В случае промаха в кэше выделяется новая запись, в тег которой записывается адрес текущего запроса, а в саму кэш-линию — данные из памяти после их прочтения либо данные для записи в память. Промахи по чтению задерживают исполнение, поскольку они требуют запроса данных в более медленной основной памяти. Промахи по записи могут не давать задержку, поскольку записываемые данные сразу могут быть сохранены в кэше, а запись их в основную память можно произвести в фоновом режиме. Работа кэшей инструкций во многом похожа на вышеприведенный алгоритм работы кэша данных, но для инструкций выполняются только запросы на чтение. Кэши инструкций и данных могут быть разделены для увеличения производительности (принцип, используемый в Гарвардской архитектуре) или объединены для упрощения аппаратной реализации.
Для добавления данных в кэш после кэш-промаха может потребоваться вытеснение () ранее записанных данных. Для выбора замещаемой строки кэша используется эвристика, называемая политика замещения (). Основной проблемой алгоритма является предсказание, какая строка вероятнее всего не потребуется для последующих операций. Качественные предсказания сложны, и аппаратные кэши используют простые правила, такие, как LRU. Пометка некоторых областей памяти как некэшируемых () улучшает производительность за счёт запрета кэширования редко используемых данных. Промахи для такой памяти не создают копии данных в кэше.
При записи данных в кэш должен существовать определённый момент времени, когда они будут записаны в основную память. Это время контролируется политикой записи (). Для кэшей со сквозной записью () любая запись в кэш приводит к немедленной записи в память. Другой тип кэшей, обратная запись (иногда также называемый copy-back), откладывает запись на более позднее время. В таких кэшах отслеживается состояние кэш-линеек ещё не сброшенных в память (пометка битом «грязный» ). Запись в память производится при вытеснении подобной строки из кэша. Таким образом, промах в кэше, использующем политику обратной записи, может потребовать двух операций доступа в память, один для сброса состояния старой строки и другой — для чтения новых данных.
Существуют также смешанные политики. Кэш может быть со сквозной записью (), но для уменьшения количества транзакций на шине записи могут временно помещаться в очередь и объединяться друг с другом.
Данные в основной памяти могут изменяться не только процессором, но и периферией, использующей прямой доступ к памяти, или другими процессорами в многопроцессорной системе. Изменение данных приводит к устареванию их копии в кэше (состояние stale). В другой реализации, когда один процессор изменяет данные в кэше, копии этих данных в кэшах других процессоров будут помечены как stale. Для поддержания содержимого нескольких кэшей в актуальном состоянии используется специальный протокол поддержки когерентности.
Структура записи в кэше Типичная структура записи в кэше Блок данных тег бит актуальности
Блок данных (кэш-линия) содержит непосредственную копию данных из основной памяти. Бит актуальности означает, что данная запись содержит актуальную (самую свежую) копию.
Структура адреса
тег индекс смещение
Адрес памяти разделяется (от старших бит к младшим) на Тег, индекс и смещение. Длина поля индекса равна бит и соответствует ряду (строке) кэша, используемой для записи. Длина смещения равна .
Ассоциативность
Ассоциативность является компромиссом. Проверка большего числа записей требует больше затрат энергии, площади чипа, и, потенциально, времени. Если бы существовало 10 мест, в которые алгоритм вытеснения мог бы отобразить место в памяти, тогда проверка наличия этого места в кэше потребовала бы просмотра 10 записей в кэше. С другой стороны, кэши с высокой ассоциативностью подвержены меньшему количеству промахов (см. ниже «конфликтующие промахи») и процессор тратит меньше времени на чтения из медленной основной памяти. Существует эмпирическое наблюдение, что удвоение ассоциативности (от прямого отображения — к 2-канальной или от 2- — к 4-канальной) имеет примерно такое же влияние на интенсивность попаданий (hit rate), что и удвоение размера кэша. Увеличение ассоциативности свыше 4 каналов приносит меньший эффект для уменьшения количества промахов (miss rate) и обычно производится по другим причинам, например, из-за пересечения виртуальных адресов.
В порядке ухудшения (увеличения длительности проверки на попадание) и улучшения (уменьшения количества промахов): кэш прямого отображения () — наилучшее время попадания и, соответственно, лучший вариант для больших кэшей; 2-канальный множественно-ассоциативный кэш ; 2-канальный skewed ассоциативный кэш (); 4-канальный множественно-ассоциативный кэш (); полностью ассоциативный кэш, — наилучший (самый низкий) процент промахов (miss rate) и лучший вариант при чрезвычайно высоких затратах при промахе (miss penalty).
Псевдоассоциативный кэш Псевдоассоциативный кэш — это тип кэш-памяти, который использует комбинацию прямого и наборного способов поиска кэш-блока. Псевдоассоциативный кэш разделяет кэш-память на несколько частей, называемых наборами. Каждый набор содержит несколько кэш-линий или блоков данных. Когда происходит обращение к памяти, хэш-адрес элемента вычисляется, и затем проверяются все линии в соответствующем наборе памяти. Кэш-память с псевдоассоциативной организацией обеспечивает компромисс между простотой проекта и эффективностью поиска данных.
Виды промахов Промах по чтению из кэша инструкций. Обычно дает очень большую задержку, поскольку процессор не может продолжать исполнение программы (по крайней мере, текущего потока исполнения) и вынужден простаивать в ожидании загрузки инструкции из памяти.
Промах по чтению из кэша данных. Обычно дает меньшую задержку, поскольку инструкции, не зависящие от запрошенных данных, могут продолжать исполняться, пока запрос обрабатывается в основной памяти. После получения данных из памяти можно продолжать исполнение зависимых инструкций.
Промах по записи в кэш данных. Обычно дает наименьшую задержку, поскольку запись может быть поставлена в очередь и последующие инструкции практически не ограничены в своих возможностях. Процессор может продолжать свою работу, кроме случаев промаха по записи с полностью заполненной очередью.
Категории промахов (Three Cs) Compulsory misses — промахи, вызванные первым упоминанием запрошенного адреса. Размеры кэшей и их ассоциативность не влияют на количество данных промахов. Предвыборка (prefetching), как программная, так и аппаратная, может помочь, так же, как и увеличение размера кэш-линии (в качестве вида аппаратной предвыборки). Такие промахи иногда называются «холодными». Capacity misses — промахи, вызванные исключительно конечным размером кэша, происходящие вне зависимости от степени ассоциативности или размера кэш-линии. График таких промахов относительно размера кэша может дать некоторую меру временной локальности (temporal locality) некоторого набора запросов в память. Стоит заметить, что не существует понятия полного кэша, пустого кэша или почти полного кэша, так как кэши процессора почти все время имеют кэш-линии в занятом состоянии, и, значит, практически каждое заведение новой линии потребует гашения уже занятой. Conflict misses — промахи, вызванные конфликтом. Их можно избежать, если бы кэш не вытеснил запись ранее. Можно дополнительно разделить на промахи, вызванные отображением (конкретным значением ассоциативности) и промахи замещения, которые вызваны конкретным алгоритмом выбора записей для замещения.
Трансляция адресов
Большая часть процессоров общего назначения реализует какой-либо вариант виртуальной памяти. Кратко говоря, каждая программа, исполняющаяся на машине, видит собственное упрощенное адресное пространство, содержащее код и данные только этой программы. Любая программа использует своё виртуальное адресное пространство вне зависимости от его местоположения в физической памяти.
Наличие виртуальной памяти требует от процессора проведения трансляции виртуальных (математических) адресов, используемых программой, в физические адреса, соответствующие реальному местоположению в ОЗУ. Часть процессора, проводящая это преобразование, называется устройство управления памятью (MMU). Для ускорения трансляций в MMU добавлен кэш недавно использованных отображений (соответствий виртуальных и физических адресов), называемый Translation Lookaside Buffer (TLB).
Для дальнейшего описания важны три особенности процесса трансляции адресов: