Устройство кэша: строки и отображение

Урок раскрывает внутреннее устройство кэша: как адрес памяти превращается в место в кэше и как проверяется попадание.

Кэш-строка (cache line) — минимальный блок, который кэш загружает за раз (обычно 64 байта). Отображение — правило, по которому адрес памяти соответствует месту в кэше.

Зачем строки, а не отдельные байты

Кэш загружает не один запрошенный байт, а целую строку (блок) соседних байт — обычно 64. Это эксплуатирует пространственную локальность: раз вы обратились к байту, соседние скоро понадобятся, и они уже в кэше. Поэтому при промахе «дорого» идём в ОЗУ один раз, а получаем сразу 64 полезных байта.

Разбор адреса: тег, индекс, смещение

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

адрес памяти (например, 32 бита):
 ┌──────────────┬──────────┬───────────┐
 │     ТЕГ      │  ИНДЕКС  │ СМЕЩЕНИЕ   │
 └──────────────┴──────────┴───────────┘
   проверка       выбор      байт внутри
   совпадения     ячейки     строки

  смещение: log2(размер_строки) бит
  индекс:   log2(число_строк) бит
  тег:      остальное

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

Простейшая схема: каждый блок памяти может лечь только в одну ячейку кэша (индекс = адрес блока mod число ячеек). Быстро и просто, но есть беда: два часто используемых блока с одинаковым индексом «выбивают» друг друга — конфликтные промахи. Смоделируем кэш прямого отображения:

class DirectCache:
    def __init__(self, num_lines, line_size):
        self.num_lines = num_lines
        self.line_size = line_size
        self.tags = [None] * num_lines   # какой блок лежит в ячейке
        self.hits = self.misses = 0
    def access(self, addr):
        block = addr // self.line_size       # номер блока
        index = block % self.num_lines       # ячейка (прямое отображение)
        tag = block // self.num_lines        # тег
        if self.tags[index] == tag:
            self.hits += 1
            return "hit"
        else:
            self.misses += 1
            self.tags[index] = tag           # загружаем строку
            return "miss"

cache = DirectCache(num_lines=4, line_size=16)
addrs = [0, 4, 8, 64, 0, 4]    # 0 и 64 -> один и тот же индекс!
for a in addrs:
    print(f"адрес {a:>3}: {cache.access(a)}")
print(f"итого: попаданий {cache.hits}, промахов {cache.misses}")

Вывод:

адрес   0: miss
адрес   4: hit
адрес   8: hit
адрес  64: miss
адрес   0: miss
адрес   4: hit
итого: попаданий 3, промахов 3

Заметьте: адрес 64 выбил блок адреса 0 (у них общий индекс), поэтому повторное обращение к 0 снова промахнулось. Это конфликтный промах.

Как работает под капотом: ассоциативность

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

Тип	Куда может лечь блок	Компромисс
Прямое отображение	в одну ячейку	быстро, но много конфликтов
N-канальное ассоциативное	в любую из N ячеек набора	баланс (обычно 4–16 way)
Полностью ассоциативное	в любую ячейку	мало промахов, но дорого

Глубже в тему

Почему кэш оперирует строками по 64 байта, а не отдельными байтами? Ответ кроется в пространственной локальности и в природе обращения к ОЗУ. Поход в память дорог не столько из-за объёма данных, сколько из-за фиксированной задержки на «раскачку»: открыть строку DRAM, дождаться сигнала. Раз уж мы заплатили эту цену, выгодно забрать сразу целый блок соседних байт, а не один запрошенный, — ведь по принципу локальности соседи почти наверняка скоро понадобятся. Кроме того, передача блока подряд эффективнее (burst-режим памяти). Размер строки — это компромисс: слишком маленькая теряет выгоду локальности, слишком большая тратит память и пропускную способность на байты, которые могут не пригодиться, и усугубляет «ложное разделение» (false sharing) между ядрами. Шестьдесят четыре байта эмпирически оказались золотой серединой для большинства нагрузок.

Разбиение адреса на тег, индекс и смещение — это, по сути, аппаратная хеш-функция, и понять её логику важно. Смещение (младшие биты) указывает байт внутри строки и в выборе ячейки не участвует. Индекс (средние биты) прямо адресует набор кэша — он играет роль номера «корзины» в хеш-таблице. Тег (старшие биты) хранится в кэше рядом с данными и сравнивается при каждом обращении, чтобы убедиться: в выбранной ячейке лежит именно нужный блок, а не другой, попавший в тот же индекс. Почему индекс берут из средних, а не старших бит? Потому что соседние блоки памяти тогда попадают в разные наборы, распределяясь по кэшу равномерно; если бы индексом служили старшие биты, целые большие области памяти конкурировали бы за горстку наборов. Это тонкое, но важное проектное решение, напрямую влияющее на долю конфликтных промахов.

Конфликтные промахи в кэше прямого отображения — частая и коварная причина внезапного замедления программ, и стоит понять механизм. Поскольку каждый блок может лечь лишь в одну ячейку (индекс = адрес блока по модулю числа ячеек), два «горячих» блока с совпадающим индексом обречены постоянно выбивать друг друга, даже если остальной кэш пуст. Особенно болезненно это проявляется, когда шаг доступа к данным кратен размеру кэша: например, обход массива структур, где каждая структура ровно совпадает по размеру с шагом отображения, может приводить к тому, что все обращения бьются в один-два набора. Это объясняет загадочные провалы производительности на «круглых» размерах данных (степенях двойки), которые ловят профессиональные оптимизаторы.

Множественно-ассоциативный кэш — компромисс между двумя крайностями, и понимать его экономику полезно. В кэше прямого отображения сравнивается один тег — быстро и дёшево, но много конфликтов. В полностью ассоциативном блок может лечь в любую ячейку, конфликтов почти нет, но при каждом обращении приходится параллельно сравнивать теги всех ячеек — это дорого по схеме, энергии и задержке. N-канальный кэш берёт лучшее: блок может лечь в любую из N ячеек набора, значит, N конфликтующих блоков мирно уживаются рядом, а сравнивать нужно лишь N тегов. На практике L1 обычно делают 4–8-канальным (баланс скорости и попаданий), а более далёкие и медленные L2/L3 — более ассоциативными (8–16 каналов), потому что там критичнее снизить промахи, а лишний такт на сравнение тегов уже не так заметен на фоне большой задержки. Так ассоциативность становится ещё одной ручкой настройки в общем компромиссе скорости, площади и доли промахов.

Частые ошибки

Думать, что кэш хранит отдельные байты. Он оперирует строками (обычно 64 байта); один промах тянет всю строку.
Игнорировать конфликтные промахи. В прямом отображении два «горячих» блока с общим индексом постоянно выбивают друг друга.
Считать ассоциативность бесплатной. Больше каналов — больше параллельных сравнений тегов и сложнее схема.

Итог

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