Кэш процессора

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:29, 15 декабря 2016.

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

Назначение кэш памяти

Процессор работает с данными, хранящимися в оперативной памяти. Однако скорость работы оперативной памяти и процессора существенно различаются: если бы процессор напрямую общался с оперативной памятью, то большую часть времени простаивал бы. Именно для сокращения задержек доступа к оперативной памяти и применяется кэш­память, которая значительно более скоростная в сравнении с оперативной. Фактически если оперативная память используется для того, чтобы сгладить задержки доступа к данным на накопителе (HDD-диске, SSD-накопителе или флэш­памяти), то кэш­ процессора применяется для нивелирования задержек доступа к самой оперативной памяти. В этом смысле оперативную память можно рассматривать как кэш накопителя. Однако между оперативной памятью и кэшем процессора есть одно очень серьезное различие: кэш процессора полностью прозрачен для программиста, то есть нельзя адресовать программным образом находящиеся в нем данные.

Есть и другая причина, по которой необходимо использовать кэш­ как промежуточное звено между процессором и оперативной памятью. Дело в том, что процесс чтения и записи данных в оперативную память происходит не отдельными байтами, а пакетами, состоящими как минимум из четырех 64-разрядных ячеек. Это позволяет повысить эффективность работы памяти. Однако процессор загружает данные в свои регистры в виде байт, слов, двойных слов или даже четверных слов. В любом случае он не работает с пакетами данных. То есть минимальная единица информации, считываемая из оперативной памяти, всегда больше той минимальной единицы информации, с которой работает процессор. Возникает вопрос: если из памяти считывается целый пакет данных, а требуется, к примеру, только одно двухбайтовое слово, то куда девать все остальные байты? Отбрасывать их было бы крайне нерентабельно, поскольку велика вероятность, что если сейчас процессору требуются данные, расположенные по одному адресу в оперативной памяти, то в следующий момент он запросит данные, находящиеся по соседнему адресу. А потому считанный пакет данных из оперативной памяти нужно где-­то временно сохранить, то есть требуется промежуточная память для временного хранения считываемых данных. Аналогично запись в оперативную память происходит пакетами данных, но эти пакеты нужно где­-то предварительно сформировать, то есть опять-таки нужна временная память или кэш.[2]

Структура кэша

Система кэш-памяти процессора состоит из двух блоков - контроллера кэш-памяти и собственно самой кэш-памяти. Она представлена на рисунке 1.

Рис.1. Структура и функционирование кэша

Кэш память

Это место, где хранится содержание кэша. Кэш-память процессора изготавливают в виде микросхем статической памяти (Static Random Access Memory, сокращенно - SRAM). По сравнению с другими типами памяти, статическая память обладает очень высокой скоростью работы. Однако, эта скорость зависит также от объема конкретной микросхемы. Чем значительней объем микросхемы, тем сложнее обеспечить высокую скорость ее работы. Если такая особенность учтена производителем, то кэш-память процессора содержит несколько блоков, называемых уровнями. В большинстве процессоров используется трехуровневая система кэша:

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

Контроллер кэш памяти

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

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

  • Размером и структурой кэш-памяти. Чем больше ресурсов имеет в своем распоряжении контроллер, тем ниже вероятность кэш-промаха
  • Эффективностью алгоритмов, по которым контроллер определяет, какая именно информация понадобится процессору в следующий момент времени
  • Сложностью и количеством задач, одновременно решаемых процессором. Чем сложнее задачи и чем их больше, тем чаще "ошибается" контроллер[3]

Организация кэш памяти

Рис.2 Структура гипотетического кэша

Теперь рассмотрим на примере, как устроен кэш. Пусть есть система с 32-разрядной адресацией памяти, то есть для задания адреса каждого байта памяти требуется 4-байтный адрес. Предположим, что наш кэш работает на уровне отдельных байтов, то есть может сохранять в качестве элемента байт оперативной памяти. Тогда каждый структурный элемент кэш­памяти должен сохранять не только байт данных оперативной памяти, но еще и его 4-байтный адрес в оперативной памяти. Получается уже некое подобие строки, которая называется кэш­строкой (cacheline). Адрес сохраняемого байта принято именовать тегом (tag). При чтении данных из кэша процессор формирует адрес, который сравнивается с тегом кэш­строки. В случае совпадения кэш выдает требуемый байт данных, если же совпадения адреса с тегом нет (кэш­промах) — производится обращение к оперативной памяти. Понятно, что для реализации данного механизма необходимо дополнить каждую строку кэша еще и устройством сравнения адреса с тегом (см. рисунок 2).

Рис.3 Пример кэш-строки

