Подсистема памяти: кэши, когерентность, контроллер

Всё, что разобрано в предыдущих главах — конвейер, внеочередное исполнение, предсказание переходов, — существует ради одной цели: не дать ядру простаивать. Простаивает же оно почти всегда по одной причине — ждёт данные. Промах до оперативной памяти на настольном или серверном ядре 2020-х стоит порядка 200–350 тактов; за это время широкое ядро могло бы завершить порядка тысячи микроопераций.

Во вводном треке уже объяснено, зачем нужна иерархия памяти и почему кэш помогает. Здесь мы разбираем механику: как физически устроен поиск в кэше, откуда берутся конфликтные промахи, что делает TLB, почему предвыборка иногда вредит, что происходит внутри микросхемы DRAM между запросом и ответом и почему у согласованности между ядрами есть измеримая цена.

Главный тезис главы стоит сформулировать сразу: подсистема памяти не «ускоряет доступ», она делает стоимость доступа зависящей от шаблона обращений. Один и тот же объём данных, обойденный двумя разными способами, различается по времени на порядок. Задача программиста — не «использовать кэш», а строить шаблоны, при которых он работает.

Стена памяти: как разошлись скорости

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

Это ключевая асимметрия всей темы:

• Пропускную способность можно купить — добавить каналов, поставить память ближе, расширить шину.
• Латентность купить нельзя — её можно только спрятать за полезной работой.

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

Локальность: единственная причина, по которой это работает

Кэш не обладает магией: он всего лишь маленькая быстрая память, куда кладут копию части большой медленной. Работает это только потому, что реальные программы обращаются к памяти неравномерно.

• Временная локальность. К одному адресу обращаются несколько раз за короткий промежуток. Пример: счётчик цикла, вершина стека, часто используемый объект.
• Пространственная локальность. После адреса A с большой вероятностью потребуется A+1. Пример: обход массива, чтение полей структуры, последовательность инструкций.

Пространственная локальность — причина, по которой единицей обмена служит не байт, а строка кэша: обычно 64 байта у ядер общего назначения (встречаются 32 и 128 у других классов устройств). Загрузив одну строку, кэш бесплатно получает соседние данные. Это же порождает и главный источник неожиданных потерь: если из 64 байт нужны 4, остальные 60 занимают место и пропускную способность впустую. Программа, читающая одно поле из большой структуры в цикле, тратит примерно в шестнадцать раз больше пропускной способности памяти, чем ей нужно.

Устройство кэша: адрес как три поля

Физически кэш — это две таблицы: массив данных (сами строки) и массив тегов (какие адреса в них лежат). Поиск устроен так, чтобы уложиться в единицы тактов, поэтому никакого перебора нет: адрес сам указывает, куда смотреть.

| ------------ тег ------------ | -- индекс -- | -- смещение -- |

смещение = log2(размер строки)                     — байт внутри строки
индекс   = log2(число множеств)                    — номер множества
тег      = всё остальное                           — что именно там лежит

число множеств = объём кэша / (размер строки × ассоциативность)

Пример для типичного L1d ядра общего назначения: 32 КиБ, 8 путей, строка 64 байта. Тогда множеств 32768 / (64 × 8) = 64, смещение 6 бит, индекс 6 бит. Адреса, отличающиеся на 4096 байт, имеют одинаковый индекс — и конкурируют за одни и те же 8 путей. Запомните это число, оно объясняет целый класс загадочных замедлений.

Ассоциативность и её цена

Прямое отображение (один путь): строка может лежать ровно в одном месте. Поиск максимально быстрый — один компаратор. Беда: два адреса с одинаковым индексом вытесняют друг друга даже при пустом кэше.

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

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

Практическое правило, известное как эмпирика «2:1»: кэш с прямым отображением объёмом 2N по числу промахов примерно эквивалентен двухпутевому объёмом N. Выигрыш от роста ассоциативности быстро насыщается: переход от 1 к 2 путям даёт много, от 8 к 16 — почти ничего, а задержку удлиняет. Поэтому у ядер общего назначения 2020-х ассоциативность L1 обычно единицы путей, L2 — порядка десятка, L3 — десяток и больше.

