Устройство кеша

Предпосылки: иерархия памяти и кеш (кеш-линия, L1/L2/L3, три типа промахов); хеш-таблица (хеш-функция, коллизия, бакет).

← Иерархия памяти | Когерентность кешей →

Иерархия объясняет, почему быстрая и ёмкая память одновременно невозможна. Кеш-линия объясняет, почему обращения доставляются блоками. Но сам факт попадания в L1 за один такт требует отдельного объяснения: CPU за 0.3 нс обращается к массиву из сотен линий и узнаёт, есть ли среди них нужная. Как вообще можно проверить присутствие за один такт?

Кроме поиска, у кеша есть ещё несколько задач, которые он обязан решать одновременно. Если на любом уровне кеш не справляется, иерархия разваливается — L1 перестаёт ловить 95% обращений, и предсказуемая задержка 1 нс превращается в 100 нс.

Кеш — несколько аппаратных компонентов, каждый отвечает за свой вопрос:

Как найти линию. Разбор адреса на тег/индекс/смещение и параллельная сверка тегов в наборе. Определяет ассоциативность.
Что выбросить, когда места нет. Политика вытеснения — приближённый LRU, адаптивные варианты.
Кто держит копию на каждом уровне. Inclusive или exclusive связь между L1, L2, L3.
Что делать с записью. Write-through или write-back, write-allocate или нет. Плюс store buffer — чтобы запись не останавливала конвейер.
Как угадать следующий адрес. Hardware prefetch: обнаружить паттерн и подтянуть линии заранее.

Каждый компонент — отдельный раздел ниже. Все они работают одновременно на каждом обращении.

Поиск линии: тег, индекс, смещение

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

Хеш-таблица с цепочками              Кеш
------------------------------------------------------
хеш(ключ) -> номер бакета            биты адреса -> номер набора
бакет хранит несколько пар           набор хранит несколько линий
поиск: последовательно по цепочке    поиск: все теги параллельно (за такт)
значение                             данные кеш-линии
коллизия: два ключа в одном бакете   конфликт: два адреса в одном наборе

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

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

Физический адрес разбивается на три поля:

|<----- тег ----->|<-- индекс -->|<-- смещение -->|
|   старшие биты  |  средние биты|  младшие биты  |
 
Смещение (offset):  номер байта внутри линии (0..63).
                     64 позиции -> 6 бит для их адресации.
 
Индекс (index):     номер набора в кеше.
                     Аналог хеш-функции: выбирает бакет.
 
Тег (tag):          оставшиеся старшие биты адреса.
                     Отличает линии, попавшие в один набор.

Механизм поиска: CPU берёт биты индекса, мгновенно находит нужный набор (это адресация в аппаратном массиве — за один такт). Внутри набора параллельно сравнивает тег запроса с тегами всех линий. Совпал — hit, данные отдаются по смещению. Не совпал ни один — miss.

       Набор 0:  [тег|данные] [тег|данные] ... [тег|данные]
       Набор 1:  [тег|данные] [тег|данные] ... [тег|данные]
  -->  Набор K:  [тег|данные] [тег|данные] ... [тег|данные]
       ...            |
       индекс         v
       выбрал    тег совпал?  --да-->  hit: данные[смещение]
       набор K                --нет--> miss

Сколько линий помещается в набор — определяет, насколько остра будет конкуренция за позицию.

Ассоциативность: сколько линий в одном наборе

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

Кеш прямого отображения (direct-mapped, ассоциативность 1). В бакете ровно одна позиция, любая коллизия — немедленное вытеснение. Два адреса с одинаковым индексом не могут сосуществовать. Зато поиск предельно простой: один тег за такт. Расплата — катастрофа на неудачных паттернах. Если цикл чередует обращения к двум адресам с одинаковым индексом, hit rate падает до 0%: каждое обращение выбрасывает то, что понадобится следующему. Классический пример: два массива по 32 КБ, выровненные по 32 КБ, в direct-mapped кеше на 32 КБ элементы A[i] и B[i] всегда попадают в один набор и вытесняют друг друга.

