Репутація українського ІТ. Пройти опитування Асоціації IT Ukraine
×Закрыть

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

Меня зовут Никита Потурай, я — 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»


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

LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

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

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

Или, что чаще важнее — они там не оставались. Кэш в современных процессорах слабо предсказуем, максимум, что может разработчик — это давать хинты процессору, но как показывает практика, эти хинты на самом деле даже замедляют работу. В статье нужно рассмотреть такие варианты, как память устройств и их отображение в процессорное адресное пространство, write-through режим кеширования региона памяти, использование специальных режимов кеширования для обработчиков больших массивов данных, чтобы они на загаживали кэш, а использовали только read-ahead в пределах нескольких cache line’s. Именно это самое важное и не было рассмотрено в статье.

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

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

Одна линия обычно может поместить в себя около 64 байт полезных данных.

А в байте где-то 7-8 бит полезных данных. Что значит около? Cache line в современных процессорах 64 байта (ровно) потому что современная память работает с гранулярностью 8 байт за транзакцию и 8 транзакций — это более-менее идеально соотношение производительности / размер для записи или чтения, чтобы память не простаивала.

Служебные биты содержат вспомогательную информацию, такую как: заполненность линии, была ли она изменена, как давно был произведен последний доступ.

Информационный мусор. Программист может повлиять на них? Нет? Значит это факультативная информация, не несущая никакой смысловой нагрузки.

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

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

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

Тема важная и абсолютно нераскрытая.

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

Кеширование виртуальных адресов умерло в далёком прошлом, современные x86 могут давать только хинты и не более.

Когеренция

Абсолютно нерасмотрен такое явление как cache snooping между процессором и устройствами, а это основа высокопроизводительных устройств.

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

Тоже пещерность и не нужность.

Любой программист знает, как важно не отставать от новых технологий, но в то же время не менее важно, особенно для embedded-инженеров, понимать, как это все работает «под капотом».

Понимание нужно только того, на что ты можешь влиять. Например, какие алгоритмы умножения и деления используется в твоём процессоре? Это важная информация? Она бесполезная, разве что косвенно может отображать скорость работы команд, но и это далеко не факт.

Ніхто не забороняє написати на доу навіть кращу статтю! ;)

Она бесполезная

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

Не первый раз. Можно ещё Юру Паламарчука позвать, знатный был генератор.

А какие пользователи по-твоему тут «лишние» — те, кто нафлудит ещё тысячу сообщений на обсуждение «к кому лучше идти чтобы получить +500»?

Cache line в современных процессорах 64 байта (ровно) потому что современная память работает с гранулярностью 8 байт за транзакцию и 8 транзакций — это более-менее идеально соотношение производительности / размер для записи или чтения, чтобы память не простаивала.

ARM/32 обычно держал 32 байта, Pentium 4 — было 128, POWER — обычно 128, AArch64 — сейчас чаще 64, но бывают варианты на 32 и на 128 (вот например рассказ про бардак между размерами в соседних ядрах). Так что, да, «около» не в смысле плюс-минус три или пять, а в смысле в два раза больше или меньше :)

С другой стороны, видно, что чёткость описания автор не держит — статью надо было бы вначале проверить на парочке коллег и отработать все замечания. Но и сейчас не поздно, DOU позволяет редактировать исходные статьи.

Информационный мусор. Программист может повлиять на них? Нет? Значит это факультативная информация, не несущая никакой смысловой нагрузки.

Ну почему же. Например, понимать различие write-back и write-through, в плане, как писать в каком случае. Влиять на них не обязательно, а вот учитывать при оптимизации — обязательно.
Вот это как раз к теме о стратегии записи.

Абсолютно нерасмотрен такое явление как cache snooping между процессором и устройствами, а это основа высокопроизводительных устройств.

Ну я так понимаю, что углубляться в проблемы координации разных ядер автору не хотелось (или это предполагало вторую статью в цикле?)

Например, какие алгоритмы умножения и деления используется в твоём процессоре? Это важная информация? Она бесполезная, разве что косвенно может отображать скорость работы команд, но и это далеко не факт.

Так именно что алгоритм может определять не только скорость, а и её зависимость от разных факторов. Например, после 2008 и Intel, и AMD начали оптимизацию работы с денормализованными вещественными с исправлением безумных задержек, а это означает, что часть трюков в математике можно убрать.

В целом, я вижу скорее зависимость от того, что малое количество технических статей не ведёт следствием соревнование за их качество. И проверять надо хотя бы на мышах (но лучше на коллегах, которые не будут хвалить просто за глаза, как тут уже бывало).