Классификация промахов: три «C» и четвёртая

Классическая таксономия (Марк Хилл, конец 1980-х) делит промахи на три вида, и лечатся они разным.

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

// Патологический случай: шаг ровно 4096 байт при 64 множествах и строке 64 байта
// означает, что ВСЕ обращения попадают в одно множество кэша.
for (size_t i = 0; i < n; i++)
    sum += matrix[i][0];              // строка матрицы = 4096 байт → конфликты

// Лечение: паддинг строки, чтобы шаг перестал быть степенью двойки
#define STRIDE (4096 + 64)            // сдвигаем индекс на одно множество

Политики: замещение, запись, включение

Замещение

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

Практические варианты:

• LRU — вытеснять давно не использованную. Хороша для циклических повторов, плоха для потокового обхода: линейный проход по данным, превышающим объём кэша, вытесняет всё полезное и сам ничего не получает.
• Псевдо-LRU — дерево бит-подсказок, приближение LRU за копейки. То, что реально стоит в железе при ассоциативности выше четырёх.
• RRIP и семейство — политики, которые пытаются различать «эта строка будет переиспользована скоро» и «эта пришла один раз и уйдёт». Вставляют новую строку не как самую свежую, а как кандидата на скорое выселение, повышая приоритет только при повторном обращении. Существенно устойчивее к потоковым нагрузкам.
• Случайная — на удивление неплохая при высокой ассоциативности и почти бесплатная.

Отсюда практический вывод: потоковая нагрузка, проходящая один раз по большому массиву, вредит соседям по кэшу. Именно поэтому существуют невременные (non-temporal) инструкции записи и чтения, которые говорят кэшу «не сохраняй это».

Запись

Две развилки, независимые друг от друга.

Сквозная (write-through) против обратной (write-back). При сквозной записи данные сразу уходят на следующий уровень; кэш всегда чист, когерентность проще, но трафик записи огромен. При обратной строка помечается «грязной» и выгружается только при выселении; трафик меньше в разы, но нужен буфер выселения и учёт грязных строк. Все внешние уровни у высокопроизводительных ядер работают на обратной записи.

С размещением (write-allocate) против без. При записи в отсутствующую строку либо сначала загружают её целиком, либо пишут мимо кэша. Первое — норма, потому что запись обычно часть чтения-модификации. Отсюда неочевидный эффект: чистая инициализация большого массива читает память, которую собирается перезаписать целиком, удваивая трафик. Лечится записью целыми строками с невременными инструкциями — приём, который заметно помогает при заполнении больших буферов.

Включение уровней

• Inclusive: всё, что есть в L1, есть и в L3. Упрощает когерентность (достаточно проверить L3, чтобы понять, есть ли строка у ядра), но тратит ёмкость на дубликаты и требует принудительного выселения из L1 при выселении из L3.
• Exclusive: строка лежит ровно на одном уровне. Полная ёмкость используется, но поиск сложнее.
• NINE (ни то ни другое) — компромисс, который на практике встречается чаще всего.

Выбор виден снаружи: при inclusive-иерархии выселение из общего L3 из-за активности соседнего ядра принудительно выбрасывает данные из вашего приватного L1. Это одна из причин, по которым производительность на многоядерной машине зависит от того, чем занят сосед.

Виртуальные адреса: TLB и почему страницы важны

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

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

Хитрость, которая позволяет не платить за трансляцию на каждом попадании в L1, называется VIPT (virtually indexed, physically tagged): индекс берут из младших битов, которые при трансляции не меняются (они внутри страницы), и поиск множества начинают параллельно с трансляцией. К моменту, когда физический адрес готов, теги уже прочитаны и остаётся их сравнить. Ограничение: индекс плюс смещение не должны выходить за пределы страницы, откуда жёсткая связь объём L1 ≤ размер страницы × ассоциативность. Это и есть настоящая причина, по которой L1 у ядер общего назначения десятилетиями держится в районе десятков килобайт: он упирается не в транзисторы, а в геометрию адреса.