Полностью ассоциативный кеш (fully associative). Другая крайность: один бакет на весь кеш, индексации нет — любая линия может занять любую позицию. Структурных коллизий не бывает вовсе. Цена — аппаратная: тег запроса сравнивается со всеми тегами одновременно. При 512 линиях это 512 параллельных сравнений за такт — железо такого объёма не масштабируется. Поэтому fully associative остаётся выбором только для маленьких специализированных структур на 64–128 записей.

Множественно-ассоциативный кеш (set-associative). Компромисс. Бакет фиксированного размера N — обычно 4, 8, 16 позиций. Биты адреса, как в direct-mapped, детерминированно указывают на один конкретный набор, но внутри набора линия свободно занимает любую из N позиций — как в крошечном fully associative. Поиск проверяет N тегов параллельно, это посильная нагрузка. Коллизия превращается в конфликтный промах только когда в один набор одновременно претендует N+1 разных адресов — на порядок реже, чем у direct-mapped. У современных L1 кешей ассоциативность обычно 8-way, у Intel P-ядер начиная с Ice Lake (2019) — 12-way.

Тип                    Конфликты        Цена
---------------------------------------------
Direct-mapped          Высокий          1 сравнение
N-way (обычно 8)       Низкий           N сравнений
Fully associative      Нет              Все линии

Разбор адреса: L1d 32 КБ, 8-way

Абстрактный разбор легче увидеть на конкретной конфигурации. Типичный Skylake: L1d = 32 КБ, 8-way, линия 64 байта. Общее количество линий: 32 КБ / 64 байта = 512. Количество наборов: 512 / 8 = 64.

|<------- тег (52 бита) ------->|<- индекс (6 бит) ->|<- смещение (6 бит) ->|
|                               |    0..63 (набор)   |   0..63 (байт)       |

Смещение: log2(64) = 6 бит. Индекс: log2(64) = 6 бит. Тег: остальные старшие биты адреса. На практике физический адрес у x86-64 уже 64 бит — конкретная ширина у каждого CPU своя (процессор сообщает её через CPUID.80000008H:EAX[7:0], типично 40–52 бита), — и тег получается на 12 бит меньше этой ширины.

Адреса записываются в шестнадцатеричной системе; каждая hex-цифра — 4 бита. Для адреса 0x...340 последние три цифры в двоичной записи — 0011 0100 0000. Младшие 6 бит — смещение, следующие 6 — индекс:

0x...340  ->  0011 0100 0000
              |---|-----|----|
              тег  инд  смещ
                   (6б) (6б)
 
смещение [5:0]  = 000000  = 0   -> нулевой байт линии
индекс   [11:6] = 001101  = 13  -> набор 13

Кеш мгновенно обращается к набору 13 и параллельно сравнивает тег запроса с тегами восьми линий. Совпал — hit, данные возвращаются за 4–5 тактов (полный цикл конвейера кеша, не задержка сверки тегов). Не совпал ни один — miss, запрос уходит в L2.

Восемь параллельных сравнений — это восемь аппаратных схем сравнения, работающих одновременно. Увеличение ассоциативности до 16 потребовало бы 16 таких схем — больше площади и потенциально более длинный критический путь. Поэтому 8-way — устоявшийся компромисс для L1.

Обращение к L1 само устроено как мини-конвейер: пока одна инструкция ожидает результат сверки тегов, следующая уже адресует набор. L1d поддерживает два чтения и одну запись за такт — при полной загрузке до 3 обращений одновременно, при условии, что все попадают.

Вытеснение: что удалить, когда набор полон

Когда в наборе заняты все 8 позиций и приходит промах, кеш должен выбрать жертву. Идеальная стратегия — убрать линию, которая не понадобится дольше всех (алгоритм Белади). Но он требует знания будущего, которого у аппаратуры нет.

