Разбираемся в кеш-памяти. Основы и нюансы

Підписуйтеся на Telegram-канал «DOU #tech», щоб не пропустити нові технічні статті.

Меня зовут Никита Потурай, я — Associate Software Engineer, консультант в киевском офисе GlobalLogic. В течение последнего года участвую в аутомотив проекте. В этой статье я расскажу, как устроена кеш-память процессора, в чем ее загвоздки и нюансы. Эта информация пригодится, в первую очередь, начинающим в embedded-направлении. К тому же, любой программист, который занимался низкоуровневой оптимизацией, знает насколько важно, чтобы данные оставались в кеше.

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

Что такое кеш?

Начнем с понятия кеш — это небольшой участок памяти, который выполняет функцию прослойки между основной памятью и процессором. Что же позволяет ему быть в сотни раз быстрее оперативной памяти? Тут играют роль несколько факторов:

1. Разные технологии производства. Кеш реализован на быстрой и стабильной технологии хранения данных (SRAM). Использование данного метода обходится несколько дороже и занимает больше пространства на кристалле (6 транзисторов против 1 транзистора и одного конденсатора в DRAM), однако при этом он дает ощутимый прирост в скорости доступа.

2. Нахождение на кристалле. В силу относительно небольшого объема, кеш можно разместить прямо на кристалле рядом с ядрами процессора. Это значительно ускоряет работу с ним, так как сигналу больше не нужно покидать пределы процессора.

3. Физический размер. Ничто во вселенной не может двигать быстрее скорости света, включая электрические сигналы. Несмотря на то, что технология SRAM требует больше места, кэш все равно получается физически меньше оперативной памяти, что позволяет электрическим сигналам быстрее передвигаться внутри него.

Как он устроен внутри

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

Вот как выглядит ячейка SRAM из 6 транзисторов:

Ячейки разделены на линии произвольного размера. При первом доступе к памяти в кеш загружается не только тот байт, который был прочитан, а еще и несколько соседних, чтобы полностью заполнить линию. Одна линия обычно может поместить в себя около 64 байт полезных данных. Кроме полезных данных, у каждой линии присутствует тег и разнообразные служебные биты. Тег позволяет определить к какому адресу относятся данные. Служебные биты содержат вспомогательную информацию, такую как: заполненность линии, была ли она изменена, как давно был произведен последний доступ.

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

Общую эффективность кеша можно примерно посчитать по простой формуле: perf=hittime+(missrate*misspenalty)

hittime — задержка при доступе к данным в кэше

missrate — частота промахов

mipenalty — задержка при доступе к оперативной памяти

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

Возможности для размещения блока

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

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

Между этими крайностями находится наборно-ассоциативный (set associative) кеш. В этой схеме каждый адрес относится к конкретному набору, в котором находится несколько линий. Внутри набора адрес может занять любую свободную линию. Количество линий в наборе называется канальностью. Кеш может быть 2-канальный (2-way), 4-канальный (4-way), 8-канальный (8-way) и так далее. Номер набора так же определяется путем взятия остатка от деления.

Алгоритм замещения

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

Случайный выбор

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

Очередь (FIFO)

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

Наименее часто используемая линия (LRU)

Если расшифровать данную аббревиатуру — Least Recently Used. Данный алгоритм при нехватке места сбрасывает линию, которая дольше всего не использовалась. Алгоритм эффективен, но сложен в реализации для всего, что более ассоциативно чем 2-канальный кеш, так как с двумя каналами достаточно одного бита на набор, указывающего на последнюю использованную линию. При большей ассоциативности начинаются проблемы, для решения которых необходимо или создавать какой-то список из линий, или хранить для каждой линии метку времени последнего доступа. Проанализировав вышесказанное, можно сделать вывод, что LRU довольно трудно реализовать в железе, вдобавок к этому сложная логика будет сильно замедлять работу всего кеша.

Не наиболее часто используемая линия (NMRU)

Также известен как Not Most Recently Used. Более простой вариант LRU, для кешей с большей ассоциативностью. Обычно реализуется в виде некоторого списка последних использованных линий. Для сброса выбирается случайная линия, которая не находится в списке.

Стратегия записи

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

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

Используемый адрес

Кеш может адресоваться как физическим, так и виртуальным адресом, или даже их комбинацией. Преимущества виртуальной адресации в том, что не нужно дожидаться окончания работы MMU. Физической — в том, что не нужно сбрасывать весь кеш при переключении контекста между процессами.

Когеренция

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

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

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

Пример простейшего протокола инвалидации при записи

Данный протокол называется MSI. Название состоит из первых букв трех возможных состояний каждой линии.

Invalid — линия еще не задействована или была инвалидирована, не содержит полезных данных и может быть перезаписана.
Shared — линия прочитана из основной памяти, и в данный момент доступна только для чтения.
Modified — линия была изменена процессором и в данный момент является самой свежей копией данных.

Переход между состояниями происходит по такой диаграмме:

Переходы, помеченные звездочками, подразумевают сброс линии в основную память. При чтении из памяти линия переходит в состояние S, а при записи (write miss) в состояние M.

Вывод

Даже такой простой на первый взгляд элемент, как кеш, оказывается хранит в себе множество сложных инженерных решений и сотни часов кропотливой работы. Задумываясь об этом, можно по-настоящему оценить всю сложность и скорость развития современных вычислительных систем. Любой программист знает, как важно не отставать от новых технологий, но в то же время не менее важно, особенно для embedded-инженеров, понимать, как это все работает «под капотом». Глубокое понимание своей сферы — это то, что со временем превращает новичков в высококлассных специалистов.

Если у вас остались вопросы, вы хотели бы поделиться своими наблюдениями и обсудить их с Embedded-практиками, присоединяйтесь к нашему Embedded Community. Будем вам рады!

Литература

Ulrich Drepper «What Every Programmer Should Know About Memory»
John L. Hennessy, David A. Patterson «Computer Architecture: A Quantitative Approach»
John Paul Shen, Mikko H. Lipasti «Modern Processor Design: Fundamentals of Superscalar Processors»