Практические следствия:

• Большие страницы (2 МиБ вместо 4 КиБ) увеличивают покрытие TLB в сотни раз. Для нагрузок с большим случайным рабочим множеством — баз данных, графов, аналитики — это одна из самых дешёвых оптимизаций. Цена: более грубое управление памятью, риск внутренней фрагментации и задержек при дефрагментации, если система собирает их на лету.
• Промах TLB не виден в счётчике промахов кэша. Программа может показывать отличную статистику по кэшу и всё равно стоять — на трансляции. Смотреть надо отдельные счётчики dTLB-load-misses.
• Раскладка виртуального адресного пространства влияет на конфликты в физически индексируемых уровнях: одинаковое смещение внутри страницы у многих буферов даёт конфликты в L2 и L3.

Обработка промахов и параллелизм по памяти

Кэш высокопроизводительного ядра — неблокирующий: промах не останавливает обслуживание последующих обращений. Каждый незавершённый промах занимает запись в структуре MSHR (miss status holding register), где хранится адрес строки и список ожидающих её операций. Порядок числа MSHR у L1 ядер общего назначения — десяток-другой.

Отсюда важнейшее для практики понятие — параллелизм по памяти (MLP): сколько промахов ядро держит в полёте одновременно.

Из диаграммы видно главное правило, которое стоит держать в голове при проектировании структур данных:

• k независимых промахов обслуживаются одновременно и стоят примерно как один плюс небольшая надбавка на очереди;
• k зависимых промахов (когда адрес следующего известен только после прихода предыдущего) стоят ровно в k раз дороже.

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

Предвыборка: угадать раньше, чем понадобится

Предвыборка (prefetch) подтягивает строки до того, как к ним обратятся. Работает на двух уровнях.

Аппаратная. Блоки внутри ядра наблюдают за потоком адресов и продолжают замеченные закономерности:

• следующая строка — простейший вариант, подтягивает A+64;
• с постоянным шагом — обнаруживает арифметическую прогрессию адресов и продолжает её; отлично работает на обходе массивов и матриц;
• потоковая — держит несколько независимых последовательных потоков одновременно;
• по коррелированным шаблонам — более сложные схемы, пытающиеся запомнить нерегулярные, но повторяющиеся последовательности.

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

Программная. Инструкции-подсказки (__builtin_prefetch в GCC и Clang, _mm_prefetch в интринсиках x86) просят подтянуть строку заранее. Полезны там, где адрес известен, но закономерность не улавливается железом: обход хеш-таблицы с заранее вычисленными индексами, дерево с известными кандидатами, конвейерная обработка списка.

// Классический приём: подтягиваем узел, который понадобится через несколько итераций.
// Расстояние подбирается экспериментально: слишком мало — не успеет приехать,
// слишком много — вытеснится до использования.
#define PREFETCH_DISTANCE 8

for (size_t i = 0; i < n; i++) {
    if (i + PREFETCH_DISTANCE < n)
        __builtin_prefetch(&table[index[i + PREFETCH_DISTANCE]], 0, 1);
    sum += table[index[i]];
}

Когда предвыборка вредит, и это не редкость:

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

Когерентность: почему запись в общую строку не бесплатна

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

Базовое семейство протоколов — MESI и его расширения.

Расширения добавляют состояния для оптимизаций: O (Owned) позволяет держать изменённую строку и одновременно раздавать её копии, избегая записи в память; F (Forward) назначает одного из держателей ответственным за ответ, чтобы не отвечали все сразу.

Как протокол реализуется физически:

• Слежение (snooping) — все запросы транслируются всем, каждый кэш проверяет себя. Просто, но трафик растёт квадратично с числом ядер. Годится для единиц ядер.
• Каталог (directory) — отдельная структура хранит, у кого какая строка. Запросы адресуются точечно. Дороже по площади и добавляет обращение к каталогу, зато масштабируется. Все многоядерные кристаллы с десятками ядер используют каталог, часто совмещённый с общим кэшем последнего уровня, а ядра соединены кольцом или сеткой.

Из аппаратной механики немедленно следует ложное разделение (false sharing): два ядра пишут в разные переменные, случайно попавшие в одну строку кэша. Логически конфликта нет, физически строка мечется между ядрами, и каждое обращение стоит как передача между кэшами — порядок десятков тактов, что на порядок хуже попадания в L1.

// Плохо: счётчики соседних потоков в одной строке кэша
struct counters { long a; long b; };        // оба поля в одной 64-байтной строке

// Хорошо: каждый счётчик в своей строке
struct counters_padded {
    long a;
    char pad[64 - sizeof(long)];
    long b;
};
// Или через выравнивание, если стандарт языка это позволяет:
// alignas(64) в C++, #[repr(align(64))] в Rust

Правило простое: данные, которые пишут разные потоки, обязаны лежать в разных строках кэша; данные, которые все только читают, могут лежать вместе и это даже полезно.

Контроллер памяти и то, что внутри DRAM

Промах, дошедший до памяти, попадает не в «оперативную память» как в однородный массив, а в довольно сложное устройство.

Структура DRAM. Микросхема делится на банки, банк — это двумерный массив ячеек: строки и колонки. Чтобы прочитать данные, нужно:

1. Активировать строку — перенести целую строку (порядка килобайта) из массива ячеек в буфер строки. Операция разрушающая: заряд ячеек стекает в усилители считывания.
2. Прочитать колонку — выдать нужные байты из буфера строки. Быстро.
3. Закрыть строку (precharge) — записать содержимое буфера обратно в ячейки и подготовить массив к следующей активации.

Отсюда три сценария с разной ценой:

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

Планировщик контроллера. Контроллер не обслуживает запросы в порядке поступления. Он держит очередь и переставляет запросы так, чтобы максимизировать попадания в открытые строки — классическая политика называется FR-FCFS («сначала готовые, потом по очереди»). Плюс он обязан соблюдать десятки временных ограничений протокола, распределять запросы по банкам и каналам и периодически выполнять регенерацию (refresh): содержимое ячеек утекает, и каждую строку нужно перечитывать каждые десятки миллисекунд. Во время регенерации часть памяти недоступна, что даёт периодические всплески задержки.

Каналы, ранги, чередование. Пиковая пропускная способность считается как частота передачи × ширина шины × число каналов. Реальная достижимая — заметно меньше пиковой: порядок 60–80% на потоковой нагрузке и существенно меньше на случайной, потому что растёт доля конфликтов по строкам и переключений между чтением и записью (шина двунаправленная, смена направления стоит тактов). Адреса раскладываются по каналам и банкам чередованием, чтобы последовательный обход равномерно нагружал все каналы; отсюда очередной патологический случай — шаг обхода, кратный периоду чередования, попадает всё время в один канал.

Практические следствия для кода и для конфигурации:

• Последовательный обход быстрее случайного даже при одинаковом объёме — не только из-за строк кэша, но и из-за попаданий в буфер строки DRAM.
• Одноканальная конфигурация памяти на многоядерной машине — частая причина того, что добавление потоков не даёт прироста: все они делят один канал.
• NUMA: на многосокетной машине память чужого узла доступна, но дороже — порядок в полтора-два раза по латентности и заметно хуже по пропускной способности. Отсюда важность привязки потоков и памяти к одному узлу (Многоядерность).

Небольшая модель: считаем промахи сами

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

"""Модель множественно-ассоциативного кэша с политикой LRU.

Считает промахи для заданной последовательности адресов.
Сложность: O(n × A) по времени, где n — число обращений, A — ассоциативность
(поиск и обновление порядка внутри множества), и O(C / L) по памяти,
где C — объём кэша, L — размер строки.
"""
from collections import OrderedDict