LRU (Least Recently Used — наименее недавно использованная) — выбирает линию, к которой не обращались дольше всех. Для 8 линий точный LRU требует хранить полный порядок последних обращений — 8! возможных перестановок, то есть log2(40320) ≈ 15 бит метаданных на набор, и обновлять порядок при каждом попадании. Для L1 с тактовой задержкой меньше наносекунды это слишком дорого.

Pseudo-LRU (приближённый LRU) — аппроксимация, используемая в реальных процессорах. Для 8-way кеша хранится бинарное дерево из 7 бит на набор:

          [бит 0]
         /       \
     [бит 1]    [бит 2]
     /    \      /    \
  [б3]  [б4]  [б5]  [б6]
  / \   / \   / \   / \
 L0 L1 L2 L3 L4 L5 L6 L7     <-- 8 линий набора

Каждый бит указывает направление (0 = лево, 1 = право) к «наименее недавно использованной» стороне. При попадании в линию биты на пути к ней переключаются в противоположную сторону — «отталкивая» путь от только что использованной линии. При вытеснении дерево указывает путь к жертве за 3 шага (log2(8) = 3 бита из 7 определяют путь). Точность ниже, чем у настоящего LRU, разница в hit rate — 1–2%, но экономия существенная: 7 бит на набор вместо 15. Для 64 наборов L1 это 56 байт метаданных вместо 120, что критично, когда каждый квадратный микрометр на счету.

В L3 кешах, где наборы содержат 12–16 линий, Intel использует адаптивную замену (adaptive replacement) — вариацию, учитывающую и частоту, и давность обращений, адаптируясь к паттерну нагрузки.

Практическое следствие: если программа последовательно сканирует массив больше L3 (например, полный обход таблицы 1 ГБ), каждая новая линия вытесняет старую, и весь кеш «промывается» (cache thrashing). После скана L3 заполнен данными из конца массива, а все ранее кешированные горячие данные потеряны. Именно поэтому PostgreSQL использует стратегию clock-sweep вместо чистого LRU для своего буферного кеша: она устойчива к последовательным сканам. На уровне аппаратного кеша аналогичную проблему решает политика вставки (insertion policy): Intel, начиная с Ivy Bridge, не помещает новые линии сразу в MRU-позицию (Most Recently Used), а ставит их ближе к LRU-концу. Если линия используется повторно — она продвигается. Если нет — быстро вытесняется, не разрушая горячие данные.

Разделение L1: инструкции отдельно, данные отдельно

До сих пор L1 выглядел как единое хранилище. Но у процессора на каждом такте идут сразу два независимых потока обращений: стадия Fetch читает следующую инструкцию, стадия Execute читает или пишет данные. Если бы L1 был единым, Fetch и Execute конкурировали бы за один вход в кеш (каждый такой вход называется портом). Пришлось бы либо чередовать доступ (потеря половины пропускной способности), либо делать кеш с двумя портами, что удваивает площадь и потребление. Поэтому L1 разделён на два независимых кеша: L1i (instruction cache — кеш инструкций) и L1d (data cache — кеш данных). На типичном Intel Skylake: L1i = 32 КБ, L1d = 32 КБ, оба 8-way.

Разделение работает, потому что инструкции и данные редко пересекаются: программа не модифицирует свой собственный код в обычной ситуации. Самомодифицирующийся код — экзотика, и он крайне дорог: требует сброса L1i, что стоит десятки тактов.

Размер L1i не менее важен, чем L1d. Программы с большим количеством ветвлений и виртуальных вызовов (интерпретаторы, JVM, большие C++ проекты с шаблонами) могут испытывать промахи L1i: код не помещается в 32 КБ, и fetch стадия ждёт загрузки инструкций из L2. Это промах кеша инструкций — менее очевидная, но реальная проблема. JIT-компиляторы (JIT — Just-In-Time; примеры: V8, YJIT в Ruby) стараются генерировать компактный машинный код именно по этой причине.

