Меню
Главная
Случайная статья
Настройки
|
Кэш микропроцессора — кэш (сверхоперативная память), используемый микропроцессором компьютера для уменьшения среднего времени доступа к компьютерной памяти. Является одним из верхних уровней иерархии памяти[1]. Кэш использует небольшую, очень быструю память (обычно типа SRAM), которая хранит копии часто используемых данных из основной памяти. Если большая часть запросов в память будет обрабатываться кэшем, средняя задержка обращения к памяти будет приближаться к задержкам работы кэша.
Когда процессору нужно обратиться в память для чтения или записи данных, он сначала проверяет, доступна ли их копия в кэше. В случае успеха проверки процессор производит операцию, используя кэш, что значительно быстрее использования более медленной основной памяти. Подробнее о задержках памяти см. Латентность SDRAM: tCAS, tRCD, tRP, tRAS.
Данные между кэшем и памятью передаются блоками фиксированного размера, также называемыми линиями кэша (англ. cache line) или блоками кэша.
Большинство современных микропроцессоров для компьютеров и серверов имеет как минимум три независимых кэша: кэш инструкций для ускорения загрузки машинного кода, кэш данных для ускорения чтения и записи данных, и буфер ассоциативной трансляции (TLB) для ускорения трансляции виртуальных (логических) адресов в физические, как для инструкций, так и для данных. Кэш данных часто реализуется в виде многоуровневого кэша (L1, L2, L3, L4).
Увеличение размера кэш-памяти может положительно влиять на производительность почти всех приложений[2], хотя в некоторых случаях эффект незначителен[3]. Работа кэш-памяти обычно прозрачна для программиста, однако для её эффективного использования в некоторых случаях применяются специальные алгоритмические приёмы, изменяющие порядок обхода данных в ОЗУ или повышающие их локальность (например, при блочном умножении матриц)[4].
Содержание
Принцип работы
Данный раздел описывает типичный кэш данных и некоторые виды кэшей инструкций; буфер ассоциативной трансляции (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).
Псевдоассоциативный кэш — это тип кэш-памяти, который использует комбинацию прямого и наборного способов поиска кэш-блока. Псевдоассоциативный кэш разделяет кэш-память на несколько частей, называемых наборами. Каждый набор содержит несколько кэш-линий или блоков данных. Когда происходит обращение к памяти, хэш-адрес элемента вычисляется, и затем проверяются все линии в соответствующем наборе памяти. Кэш-память с псевдоассоциативной организацией обеспечивает компромисс между простотой проекта и эффективностью поиска данных.
Виды промахов
Промах по чтению из кэша инструкций. Обычно дает очень большую задержку, поскольку процессор не может продолжать исполнение программы (по крайней мере, текущего потока исполнения) и вынужден простаивать в ожидании загрузки инструкции из памяти.
Промах по чтению из кэша данных. Обычно дает меньшую задержку, поскольку инструкции, не зависящие от запрошенных данных, могут продолжать исполняться, пока запрос обрабатывается в основной памяти. После получения данных из памяти можно продолжать исполнение зависимых инструкций.
Промах по записи в кэш данных. Обычно дает наименьшую задержку, поскольку запись может быть поставлена в очередь и последующие инструкции практически не ограничены в своих возможностях. Процессор может продолжать свою работу, кроме случаев промаха по записи с полностью заполненной очередью.
Категории промахов (Three Cs)- 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 одновременно с запросом данных из кэш-памяти.
Виртуальное тегирование и механизм vhints
Но виртуальная индексация не является лучшим выбором для других уровней кэша. Стоимость обнаружения пересечения виртуальных адресов (aliasing) растет с увеличением размера кэша и, в результате, большинство реализаций L2 и более дальних от процессора уровней кэша использует индексирование по физическим адресам.
Достаточно длительное время кэши использовали для тегов как физические, так и виртуальные адреса, хотя виртуальное тегирование в настоящее время встречается очень редко. Если TLB-запрос заканчивается раньше запроса в кэш-память, физический адрес будет доступен для сравнения с тегом к моменту, когда это будет необходимо, и, следовательно, виртуальное тегирование не потребуется. Большие кэши чаще тегируются физическими адресами, и только небольшие быстродействующие кэши используют для тегов виртуальные адреса. В современных процессорах общего назначения, виртуальное тегирование заменено на механизм vhints, описанный далее.
|
|