class Cache:
    def __init__(self, size_bytes: int, line: int, ways: int):
        self.line = line
        self.ways = ways
        self.sets = size_bytes // (line * ways)
        assert self.sets > 0 and (self.sets & (self.sets - 1)) == 0, "число множеств — степень двойки"
        self.data = [OrderedDict() for _ in range(self.sets)]
        self.hits = 0
        self.misses = 0

    def access(self, addr: int) -> bool:
        line_addr = addr // self.line
        idx = line_addr % self.sets
        tag = line_addr // self.sets
        s = self.data[idx]
        if tag in s:
            s.move_to_end(tag)          # обновляем позицию LRU
            self.hits += 1
            return True
        if len(s) >= self.ways:
            s.popitem(last=False)       # выселяем самую давнюю
        s[tag] = True
        self.misses += 1
        return False


def обойти(шаг: int, объём: int, повторов: int, кэш: Cache) -> float:
    for _ in range(повторов):
        for a in range(0, объём, шаг):
            кэш.access(a)
    total = кэш.hits + кэш.misses
    return round(100.0 * кэш.misses / total, 1)


# L1d-подобный кэш: 32 КиБ, строка 64 байта, 8 путей → 64 множества
for шаг in (8, 64, 512, 4096):
    c = Cache(32 * 1024, 64, 8)
    доля = обойти(шаг, 1 << 20, 4, c)
    print(f"шаг {шаг:5} байт → промахов {доля:5}%")

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

Как измерить всё это на своей машине

# Что за иерархия под вами: размеры, ассоциативность, длина строки
lscpu --caches
getconf -a | grep -i cache
cat /sys/devices/system/cpu/cpu0/cache/index*/{level,type,size,ways_of_associativity,coherency_line_size}

# Топология и NUMA: какие ядра делят какой кэш, где какая память
lstopo-no-graphics --of console
numactl --hardware

# Промахи по уровням и по TLB — отдельно
perf stat -e L1-dcache-loads,L1-dcache-load-misses,LLC-loads,LLC-load-misses ./prog
perf stat -e dTLB-loads,dTLB-load-misses,iTLB-load-misses ./prog

# Где именно теряются такты: категория Memory Bound в методике Top-Down
perf stat -M TopdownL2 ./prog

# Кто именно промахивается: привязка промахов к строкам кода
perf record -e cache-misses -c 10000 ./prog && perf report

# Большие страницы: включены ли и сколько используется
cat /sys/kernel/mm/transparent_hugepage/enabled
grep -i huge /proc/meminfo

Отдельно стоит один раз измерить свою машину микробенчмарком с обходом указателей по массиву разного объёма: график «объём рабочего множества против латентности на обращение» показывает ступеньки на границах уровней кэша нагляднее любой документации. Готовые реализации есть в наборе lmbench и в тестах на 7-cpu.com.

Что это значит для кода

1. Раскладка данных важнее алгоритма чаще, чем кажется. Массив структур (AoS) против структуры массивов (SoA) — это не стилистика: если в цикле нужно одно поле из десяти, SoA даёт кратную экономию пропускной способности и открывает дорогу векторизации.

2. Блочная обработка (tiling) превращает ёмкостные промахи в попадания. Классический пример — умножение матриц: наивный тройной цикл имеет ту же асимптотику O(n³), что и блочный, но отличается по времени в разы, потому что блочный работает с подматрицами, помещающимися в кэш. Это самый наглядный случай, когда O(...) ничего не говорит о времени.

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

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

5. Разделяйте то, что пишут разные потоки. Ложное разделение — самая частая аппаратная причина того, что многопоточная версия медленнее однопоточной.

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

Типичные заблуждения

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

«У процессора 32 МиБ кэша, значит мои 20 МиБ данных поместятся». Общий кэш последнего уровня делится между всеми ядрами, а часто и между виртуальными машинами на одном хосте. Реально доступная вам доля намного меньше номинала и непостоянна.