L2 и L3 кеши — unified (объединённые): хранят и инструкции, и данные. На этих уровнях задержка уже достаточно велика (4–30 нс), чтобы один порт с арбитражем не создавал узкого места, а объединение позволяет гибко распределять объём между инструкциями и данными.

L1 — не единственная кеш-подобная структура внутри ядра. Помимо L1i и L1d, у каждого ядра есть TLB (Translation Lookaside Buffer — буфер трансляции адресов). Программа работает с виртуальными адресами, процессор на каждом обращении преобразует виртуальный в физический. TLB кеширует результаты этих трансляций — без него каждое обращение требовало бы нескольких дополнительных чтений из памяти. Промах TLB стоит 10–50 нс — сопоставимо с промахом кеша данных (подробнее — в виртуальной памяти).

При случайном доступе к массиву, занимающему тысячи страниц (страница — 4 КБ), промахи TLB добавляются поверх промахов кеша данных. При шаге больше 4096 байт каждое обращение попадает на новую страницу, промахи TLB накладываются на промахи кеша, и пропускная способность падает ещё в 1.3–1.5 раза (а в виртуализированных средах, где обход страниц гостя проходит ещё один уровень, — в 2–3 раза).

Inclusive vs exclusive: что копируется между уровнями

L1 разделён, L2 и L3 — объединённые. Между уровнями возникает вопрос: если линия есть в L1, должна ли копия оставаться в L2? От ответа зависит и эффективная ёмкость иерархии, и сложность поддержания согласованного состояния между ядрами.

Inclusive (включающий): L2 содержит копию всего, что есть в L1. L3 содержит копию всего, что есть в L2. Плюс: когда другое ядро проверяет, есть ли линия у соседа, достаточно проверить L3 — это упрощает протокол согласования данных между ядрами (когерентности, подробнее — в следующей заметке). Минус: эффективный объём L2 меньше на размер L1 (часть данных дублируется).

Exclusive (исключающий): линия хранится ровно на одном уровне. Вытеснение из L1 помещает линию в L2, а не удаляет. Плюс: суммарная ёмкость = L1 + L2 + L3 без дублирования. Минус: при промахе L1, если данные найдены в L2, их нужно переместить (swap): линия из L2 уходит в L1, а вытесненная из L1 — в L2. AMD (Zen 1–4) использует почти исключающую (mostly-exclusive) схему для L3: линии попадают туда преимущественно при вытеснении из L2, новые данные из памяти идут сразу в L2, минуя L3. Строгого исключения нет — разделяемые линии и выборки инструкций могут дублироваться.

NINE (Non-Inclusive Non-Exclusive) — гибрид, используемый в Intel начиная со Skylake-SP для серверных процессоров. L3 не гарантирует ни включения, ни исключения: линия может быть в L1 и не быть в L3. Согласованность данных между ядрами поддерживается дополнительной структурой — фильтром слежения (snoop filter), хранящим метаданные о том, какие ядра могут иметь копию. Это позволяет масштабировать L3 на десятки ядер без дублирования.

Политики записи: write-through/write-back и write-allocate

Всё сказанное выше про чтение. Запись устроена сложнее, потому что у неё два независимых вопроса. Первый: когда изменённые данные должны уйти в нижний уровень? Это выбор между write-through и write-back. Второй: что делать при промахе на запись — загружать ли линию в кеш или писать мимо него? Это выбор между write-allocate и no-write-allocate.

Write-through (сквозная запись): каждая запись в кеш одновременно записывается в следующий уровень (L2 или RAM). Данные всегда консистентны между уровнями, но каждая инструкция mov [addr], rax генерирует трафик к L2 — дорого.

Write-back (отложенная запись): запись изменяет только линию в кеше и помечает её dirty (грязная, изменённая). Грязная линия записывается в следующий уровень только при вытеснении. Это радикально уменьшает трафик: если программа пишет в одну ячейку 100 раз подряд (инкрементирует счётчик в цикле), только последнее значение уедет в L2 — при вытеснении линии. Все современные процессоры используют write-back для L1d.

