Кэш

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

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

Подробнее о задержках памяти можно прочесть в SDRAM latency: tCAS, tRCD, tRP, tRAS.

В настоящее время, большая часть микропроцессоров для ПК и серверов оснащена минимум тремя независимыми кэшами:

  • кэшем инструкций (ускорение загрузки машинного кода); 
  • кэшем данных (ускорение чтения и записи данных);
  • буфером ассоциативной трансляции (TLB) (ускорение трансляций виртуальных адресов в физические). 

Зачастую, кэш данных имеет вид многоуровневого кэша: L1, L2, L3.

Увеличение размера кэш-памяти прямым образом влияет на скорость работы практически всех без исключения приложений.

История

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

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

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

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

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

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

Принципы

Рассмотрим типичный кэш данных, а вместе с ним и некоторые виды кэшей инструкций. TLB может иметь более сложное устройство; кэш инструкций — устроен проще. Размер каждой кэш-линии в различных процессорах может быть различен, однако для большинства x86-процессоров, он равен 64 байтам. Как правило, размер кэш-линии превышает размер данных, к которому возможен доступ из одной машинной команды. Стандартные размеры: от 1 до 16 байт. Каждой группе данных размером в 1 кэш-линию присвоен порядковый номер. В основной памяти такой номер выступает в качестве адреса памяти с отброшенными младшими битами. В кэше каждой кэш-линии проставлен дополнительный тег. Это адрес продублированных в определенной кэш-линии данных с основной памяти.

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

Попадание дает процессору возможность тут же осуществить чтение/запись данных в кэш-линии с совпавшим тегом. 

Существует также такое понятие, как рейтинг попаданий. Это отношение количества попаданий в кэш к общему количеству запросов к памяти. Это наиболее объективная мера эффективности кэша для выбранного алгоритма/программы.

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

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

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

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

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

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

Кэши со сквозной записью устроены так, что любая запись в них приводит к  единовременной записи в память. Кэши с обратной записью откладывают ее на более позднее время - они проверяют состояние не сброшенных в память кэш-линеек (пометка битом «грязный» - dirty). Запись в память производится по вытеснению такой линейки из кэша. Так, промах в кэше с обратной записью может потребовать двух операций доступа в память: для сброса состояния старой линейки и для чтения новых данных.

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

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

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

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

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

Бит актуальности содержит самую актуальную запись - самую свежую копию данных. 

Промахи

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

Кэши в современных микропроцессорах

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

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

Суперскалярные ЦПУ производят доступ к памяти в несколько этапов: 

  • чтение инструкции;
  • трансляция виртуальных адресов в физические;
  • чтение данных. 

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

  • кэша инструкций;
  • кэша трансляций TLB;
  • кэша данных.

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

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

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

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

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

По ходу увеличения разницы задержек между памятью и быстрейшим кэшем, часть процессоров увеличивает число уровней кэша. Некоторые процессоры доводят его до 3-х уровней на кристалле (Xeon MP «Tulsa» в 2006 году имел 16 МБ кэша L3 на общем кристалле на 2 ядра; Phenom II в 2008 году имел до 6 МБ универсального L3 кэша; Intel Core i7 в 2008 году обладал накристалльным кэшем L3 в 8 МБ, инклюзивным и разделяемым между ядрами). Польза от L3-кэша определяется характером обращений программы в память.

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

Эксклюзивность и инклюзивность

Многоуровневые кеши требуют новых архитектурных решений.

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

В настоящее время, не существует универсального общепринятого названия для промежуточной политики между двумя архитектурами, хотя часто применяется термин mainly inclusive («главным образом инклюзивно»).

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

#