«Промах кэша стоит 300 тактов, значит 1000 промахов стоят 300 000 тактов». Только если они зависимые. Независимые обслуживаются параллельно, и итог может отличаться на порядок.

«Больше ассоциативность — всегда лучше». Выигрыш насыщается быстро, а задержка и энергия растут. У L1 ассоциативность ограничена ещё и требованием VIPT.

«Предвыборка бесплатна». Она тратит пропускную способность и место в кэше. На нагрузке, упирающейся в пропускную способность памяти, лишняя предвыборка — прямое замедление.

«Выравнивание уже не важно, процессор умеет невыровненный доступ». Умеет, но обращение, пересекающее границу строки кэша, обслуживается как два, а пересекающее границу страницы — ещё и с двумя трансляциями.

«Память отдаёт данные с постоянной задержкой». Задержка зависит от состояния банка, от очереди в контроллере, от регенерации и от того, чем заняты соседние ядра.

Мини-итог

• Латентность памяти почти не улучшается десятилетиями; улучшается пропускная способность. Вся подсистема памяти существует, чтобы прятать латентность, а не устранять её.
• Кэш ищет по адресу, разобранному на тег, индекс и смещение. Индекс задан жёстко — отсюда конфликтные промахи и патологические шаги обхода, кратные степени двойки.
• Ассоциативность лечит конфликты, но её выигрыш быстро насыщается, а у L1 она ещё и ограничена схемой VIPT, которая и держит объём L1 в районе десятков килобайт.
• Промахи делятся на обязательные, ёмкостные, конфликтные и когерентные; каждый вид лечится своим средством, и путать их дорого.
• Политики записи и включения уровней объясняют неочевидные эффекты: удвоение трафика при инициализации массива, влияние соседнего ядра на содержимое вашего приватного кэша.
• TLB — отдельный кэш со своими промахами, невидимыми в статистике по данным; большие страницы часто дают больший выигрыш, чем любая правка кода.
• Неблокирующие кэши и MSHR дают параллелизм по памяти: независимые промахи почти бесплатны относительно друг друга, зависимые складываются полностью.
• Когерентность реализуется слежением или каталогом; её видимая программисту цена — ложное разделение и стоимость записи в общую строку.
• DRAM — не однородный массив: банки, строки, буфер строки, планировщик контроллера и регенерация делают стоимость обращения зависящей от истории обращений.

Источники

• U. Drepper. What Every Programmer Should Know About Memory, 2007 — PDF. Числа устарели, механика — нет; лучший связный текст по теме.
• J. Hennessy, D. Patterson. Computer Architecture: A Quantitative Approach — глава 2 и приложение B: количественный разбор иерархии памяти, классификация промахов, политики.
• M. Hill, A. Smith. Evaluating Associativity in CPU Caches. IEEE ToC, 1989 — источник классификации «три C» и эмпирики 2:1.
• A. Jaleel et al. High Performance Cache Replacement Using Re-Reference Interval Prediction (RRIP). ISCA, 2010 — doi.org/10.1145/1815961.1815971.
• V. Nagarajan, D. Sorin, M. Hill, D. Wood. A Primer on Memory Consistency and Cache Coherence, 2-е издание — doi.org/10.2200/S00962ED2V01Y201910CAC049: исчерпывающий разбор протоколов когерентности.
• B. Jacob, S. Ng, D. Wang. Memory Systems: Cache, DRAM, Disk — подробное устройство DRAM и контроллеров.
• S. Rixner et al. Memory Access Scheduling. ISCA, 2000 — doi.org/10.1145/339647.339668: откуда взялась политика FR-FCFS.
• 7-cpu.com — измеренные латентности кэшей и памяти по конкретным ядрам; полезно как образец того, как приводить такие числа.
• Документация ядра Linux по прозрачным большим страницам — kernel.org.

Что дальше

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

SIMD и векторные расширения: параллелизм внутри ядра