При промахе на запись кеш обычно применяет write-allocate (запись с размещением): сначала загружает в кеш всю 64-байтную линию, содержащую нужный адрес, затем изменяет в ней нужные байты. Причина в том, что кеш хранит и вытесняет данные линиями целиком, тогда как store-инструкция меняет лишь часть линии, например 4–8 байт. Если создать линию в кеше без чтения старого содержимого, незатронутые байты останутся неизвестными: повторное чтение вернёт мусор, а при write-back этот мусор может ещё и уйти вниз по иерархии.

Альтернатива — no-write-allocate (запись мимо кеша): запись идёт напрямую в следующий уровень, без загрузки в кеш. Используется для потоковых записей (streaming stores), когда данные точно не будут перечитаны — заполнение большого буфера, который сразу отправляется по сети. На x86-64 для этого есть инструкции movntps/movntdq (non-temporal store — запись без временной локальности: процессор знает, что данные не будут перечитаны, и не загружает линию в кеш).

Для L1d стандартна комбинация write-back + write-allocate. У неё есть неочевидное следствие: обнуление большого массива через memset сначала вынужденно читает старую линию, а уже потом пишет нули. Если массив не помещается в кеш, это превращается в чтение из RAM для каждой линии, хотя программа собирается перезаписать её целиком. Для больших массивов memset со streaming stores может быть в 2 раза быстрее обычного. Glibc на x86-64 автоматически переключается на non-temporal stores для memset при размере, превышающем определённую долю L3.

Store buffer: запись не останавливает конвейер

Write-back + write-allocate означает, что на промахе на запись нужно сначала загрузить всю 64-байтную линию, и только потом записать в неё значение. Если каждая store-инструкция ждала бы завершения этой загрузки, конвейер простаивал бы на каждом mov [addr], rax.

Задержку скрывает store buffer (буфер записей) — отдельное аппаратное хранилище, куда store-инструкция помещает адрес и значение сразу после исполнения. Тот же буфер появляется во внеочерёдном исполнении: запись живёт в нём до коммита соответствующей записи ROB и, пока не коммитнута, остаётся обратимой при откате. Здесь важен другой эффект того же механизма: буфер позволяет конвейеру продолжать выполнение, пока запись в фоне добирается до L1d и, при промахе, ждёт write-allocate.

Store buffer в кеш-контексте работает так:

  store [addr] = value
         |
         v
  [ Store buffer (56 записей) ]
         |
         v
  Линия в L1d?  --да-->  обновить линию, пометить dirty
                --нет--> write-allocate: загрузить 64-Б линию,
                         затем обновить и пометить dirty
                              |
                         линию вытесняют?
                         --нет--> остается в L1d
                         --да---> write-back в следующий уровень
 
  * load по тому же адресу -> store-to-load forwarding
    (данные берутся из буфера, минуя кеш)

Инструкция записи помещает в буфер адрес и значение, после чего конвейер идёт дальше. Буфер «сливает» (drain) записи в L1d по мере освобождения портов кеша. Если следующая инструкция читает только что записанный адрес, данные берутся напрямую из store buffer (store-to-load forwarding — пересылка из записи в чтение), без обращения к кешу. Задержка L1d при чтении собственной только что записанной ячейки превращается в задержку комбинационной схемы — единицы тактов.

Буфер отделяет момент, когда инструкция записи считается выполненной для конвейера, от момента, когда изменённая линия действительно попадает в L1d и позже уезжает вниз по иерархии. Именно поэтому частые записи не стопорят фронтенд сразу. Но сам буфер имеет конечный размер — порядка 56 записей на современном Intel. Если программа генерирует записи быстрее, чем буфер сливает их в кеш (массовое заполнение массива с промахами), буфер переполняется и конвейер стопорится. Это ещё один механизм, через который промахи кеша замедляют не только чтение, но и запись.

Store buffer — канонический дом этого механизма. Во внеочерёдном исполнении он появляется для обсуждения необратимости записи до коммита; в когерентности — для обсуждения того, как скрывается задержка когерентного протокола. Внутренняя механика буфера (размер, drain, forwarding) — здесь.