Для реализации политики замещения на основе алгоритма FIFO или LRU, необходимо, чтобы каждая строка кэша была дополнена счетчикам возраста. Причем сколько именно байт отводится под счетчик, зависит от того, каков размер кэша. Если, к примеру, описанный нами кэш имеет размер 64 Кбайт, то в нем должно быть 65 536 строк. Тогда необходимо к каждой строке кэша добавить еще двухбайтовое поле (216 = 65 536), чтобы реализовать счетчик возраста строк. Строка, к которой обращались в последнюю очередь, имеет возраст 0, а строка с самым поздним обращением — возраст 65 535. В описанном выше кэше объем полезной сохраняемой информации в шесть раз меньше полного объема кэша, поскольку на каждый байт хранимых данных приходится еще шесть служебных байт. Понятно, что такая структура кэша абсолютно нецелесообразна. Для того чтобы повысить объем полезной информации и одновременно уменьшить объем служебных данных, достаточно сохранять информацию в кэше не в виде отдельных байтов, а в виде блоков данных. То есть в каждой строке кэша будем сохранять не один байт данных, а блок данных фиксированного размера, идущих подряд в оперативной памяти, — он называется размером кэш­строки. Тегом строки будет адрес в оперативной памяти первого содержащегося в ней байта. Отметим, что блок сохраняемых данных в кэш­строке (то есть по сути сама кэш­строка) имеет строго фиксированный размер и является минимальной единицей информации, которая может быть считана из кэша или загружена в кэш. Размер кэш­строки может быть равен только степени двойки (2, 4, 8, 16 и так далее. см. рисунок 3). Как мы помним, чтение из оперативной памяти (равно как и запись в нее) происходит пакетом данных, а кэш работает только с кэш­строками. Поэтому адрес первого байта кэш­строки всегда кратен размеру пакета данных, то есть начало кэш­строки всегда совпадает с началом пакета данных. В рассмотренном нами кэше мы не учитывали биты модификации, которые также добавляются в каждой строке кэша и необходимы для поддержания когерентности.

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

Рис.4 Пример кэш-памяти

Так вот суть кэширования состоит в разбиении RAM на кэш-линии и отображении их на кэш-линии кэш-памяти. Возможно несколько вариантов такого отображения.

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

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

Рис.5 Прямое отображение. Разделение на блоки

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

Рис.6 Прямое отображение. Отображение блока на кэш-память

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

Если - это размер кэш-линии, а - это количество кэш-линий в кэше, то:

  • Для адресации внутри каждой кэш-линии потребуется: бит
  • Для адресации кэш-линий внутри каждого сегмента потребуется: бит
  • Для адресации сегментов RAM потребуется: бит
  • Для адресации байта потребуется: бит

Поиск в такой организации кэша будет строится следующим образом:. .

  1. Извлекается средняя часть адреса, определяющая номер кэш-линии в кэше
  2. Тэг кэш-линии с данным номером сравнивается со старшей частью адреса

Если было совпадение по одному из тэгов, то произошло кэш-попадание. Если не было совпадения ни по одному из тэгов, то произошел кэш-промах.

Полностью ассоциативное отображение

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

Рис.7 Полностью ассоциативное отображение

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

Если - это размер кэш-линии, а - количество кэш-линий, помещающихся в RAM, то:

  • Для адресации байт внутри каждой кэш-линии потребуется: бит
  • Для адресации кэш-линий: бит
  • Для адресации байта потребуется: бит

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

Наборно-ассоциативное отображение

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

Рис.8 Схема кэша при наборно-ассоциативном отображении

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

Рис.9 Наборно-ассоциативное отображение

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

  1. Извлекается средняя часть адреса, определяющая номер набора в кэше. Сложность:
  2. Тэги всех кэш-линий данного сета сравниваются со старшей частью адреса одновременно. Сложность:

- это количество сегментов RAM, количество кэш-линий, размер кэш-линии соответственно. Если было совпадение по одному из тэгов, то произошло кэш-попадание. Если не было совпадение ни по одному из тэгов, то произошел кэш-промах.

Многоуровневая организация

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

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

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

Преимущество исключительных кэшей в том, что они хранят больше данных. Это преимущество больше, когда исключительный кэш 1 уровня сопоставим по размеру с кэшэм 2 уровня, и меньше, если кэш 2 уровня во много раз больше, чем кэш 1 уровня. Когда 1 уровень пропускает и 2 уровень получает доступ в случае попадания, строка кэша попадания в кэшэ 2 уровня обменивается со строкой с 1 уровнем.[4]

Источники

  1. Википедия [Электронный ресурс]: Кэш процессора — материал из Википедии — свободной энциклопедии: Версия 81753821, сохранённая в 16:06, 7 ноября 2016. / Авторы Википедии // Википедия, свободная энциклопедия. — Электрон. дан. — Сан-Франциско: Фонд Викимедиа, 2016. — Режим доступа: https://ru.wikipedia.org/wiki/%D0%9A%D1%8D%D1%88_%D0%BF%D1%80%D0%BE%D1%86%D0%B5%D1%81%D1%81%D0%BE%D1%80%D0%B0#.D0.A1.D1.82.D1.80.D1.83.D0.BA.D1.82.D1.83.D1.80.D0.B0_.D0.B7.D0.B0.D0.BF.D0.B8.D1.81.D0.B8_.D0.B2_.D0.BA.D1.8D.D1.88.D0.B5
  2. Компьютер пресс [Электронный ресурс] : Что такое кэш процессора и как он работает / Дата обращения: 15 декабря 2016 - Режим доступа: http://compress.ru/article.aspx?id=23541#03
  3. Info [Электронный ресурс] : Кэш-память процессора / Дата обращения: 15 декабря 2016 - Режим доступа: http://www.chaynikam.info/kesh-cpu.html
  4. Хабрахабр [Электронный ресурс] : Логическая организация кэш-памяти процессора / Дата обращения: 15 декабря 2016 - Режим доступа: https://habrahabr.ru/post/179647/