Я может на днях допишу свою статью по работе с разными режимами кеширования на x86 на примере живого проекта. Вот тогда покидаешь помидорами %)

Помню в СС якось «включали кеш», і асм код копіпейстили, а на кінець другого тижня пошуку рішення розробник Орлине Око побачив, що в ІДЕ стоїть не чекнута опція «включити кеш».
Це все що тре знати пацанам про кешування.

Цікаво було б заодно ARM згадати.

Недавно підняли швидкість роботи однієї німецької камери майже в 10 разів, дописавши dma-coherent в device tree.

ARM будет может во второй части — там всё гораздо сложнее, чем в x86, но, возможностей для тонких оптимизаций ещё больше.

Не совсем. В ядре линуксе есть API для выделения DMA когерентных буферов, например dma_alloc_coherent(), если бекенд их не поддерживает, то ядро пытается через кешируемую память, если можно, если нет, то опускается до некешируемой. Очень много переменных факторов — полная поддержка кортекс ядра, устройств и прочего, включая настройку pinmux’ов при старте ядра. Но если всё складывается, то ускорить можно очень сильно.

Завтра опубликуют статью, она как раз посвящена этому вопросу.

Всё, статью отправил, должна завтра появиться.

Основна проблема S-RAM — це навіть не кількість транзисторів, інакше існувала б S-RAM, яка була б сумісною с DRAM електрично, але зі значно меншими таймингами (деякі взагалі нульові). Проблема регістрової пам′яті саме в тому, що треба перемкнути декілька транзисторів. А я нагадаю, що польові транзистори майже не витрачають енергії поки відкриті чи закритї, саме в момент перемикання йде колосальний сплеск.

Тому, як не дивно, майбутнє сам за DRAM-кешами. Чому так? Бо можна значно здешевити виробництво.

В чому основна проблема DRAM: треба постійно оновлювати дані, а також висока зарядова (та через це часова) вартість. Але все суттєво змінюється, коли ця пам′ять знаходиться поряд, а напруга суттєво знижується. Наприклад, чи велика напруга в 1В? А в 0.1В? Чи може працювати динамічна пам′ять з напругами менше за 0.1В? Відповідь — так, може. А для надпровідникових матеріалів ліміти значно менші.

Кеш реализован на быстрой и стабильной технологии хранения данных (SRAM)

на DRAM кэш тоже реализуют, даже с учетом контроллера — меньше площадь/больше объем, просто не первых уровней
IBM POWER9 120 MiB eDRAM L3 Cache
IBM z15
L3 256MiB eDRAM 2.3GHz
L4 960MiB eDRAM 2.3GHz
и в некоторых процессорах Intel тоже был eDRAM кэш
игровых приставках и т.д.

6 транзисторов

тоже не обязательно, у того же POWER9 3 типа SRAM Cell:
— 6T high performance
— 6T low leakage
— и 8T 1R/1W

А где такая базовая информация, например чем L1 отличается от L2 ?

Line — строка, а не линия. И чаще таки пишут «кэш», а не «кеш».

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

LRU достаточно просто делать, если вести у каждой строки счётчик по типу:
— Доступ к этой строке — сбрасывается в 0, если был не 0
— Доступ к другой строке — если та другая была при этом со счётчиком не 0, то увеличить на 1, если есть ещё куда увеличивать
— Незанятые строки получают максимальное значение
— При выборе строки для выкидывания выбирается строка с максимальным значением (в смысле, если N строк, то у неё счётчик будет равен N-1 — такая будет всегда)
Опять же, это может быть дорого по энергии.

Что такое «когеренция», непонятно — такой термин крайне редко используется — а вот «когерентность» как раз вполне принято.

MSI — плохая аббревиатура (слишком много других значений), лучше упомянуть, что принципы следует искать по MESI или MOESI, и откинуть (если не нужно) подходы для многопроцессорных систем.

Ну а в целом — конечно, статья самого начального уровня, но кому-то может стать откровением именно факт существования и важности подобных механизмов. Ну и вообще технические статьи тут на пользу :)

С каких пор линия кеша стала строкой?

Всегда была (в грамотных переводах, разумеется).

Застаріла російськомовна термінологія,
в книгах Гука, типа «архітектура процесорів..» точно було строка, коли йшлось про кеш L1

В американском языке не используется queue для указания организации данных, только line, что может означать и блок и очередь, ну и линию тоже, но в данном случае скорее блок.

Подписаться на комментарии