Hardware prefetch: угадать следующий адрес

Запись скрыта буферизацией. Для чтения буферизовать нечего — данные нужны прямо сейчас. Поэтому процессор не просто реагирует на промахи, он пытается их предотвратить. Hardware prefetcher (аппаратный предвыборщик) отслеживает паттерн обращений к памяти и загружает линии до того, как программа их запросит.

Основной механизм — stride prefetch (предвыборка с шагом). Если процессор замечает последовательность обращений к адресам A, A+64, A+128 (шаг 64 = размер линии), он начинает загружать A+192, A+256 заранее. Это работает идеально для обхода массивов и полей структур. Intel описывает два уровня prefetcher’ов: один на уровне L1 — prefetcher следующей линии (L1 DCU prefetcher), другой — потоковый prefetcher уровня L2 (L2 streamer), способный загружать до 20 линий вперёд.

Prefetch работает в фоне: загруженные линии размещаются в кеше, не блокируя выполнение инструкций. Если предсказание верное — когда программа обратится к адресу, данные уже в L1/L2, промаха нет. Если предсказание ошибочное — линия просто займёт место в кеше и будет вытеснена позже. Цена ошибки — потраченная полоса пропускания и одна бесполезная линия в кеше, но не остановка конвейера.

Prefetch бессилен против случайного доступа (нет паттерна для обнаружения) и непрямого доступа arr[index[i]], где адрес зависит от значения, которое само должно быть загружено из памяти. Именно поэтому обход связного списка, где указатель next в каждом узле лежит по случайному адресу, не получает выгоды от prefetch и работает со скоростью промахов L3/RAM.

Программист может помочь prefetcher’у явно, через интринсик (intrinsic — встроенная функция компилятора, отображающаяся на конкретную инструкцию процессора). В C/C++ это __builtin_prefetch(addr), в Rust — core::arch::x86_64::_mm_prefetch. Смысл: программа знает, что через несколько итераций понадобится адрес X, и просит процессор начать загрузку заранее. Классический пример — обход хеш-таблицы: при обработке бакета N можно запросить prefetch бакета N+4, давая процессору 3–4 итерации (~100–200 нс) на загрузку. В реальных реализациях (SwissTable от Google, используемая в Abseil и Rust HashMap) software prefetch даёт 10–30% ускорения на больших таблицах, не помещающихся в L3.

Пропускная способность L1 и границы внутри ядра

Prefetch скрывает латентность одного обращения. Но когда поток обращений плотный, ограничением становится пропускная способность самого L1. L1d на современном Intel поддерживает два чтения и одну запись за такт. При частоте 3 ГГц и 32-байтной ширине шины это пик порядка 192 ГБ/с на ядро — только если конвейер полностью загружен чтениями и все они попадают. Реальные числа ниже: каждый промах в L2 (задержка 4–7 нс) в 10+ раз дольше локальной сверки тегов, и поток обращений периодически прерывается.

L2 отдаёт ~50–70 ГБ/с на ядро, L3 (общий) — ~150–300 ГБ/с суммарно. Это внутрипроцессорный потолок; для сравнения с RAM (~40–50 ГБ/с) и про memory-bound нагрузки — в иерархии памяти.

Когда один кеш перестаёт быть локальной историей

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

Sources

John L. Hennessy, David A. Patterson, 2017, Computer Architecture: A Quantitative Approach — 6th edition, Chapter 2
Intel, 2023, Intel 64 and IA-32 Architectures Optimization Reference Manual — Chapter 2: Intel Microarchitecture Code Name Skylake
Ulrich Drepper, 2007, What Every Programmer Should Know About Memory — Red Hat, Inc.
Maksim Panchenko, 2018, Accelerate large-scale applications with BOLT — front-end stalls в datacenter-нагрузках: https://engineering.fb.com/2018/06/19/data-infrastructure/accelerate-large-scale-applications-with-bolt/