Кэш-память процессора
AmeliePick
В качестве вступления:
Некоторые термины специально изменены, для лучшего понимая материала. Так например, блок(строку) данных из ОЗУ принято называть страницой.
Некоторые понятия, как например, представление структуры кэш-линии —являются чисто абстрактными, т.к в действительности могут иметь разную структуру в зависимости от архитектуры системы.
Представьте, что вы пишите работу на тему масонства. Идёте в библиотеку(да, я в курсе, что сейчас 21 век и есть Интернет, но предположим, что у нас его нет) берёте нужную книгу, приходите к себе в кабинет, пишите статью. Теперь вам нужна другая книга, вы относите уже ненужную вам книгу и берёте в библиотеке другую, приходите в кабинет, продолжаете работать. В ходе работы вам понадобилась цитата из первой книги, вы снова относите ненужную ныне книгу и берёте в библиотеке ту, которую брали первой. Возникает вопрос: зачем мы так делаем? Почему мы не храним несколько книг у себя кабинете?
Временная локальность - определяет, что если мы взяли какую-то книгу, воспользовались ею и вернули обратно, то эта книга нам вскоре снова понадобится.
Пространственная локальность - определяет, что несколько книг, стоящих рядом с выбранной, скорее всего тоже нам вскоре понадобятся.
Да, в данном примере в роли ОЗУ выступает библиотека. Книги - это данные из ОЗУ. А мы и наш кабинет - это процессор.
В силу того, что в настоящее время процессор гораздо быстрее памяти, то когда он обращается к ОЗУ за данными, ему приходится простаивать какое-то время. И связано это не только с малым прогрессом памяти, но и с её устройством.
Немного hardware
Почти вся ОЗУ является динамической и каждый бит информации представляется в виде заряда конденсатора. Когда с него читается информация, он разряжается и ему требуется некоторое время, что бы регенерироваться и дальше хранить бит. И в момент регенерации памяти, обмен данными невозможен.
С приходом синхронной динамической памяти(SDRAM) скорость памяти увеличилась, но она по-прежнему медленнее процессора. В итоге было принято решение хранить копии определённых данных из ОЗУ прямо в процессоре. Сама кэш-память расположена на одном чипе вместе с ядрами ЦП, а это значит, что частота памяти приблизительно равна частоте процессора, что и делает её самой быстрой памятью в системе.
Сама кэш память имеет уже другую структуру. Она является статичной(SRAM). Статичная потому, что в ней нет необходимости регенерации хранимых данных. Данные хранятся в бистабильной схеме, состоящей из двух перекрестно соединенных инверторов.
Как процессор работает с памятью
Когда процессору нужно получить данные с определенного адреса в ОЗУ, он сперва проверяет эти данные в кэше, если их там нет(кэш промах), процессор ищет их в ОЗУ, если и в ОЗУ нет нужных данных, процессор вынужден искать данные в виртуальной памяти - на диске. Что в свою очередь занимает очень много времени. Когда процессор находит данные, он помещает их в кэш, обрабатывает их, далее эти данные могут быть загружены обратно в память, согласно политике замещения данных.
Если же процессор находит данные в кэше(попадание в кэш), эти данные немедленно будут обработаны.
Процент попаданий и промахов вычисляется так:
Miss Rate = кол-во промахов / кол-во обращений к памяти = 1 – Hit Rate. Hit Rate = кол-во попаданий / кол-во обращений к памяти = 1 – Miss Rate.
Среднее время доступа(Average Memory Access Time, AMAT) - среднее время, которое тратит ЦП, ожидая доступа к памяти при выполнении команд загрузки или сохранения данных.
AMAT = Tcache + MRcache(Tmm + MRmm * Tvm), где Tcache, Tmm, Tvm - время доуступа к кэшу, ОЗУ, виртуальной памяти. MRcache, MRmm - процент промахов кэша и ОЗУ. Полученное значение является тактами.
Стратегия кэширования
Кэш процессора состоит как из кэш-памяти так и из кэш-контроллера, задачей которого является загрузка и чтение данных в/из кэш-памяти, а так же сведение колличества кэш-промахов к минимуму, обеспечение актуальности данных. Поэтому контроллер должен как-то предполагать, какие данные вскоре будут нужны. Самая простая стратегия заключается в том, что запись в кэш происходит в тот момент, когда кэш-контроллер не обнаружил нужных данных. Тоесть происходит загрузка по требованию.
Более продвинутая стратегия - упреждающая загрузка данных. Предполагается, что данные из ОЗУ обрабатываются в порядке возрастания адресов. Однако этот механизм тоже имеет недостаток, т.к не всегда данные в программе могут обрабатываться по порядку.
Упреждающая спекулятивная загрузка - алгоритмы, которые предсказывают адрес следующего блока памяти на основе прошлых обращений. Именно такие алгоритмы используются в современных ЦП.
Организация кэша
Кэш состоит из блоков фиксированной длины - кэш линий. Кэш-линия - это минимальная еденица с которой работает кэш.
Как узнать сколько кэш-линий содержит кэш:
B = C/b,
где B - кол-во строк в кэше, C - ёмкость кэша(в машиных словах или байтах), b - длина кэш-строки.
Длина кэш строки обычно равна от 16 до 64 байт. Думаю, будет понятно на примере:
Есть кэш объёмом 32КиБайт. Объём одной кэш-строки 32 байта.
Найдём кол-во кэш-строк: 32КиБайта = 32 * 1024 байт. 32 * 1024 / 32 = 1024 кэш-строк.
Когда процессор записывает данные в кэш-линию, в неё попадают байты не только находящиеся по текущему адресу, но так же и из соседних адресов. Ибо кэш-строка фиксированного размера - реализована пространственноая локальность.
Загрузка данных в кэш может осуществляться по двум стратегиям - Look Through, Look Aside. В случае использования первой стратегии загрузка в кэш осуществляется при фиксировании кэш-промаха. В случае использования стратегии Look Aside загрузка в кэш может происходить параллельно с проверкой данных в кэш-памяти и другой любой памяти. Если копия данных есть в кэше, то запрос прекращается. Проще говоря, когда процессор получает команду считать данные, он ищет эти данные одновременно и в кэше и в ОЗУ или в виртуальной памяти. При такой стратегии увеличивается энергопотребление из-за нагрузки на систему, но зато сокращается время доступа к памяти в случае кэш-промаха.
Ассоциативность, структуры кэша
Если сказать простыми словами, то ассоциативность показывает как ОЗУ отображается на кэш память. С увеличением степени ассоциативности эффективность кэша существенно возрастает.
Как было сказано выше, кэш-линия это минимальная еденица работы с кэш-памятью(размер кэш-линии зависит от конкретной архитектуры ЦП). Но как именно ЦП записывает данные в кэш-линию и потом находит нужную информацию из неё или как ОЗУ отображается на кэш?
Разобьём ОЗУ на линии или блоки. Если мы читаем один байт, то прочтётся всё слово выровненное на размер кэш-линии, которое захватит с собой определённый диапазон адресов, есстественно. По этой причине в качестве примера разобьём ОЗУ на блоки, выровненные на размер кэш-строки. Кэш-линия состоит в свою очередь из нескольких областей. А именно:
Область данных - непосредственно, сами данные из ОЗУ. В документациях, под термином размер кэш-строки, по умолчанию имеется в виду именно эта область.
Тег - адрес блока данных из ОЗУ.
Индекс - каждый блок данных размером с кэш-линию имеет свой номер.
Область дополнительных данных - хранит бит валидности(V-valid), "грязный"(dirty-D) бит и другую информацию для алгоритмов замещения и актуальности данных.
Тег - хранит несколько страших бит. Т.к именно старшая часть адреса меняется реже всего, а кэш-линия хранит данные из нескольких адресов, то сравнение на наличие данных происходит с помощью тега.
Индекс - средняя часть адреса. Номер строки. Указывает на какую строку будет отображаться этот адрес.
Смещение - Малдшая часть адреса. Т.к кэш-линия хранит фиксированный объём, то для того, что бы прочитать необходимый байт из неё, используется смещение. Таким образом, из нескольких слов выделяется нужное.
Размер смещения: младшие log2N бит адреса, где N - размер кэш-строки.
Размер индекса: log2N, где N - количество строк в кэше.
Размер тега: разрядность адреса - размер индекса - смещение.
Data - сами данные.
Tag - адрес блока памяти из ОЗУ.
Valid bit - бит актуальности данных - показывает, что данные в кэш-линии имеют смысл. При включении системы, все кэш-линии хрянят ноль в качестве бита валидности.
Структуры кэш-памяти
Полностью ассоциативный кэш
В таком кэше на каждую кэш-линию могут отобразиться все адреса ОЗУ.
Минус такого кэша заключается в долгом поиске данных, т.к для этого надо просмотреть тег каждой строки. И даже если бы за один такт просматривалось по два тега, это всё равно было бы очень медленно. Поэтому полностью ассоциативные кэши, обычно, небольшого размера.
Кэш с прямым отображением
В таком кэше, каждая строка ОЗУ жёстко закреплена за определенной кэш-линией. И естественно, в силу того, что кэш меньше ОЗУ, каждая кэш-линия может содержать данные только строго определенных строк из ОЗУ.
Этот кэш уже не имеет недостатка по скорости нахождения данных, т.к теперь требуется просмотреть всего лишь один тег. Однако есть и существенный недостаток. Т.к на одну кэш-строку претендуют несколько строк ОЗУ, а в единицу времени кэш-строка может хранить данные только из одной строки ОЗУ, то когда происходит кэш-промах, данные в кэш-строке перезаписываются. Таким образом, если программа хранит часто используемые данные в тех адресах, которые отображаются на одну кэш-линию, ЦП будет постоянно перезаписывать кэш-строку, даже несмотря на то, что другие кэш-строки пустые. Это увеличивает процент кэш-промахов, что существенно снижает производительность.
Узнать, в какую кэш линию будет загружена информация из ОЗУ можно по формуле:
Ncache line = Nmemory mod Nmax cache lines , где Nmemory - номер строки ОЗУ, Nmax cache lines - количество кэш строк в кэше.
Наборно ассоциативный кэш
или
N-секционный наборно-ассоциативный кэш (N-way set associative cache)
Этот кэш лишён недостатков двух предыдущих типов кэшей. Кэш память делится на наборы (каналы. N-way cache — N-канальный кэш), которые являются ассоциативными к каждому адресу ОЗУ. В каждом наборе содержится по две кэш-линии. Количество наборов всегда равно степени 2 и называется степенью ассоциативности или канальностью(way).
Примечательно, что если количество наборов равно количеству кэш-линий, то мы получим полностью ассоциативный кэш. Или если будет только один набор - получится кэш с прямым отображением.
Любой элемент может быть размещён в любом банке, но в каждом банке ему отведена строго определённая строка. Т.к каждый банк представляет собой память с прямым отображением, то и номер строки определяется так же как и в кэше-прямого отображения. Понятно, что из-за структуры кэша, изменится и размер индекса и тега.
Т.к количество строк в кэше: количество банков * 2, в каждом банке по две строки, то размер индекса будет меньше, следовательно размер тега увеличится на log2S, где S - кол-во банков(каналов).
Определить в какую строку банка будет записана информация можно по той же формуле кэша прямого отображения, только теперь вместо колличества строк всего кэша, учитывается количество строк в банке.
Ncache line = Nmemory mod Nmax bank cache lines , Nmemory - номер строки ОЗУ.
Однако точно определить банк не получится, т.к всё зависит от состояния кэш-памяти. В любом случае, будет найден такой банк, в котором нужная строка будет свободна либо заменена с помощью алгоритмов замещения.
Многоуровневая организация кэша
Проблема заключается в том, что чем больше объём кэша, тем он медленее. Из двух вариантов: сделать один большой, но медленный кэш или сделать несколько маленьких, но быстрых - лучше оказывается второй вариант. Так современные ЦП имееют как минимум два уровня кэша. В ЦП Intel используется три уровня.
Кэш первого уровня является самым малым по объему, но и самым быстрым. Он локален для каждого ядра. В свою очередь поделён на кэш данных - L1D и кэш инструкций - L1I(принцип гарвардской архитектуры процессора).
Кэш второго уровня имеет объём чуть больше чем кэш первого уровня из-за этого медленнее. Так же локален для каждого ядра. Уже не разделён на части, но так же хранит данные и инструкции, но обращение к ним происходит реже, чем к данным и инструкциям из L1 кэша.
Кэш третьего уровня самый большой по объему и в то же время самый медленный из всех уровней. Является общим для всех ядер.
Политики замещения данных в кэшпамяти
Кэш не бесконечный и место в нём рано или поздно кончится, более того, он почти всегда полон, поэтому надо как-то находить место для новых записей - замещать данные в кэше новыми. На это есть несколько алгоритмов, три из последних которые требуют ещё одно поле и несколько бит в зависимости от размера памяти.
1) Random - сулчайным образом выбирается строка, которая будет заменена другой информацией. В данном случае не учитывается частота использования замещаемых данных, ничего! Поэтому этот алгоритм нигде не используется.
Теперь про ещё одно поле, а именно счётчик, который обновляется всякий раз при обращении к кэш-строке. Строка, к которой обращались в самый последний раз имеет значение 0. Строка, к которой дольше всего не было запросов имеет значение приблизительное к объёму кэша.
Например кэш имеет объём 64 КиБайт -> 65 536 байт, разрядность кэш-строки 32 байта .
Кол-во строк в кэше: 64 * 1024 / 32 = 2048.
Путём простых вычислений получаем: log2 (2080) = 11 бит размер счётчика.
Значит самая долго не используемая строка будет иметь счётчик со значением 2080.
2) LRU (Least Recently Used) - замещаются данные, которые дольше всего не использовались.
3) FIFO (First In First Out) - из названия понятно: обновляется та строка, которая была загружена самой первой. Так же этот алгоритм используется не только внутри ЦП, но так же служит основой для такой структуры данных как очередь(Первый зашёл первый вышел).
4) LRR (Least Recently Replaced) - замещение происходит в строке в которой наименее старые данные.
Когерентность кэша
Политика кэша, обеспечивающая акутальность данных в кэше и оперативной памяти. Проблема заключается в том, что ОЗУ доступна как на чтение, так и на запись, что ставит вопрос об отслеживании изменений. К ОЗУ может обратиться перефейрийное устройство, в многопроцессорных системах - разные процессоры, в многоядерных ЦП - разные ядра. Например устройство обратилось к ОЗУ, несколько операциями ранее ЦП изменил данные по этому адресу и сохранил у их себя в кэше, сделав тем самым данные в ОЗУ не актуальными. В таком случае устройство получит неверные данные.
Есть несколько вариантов обеспечения когерентности:
1) Алгоритм сквозной записи или Write Through - предполагает, что вся ОЗУ кэшируется только для чтения и запись в неё происходит минуя кэш, тем самым увеличивается процент кэш-промахов. В силу этого недостатка - алгоритм не используется.
2) Алгоритм обратной записи или Write Back - при использовании данного алгоритма каждая кэш-строка хранит бит модфикации или "грязный"(dirty) бит. Если данные в кэш-линии изменилсь - dirty bit = 1, иначе 0.
Пример: когда устройство обратилось в память, кэш контроллер проверяет этот адрес на наличии в кэше, если такой есть, просматривается "рязный" бит. Если он равен 1, значит данные в ОЗУ не актуальны, и содержимое кэш-строки выгружается в ОЗУ, далее устройство забирает эти данные из основной памяти.
Существует множество протоколов для когерентности кэша с обратной записью:
· Протокол MSI
· Протокол MESI
· Протокол MOSI
· Протокол MOESI
· Протокол MOWESI
· Протокол MERSI
· Протокол MESIF
· Протокол Write-once
· Протокл MESI - один из самых известных. По ссылке можно найти его подробное описание и принцип работы.
Источники
Схемы DRAM/SRAM: Цифровая схемотехника и архитектура компьютера - Дэвид М. Харрис и Сара Л. Харрис.
Preview Art: AmeliePick.
Pictures in the article: AmeliePick.
Art in the end: Alena Aenami -> ArtStation .
Peace of mind !
