Раздел 32 · Системное программирование: Zig, ассемблер, Verilog

Организация кэша

senior~120 мин

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

Организация кэша

В прошлом уроке ты увидел иерархию памяти как лестницу с пропастью между ступенями: регистр отвечает за такт, DRAM за две сотни тактов, SSD за десятки микросекунд. И увидел, за что программе прощают эту пропасть: за локальность. Сегодня мы разберём механизм, который превращает локальность в скорость. Кэш это не волшебная коробка, а очень простая машина из четырёх чисел: S наборов, E строк в наборе, B байт в блоке и m бит адреса. Из этих чисел следует всё: как адрес режется на тег, индекс и смещение, почему два массива могут выталкивать друг друга из кэша до бесконечности, что такое LRU и что происходит с байтом, который ты записал. В конце сверим теорию с настоящими процессорами: Core i7 из книги и Apple M4, на котором сняты все числа последних уроков.

Цели урока

Увидеть иерархию памяти как цепочку кэшей, где каждый уровень хранит блоки следующего, и различать три вида промахов: холодный, конфликтный и по ёмкости.
Выучить четыре параметра кэша (S, E, B, m) и выводить из них всё остальное: ёмкость, ширину тега, число строк.
Резать адрес на тег, индекс набора и смещение в блоке руками и кодом, и понимать, почему индекс берётся из средних бит, а не из старших.
Проиграть последовательность обращений через кэш прямого отображения, увидеть конфликтный промах на скалярном произведении и вылечить его сдвигом массива.
Написать симулятор с наборами, LRU-замещением и двумя политиками записи, и проверить его тестами.
Понимать, чем отличаются write-back и write-through, write-allocate и no-write-allocate, и какие сочетания выбирают настоящие L1 и L3.
Читать параметры кэшей своей машины из sysctl, lscpu и getconf, и сверять их с ограничением на размер пути L1.

Иерархия как цепочка кэшей

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

Уровень	Что хранит	Единица переноса	Кто управляет	Задержка, тактов
регистры	слова по 8 байт	слово	компилятор	0
TLB	трансляции адресов	одна запись	железо MMU	0
L1	блоки памяти	линия, 64 или 128 байт	железо	3 до 4
L2	блоки памяти	линия	железо	10 до 15
L3	блоки памяти	линия	железо	40 до 50
оперативная память	страницы диска	страница, 4 или 16 КБ	железо и ОС	200
буферный кэш ОС	куски файлов	страница	ОС	десятки тысяч
кэш браузера	страницы сайтов	файл	браузер	миллиарды

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

Промахи бывают трёх видов, и различать их важно, потому что лечатся они по-разному.

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

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

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

Цена промаха измеряется просто. Пусть попадание в L1 стоит один такт, а промах уводит на сто тактов в память. Тогда при 99 процентах попаданий среднее обращение стоит 1 + 0.01 × 100 = 2 такта, а при 97 процентах уже 1 + 0.03 × 100 = 4 такта. Два процента промахов удваивают время. Поэтому о кэше говорят не «доля попаданий», а «доля промахов»: она маленькая, и каждая её сотая ощутима.

Четыре числа: S, E, B, m

Всё устройство кэша процессора задаётся четырьмя числами. Адрес имеет ширину m бит, то есть адресов M = 2^m. Кэш это массив из S = 2^s наборов. В каждом наборе E строк. Каждая строка держит блок из B = 2^b байт, бит valid и тег из t = m − s − b бит. Ёмкость кэша считают только по данным: C = S × E × B, теги и биты valid в неё не входят.

Выпиши эту четвёрку и выведи из неё остальное: это первое, что нужно уметь, и это же первое упражнение книги. Заодно получим код, которым будем резать адреса.

//! Геометрия кэша: из (m, C, B, E) выводим S, t, s, b, и режем адреса.
const std = @import("std");

/// Кэш задан четвёркой: ширина адреса m, ёмкость C, блок B, строк в наборе E.
const Spec = struct { m: u7, c: u64, b: u64, e: u64 };

/// Что из неё выводится: наборов S, и сколько бит адреса уходит на тег,
/// индекс и смещение.
const Geometry = struct {
    sets: u64,
    tag_bits: u7,
    set_bits: u6,
    offset_bits: u6,
};

fn geometry(spec: Spec) Geometry {
    const sets = spec.c / (spec.b * spec.e);
    const set_bits: u6 = @intCast(std.math.log2_int(u64, sets));
    const offset_bits: u6 = @intCast(std.math.log2_int(u64, spec.b));
    return .{
        .sets = sets,
        .tag_bits = spec.m - set_bits - offset_bits,
        .set_bits = set_bits,
        .offset_bits = offset_bits,
    };
}

/// Три поля адреса по (s, b): старшие биты тег, средние индекс, младшие смещение.
const Parts = struct { tag: u64, set: u64, offset: u64 };

fn split(g: Geometry, addr: u64) Parts {
    const set_mask = (@as(u64, 1) << g.set_bits) - 1;
    const offset_mask = (@as(u64, 1) << g.offset_bits) - 1;
    return .{
        .tag = addr >> @intCast(@as(u7, g.set_bits) + g.offset_bits),
        .set = (addr >> g.offset_bits) & set_mask,
        .offset = addr & offset_mask,
    };
}

pub fn main(init: std.process.Init) !void {
    var buf: [1024]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    const rows = [_]Spec{
        .{ .m = 32, .c = 1024, .b = 4, .e = 1 },
        .{ .m = 32, .c = 1024, .b = 8, .e = 4 },
        .{ .m = 32, .c = 1024, .b = 32, .e = 32 },
    };
    try out.print("{s:>3} {s:>5} {s:>3} {s:>3} | {s:>4} {s:>3} {s:>3} {s:>3}\n", .{ "m", "C", "B", "E", "S", "t", "s", "b" });
    for (rows) |row| {
        const g = geometry(row);
        try out.print("{d:>3} {d:>5} {d:>3} {d:>3} | {d:>4} {d:>3} {d:>3} {d:>3}\n", .{
            row.m, row.c, row.b, row.e, g.sets, g.tag_bits, g.set_bits, g.offset_bits,
        });
    }

    // Кэш из упражнений книги: 13-битный адрес, 8 наборов по 2 строки, блок 4 байта.
    const book = geometry(.{ .m = 13, .c = 64, .b = 4, .e = 2 });
    try out.print("\n(m, C, B, E) = (13, 64, 4, 2): t = {d}, s = {d}, b = {d}\n", .{ book.tag_bits, book.set_bits, book.offset_bits });
    for ([_]u64{ 0x0e34, 0x0dd5, 0x1fe4 }) |addr| {
        const p = split(book, addr);
        try out.print("0x{x:0>4}: tag 0x{x:0>2}  set {d}  offset {d}\n", .{ addr, p.tag, p.set, p.offset });
    }
    try out.flush();
}

test "(32, 1024, 4, 1): 256 наборов, 22 бита тега" {
    try std.testing.expectEqual(Geometry{ .sets = 256, .tag_bits = 22, .set_bits = 8, .offset_bits = 2 }, geometry(.{ .m = 32, .c = 1024, .b = 4, .e = 1 }));
}

test "13-битный кэш книги: 0x0e34 это тег 0x71, набор 5, смещение 0" {
    const g = geometry(.{ .m = 13, .c = 64, .b = 4, .e = 2 });
    try std.testing.expectEqual(Parts{ .tag = 0x71, .set = 5, .offset = 0 }, split(g, 0x0e34));
}

$ zig run geometry.zig
  m     C   B   E |    S   t   s   b
 32  1024   4   1 |  256  22   8   2
 32  1024   8   4 |   32  24   5   3
 32  1024  32  32 |    1  27   0   5

(m, C, B, E) = (13, 64, 4, 2): t = 8, s = 3, b = 2
0x0e34: tag 0x71  set 5  offset 0
0x0dd5: tag 0x6e  set 5  offset 1
0x1fe4: tag 0xff  set 1  offset 0

Первые три строки таблицы это упражнение книги про геометрию, и у него есть смысл, кроме арифметики. Все три кэша одной ёмкости в килобайт, но устроены они по-разному. Первый: 256 наборов по одной строке, блок в одно слово. Второй: 32 набора по четыре строки. Третий: один набор из 32 строк, то есть любой блок может лечь в любую строку. Это три семейства кэшей, и дальше мы разберём их по очереди: прямое отображение (E = 1), множественно-ассоциативный кэш (1 < E < C/B) и полностью ассоциативный (S = 1).

Два инварианта держи в голове при любом расчёте. Сумма s + b + t всегда равна m. Ёмкость C = S × E × B, и если тебе дали C, B и E, то S выводится делением, а s это двоичный логарифм S. Зная только пару из (S, E, B), кэш восстановить нельзя.

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

Когда процессор просит слово по адресу A, кэш делает три шага. Первый: по средним s битам адреса находит набор. Второй: сравнивает старшие t бит адреса с тегами всех E строк набора, и ищет строку с совпавшим тегом и установленным битом valid. Третий: по младшим b битам достаёт нужное слово из блока. Промах это провал второго шага.

Почему именно средние биты идут в индекс, а не старшие? Представь кэш, в котором индексом набора служат старшие s бит. Тогда соседние блоки памяти, у которых старшие биты одинаковы, попадают в один и тот же набор. Целый непрерывный кусок памяти конкурирует за одну ячейку кэша, а остальные ячейки пустуют. Программа, которая идёт по массиву подряд, самая локальная из всех программ, получала бы в таком кэше промах на каждом блоке. Со средними битами соседние блоки ложатся в соседние наборы, и массив равномерно заполняет весь кэш.

Это упражнение книги можно и посчитать. Пусть кэш прямого отображения имеет параметры (S, E, B, m) = (512, 1, 32, 32) и, вопреки здравому смыслу, индексирует наборы старшими битами. Тегом тогда работают средние t = 32 − 9 − 5 = 18 бит, и подряд идущие блоки с одинаковыми старшими девятью битами отличаются только тегом. Сколько таких блоков подряд? 2^18, то есть 8 МБ памяти претендуют на один набор. А сколько блоков массива может лежать в таком кэше одновременно? Ровно один на набор, потому что E = 1. Массив в 8 МБ помещается в одну строку кэша, остальные 511 строк никогда не используются.

Поиграй с разбором адреса на виджете. Пресет «упражнение из книги» это тот же 13-битный кэш, что мы только что считали кодом: восемь наборов, блок в четыре байта, восемь бит тега. Меняй адрес и смотри, какие биты куда уходят. Пресеты L1d от Core i7 и от Apple M4 показывают, как выглядят те же поля на 48-битном адресе настоящего процессора.

Теперь снимок кэша, на котором книга задаёт целую серию вопросов. Наш кэш: адрес 13 бит, S = 8 наборов, E = 2 строки, B = 4 байта, тег 8 бит. В таблице для каждой строки бит valid, тег и четыре байта блока по смещениям 0, 1, 2, 3.

Набор	valid	тег	байт 0	байт 1	байт 2	байт 3	valid	тег	байт 0	байт 1	байт 2	байт 3
0	1	1A	40	41	42	43	0	00	·	·	·	·
1	1	2C	11	22	33	44	1	A9	55	66	77	88
2	0	3D	·	·	·	·	0	90	·	·	·	·
3	1	32	DE	AD	BE	EF	0	BC	·	·	·	·
4	1	5E	01	02	03	04	1	D1	F0	E1	D2	C3
5	1	71	9A	8B	7C	6D	0	6E	·	·	·	·
6	1	2F	AA	BB	CC	DD	1	F0	10	20	30	40
7	1	46	C0	FF	EE	00	0	DE	·	·	·	·

Задачка: где какие биты. Из тринадцати бит адреса младшие два (биты 1 и 0) это смещение, потому что b = 2. Следующие три (биты 4, 3, 2) это индекс набора, s = 3. Оставшиеся восемь (биты 12 до 5) это тег. Проверь: 2 + 3 + 8 = 13.

Задачка: чтение по адресу 0x0E34. Двоично это 0 1110 0011 0100. Смещение: биты 1 и 0 равны 00, то есть 0. Индекс: биты 4, 3, 2 равны 101, набор 5. Тег: оставшиеся 0111 0001, то есть 0x71. Смотрим набор 5: строка с тегом 0x71 есть и valid равен 1. Попадание, по смещению 0 отдаём байт 0x9A. Именно эти числа напечатала наша программа, сверь с выводом выше.

Задачка: чтение по адресу 0x0DD5. Смещение 1, набор 5, тег 0x6E. В наборе 5 строка с тегом 0x6E есть, но её бит valid сброшен. Строка не считается: промах, слово приедет из памяти.

Задачка: чтение по адресу 0x1FE4. Смещение 0, набор 1, тег 0xFF. В наборе 1 теги 0x2C и 0xA9. Промах.

Задачка: какие адреса попадают в набор 3. В наборе 3 одна годная строка с тегом 0x32. Адрес собирается обратно из полей: тег 0x32 сдвигаем на s + b = 5 бит, получаем 0x640, добавляем индекс 3, сдвинутый на 2, это 0xC, и любое смещение от 0 до 3. Попадут четыре адреса: 0x64C, 0x64D, 0x64E, 0x64F. Заметь, что всего адресов с индексом 3 намного больше: 2^8 тегов на 4 смещения, 1024 штуки, но в кэше прямо сейчас лежит один блок из 256 возможных.

Такое разложение адреса на три поля и есть код-задача урока. Там ещё будут крайние случаи, которых нет в примерах: s = 0, b = 0 и m = 64, когда тег занимает весь адрес.

Кэш прямого отображения

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

Возьмём кэш с рисунка из книги: m = 4, S = 4, E = 1, B = 2. Адрес из четырёх бит режется на тег (1 бит), индекс (2 бита), смещение (1 бит). Прогоним пять чтений подряд: адреса 0, 1, 7, 8, 0.

Обращение	Двоично	тег	набор	смещение	Исход	Что в наборе после
0	0000	0	0	0	промах, холодный	набор 0: блок с тегом 0, байты m[0], m[1]
1	0001	0	0	1	попадание	без изменений: слово m[1] уже здесь
7	0111	0	3	1	промах, холодный	набор 3: тег 0, байты m[6], m[7]
8	1000	1	0	0	промах, конфликтный	набор 0: тег 1, байты m[8], m[9]; блок 0 вытеснен
0	0000	0	0	0	промах, конфликтный	набор 0: снова тег 0; блок 8 вытеснен

Обращение к адресу 1 попадает, потому что блок в два байта принёс оба слова сразу: это пространственная локальность в действии. А вот адреса 0 и 8 воюют за один набор: у них одинаковый индекс 00 и разные теги. Пока кэш прямого отображения, они будут выталкивать друг друга сколько угодно раз, хотя наборы 1 и 2 пустуют. Это и есть конфликтный промах: места хватает, правило размещения не пускает.

Самый частый способ нарваться на него в настоящем коде это два массива, разложенных в памяти на расстоянии, кратном размеру кэша. Скалярное произведение из книги: x[8] и y[8] из f32, лежат подряд с адресов 0 и 32. Кэш прямого отображения на 32 байта данных с блоками по 16 байт, то есть два набора. Прогоним через наш симулятор (он написан ниже, в разделе про ассоциативность, здесь мы только пользуемся его read).

//! Скалярное произведение x[8] и y[8] через кэш из книги: 32 байта данных,
//! блок 16 байт. Массивы f32 лежат подряд: x с адреса 0, y с адреса 32.
const std = @import("std");
const cache = @import("cache.zig");

const Access = struct { name: []const u8, addr: u64 };

/// Обращения цикла `sum += x[i] * y[i]`: на каждой итерации x[i], потом y[i].
fn dotprodTrace(x_base: u64, y_base: u64) [16]Access {
    var out: [16]Access = undefined;
    for (0..8) |i| {
        out[2 * i] = .{ .name = "x", .addr = x_base + 4 * i };
        out[2 * i + 1] = .{ .name = "y", .addr = y_base + 4 * i };
    }
    return out;
}

fn play(out: *std.Io.Writer, title: []const u8, params: cache.Params, trace: []const Access) !void {
    var c = try cache.Cache.init(std.heap.page_allocator, params, .write_back);
    defer c.deinit(std.heap.page_allocator);
    try out.print("{s}\n", .{title});
    for (trace, 0..) |a, i| {
        const outcome = c.read(a.addr);
        if (i % 4 == 0) try out.writeAll("   ");
        try out.print("{s}[{d}] {s}  ", .{ a.name, i / 2, if (outcome == .hit) "hit " else "miss" });
        if (i % 4 == 3) try out.writeAll("\n");
    }
    try out.print("   {d} попаданий из {d}\n\n", .{ c.stats.hits, c.stats.accesses() });
}

pub fn main(init: std.process.Init) !void {
    var buf: [4096]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    const packed_arrays = dotprodTrace(0, 32);
    try play(out, "прямое отображение, S=2, B=16", .{ .s = 1, .e = 1, .b = 4 }, &packed_arrays);
    try play(out, "два пути, S=1, B=16", .{ .s = 0, .e = 2, .b = 4 }, &packed_arrays);

    // Та же прямая организация, но y сдвинут на 16 байт: x[12] вместо x[8].
    const padded = dotprodTrace(0, 48);
    try play(out, "прямое отображение, y с адреса 48", .{ .s = 1, .e = 1, .b = 4 }, &padded);
    try out.flush();
}

$ zig run dotprod.zig
прямое отображение, S=2, B=16
   x[0] miss  y[0] miss  x[1] miss  y[1] miss
   x[2] miss  y[2] miss  x[3] miss  y[3] miss
   x[4] miss  y[4] miss  x[5] miss  y[5] miss
   x[6] miss  y[6] miss  x[7] miss  y[7] miss
   0 попаданий из 16

два пути, S=1, B=16
   x[0] miss  y[0] miss  x[1] hit   y[1] hit
   x[2] hit   y[2] hit   x[3] hit   y[3] hit
   x[4] miss  y[4] miss  x[5] hit   y[5] hit
   x[6] hit   y[6] hit   x[7] hit   y[7] hit
   12 попаданий из 16

прямое отображение, y с адреса 48
   x[0] miss  y[0] miss  x[1] hit   y[1] hit
   x[2] hit   y[2] hit   x[3] hit   y[3] hit
   x[4] miss  y[4] miss  x[5] hit   y[5] hit
   x[6] hit   y[6] hit   x[7] hit   y[7] hit
   12 попаданий из 16

Первый прогон: ни одного попадания у самого локального цикла на свете. Разбери, почему. Блок x[0..3] (адреса 0 до 15) ложится в набор 0. Блок y[0..3] (адреса 32 до 47) тоже в набор 0, потому что 32 в двоичном это 10 0000, бит индекса (бит 4) равен нулю, а единица ушла в тег. x[0] приносит блок x, y[0] выталкивает его блоком y, x[1] возвращает x и выталкивает y, и так шестнадцать раз. Это называется пробуксовка, thrashing. Программа получает промах на каждом обращении, хотя рабочее множество, 64 байта, всего вдвое больше кэша, а по идее локальность должна давать 75 процентов попаданий.

Второй прогон: кэш той же ёмкости, но с двумя строками в единственном наборе. Оба блока лежат рядом, промахи только при переходе ко второй половине массивов. Это лечение ассоциативностью, и ниже мы его разберём. Третий прогон: кэш прямого отображения оставили как есть, но объявили x[12] вместо x[8], и y уехал на адрес 48. Теперь 48 это 11 0000, бит индекса равен единице, блоки x[0..3] и y[0..3] попали в разные наборы, и промахов ровно столько, сколько положено локальности: по одному на блок. Шестнадцать байт пустоты в памяти, четыре лишних f32, купили 12 попаданий из 16. Этот приём, набивка между массивами, живёт в настоящих библиотеках линейной алгебры до сих пор.

Задачка из книги: а если кэш больше? Возьми тот же цикл, но кэш на 32 байта с блоками по 16 байт заменён кэшем на 64 байта с теми же блоками, то есть S = 4. Проверь на бумаге, что пробуксовка исчезает: x[0..3] в набор 0, x[4..7] в набор 1, y[0..3] в набор 2, y[4..7] в набор 3, все четыре блока живут одновременно, четыре промаха на шестнадцать обращений. А теперь наоборот: кэш прямого отображения на 32 байта, но блок в 8 байт, S = 4. Адрес 32 это 10 0000, биты индекса 4 и 3 равны 00, набор 0, как и у адреса 0. Пробуксовка остаётся, и это упражнение книги показывает, что размер блока сам по себе конфликт не лечит: важно, куда падает граница между индексом и тегом.

Множественно-ассоциативный кэш и LRU

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

Цена этого удобства двойная. Во-первых, E компараторов тегов вместо одного, и они работают на каждом обращении, то есть жгут энергию. Во-вторых, появляется вопрос, которого не было у прямого отображения: если набор полон и нужно место, какую из E строк выселить? Это политика замещения. Варианты: случайная строка (дёшево, работает неожиданно неплохо), LFU (least frequently used, выселить ту, к которой обращались реже всех), LRU (least recently used, выселить ту, к которой дольше всех не обращались). LRU ближе всего к локальности: если к блоку давно не обращались, по временной локальности к нему, скорее всего, не обратятся и дальше.

Прежде чем писать, проиграй ту же последовательность 0, 1, 7, 8, 0 на трёх организациях одной ёмкости. В виджете кэш прямого отображения, кэш с двумя путями и полностью ассоциативный стоят рядом, и обращения проигрываются по шагу. Посмотри, на каком именно шаге у прямого отображения начинается конфликт и почему у двух путей последнее чтение попадает.

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

//! Симулятор кэша с параметрами (s, E, b): S = 2^s наборов, E строк в наборе,
//! B = 2^b байт в блоке. Замещение LRU, счётчики как в cachelab.
//!
//! Кэш хранит только теги и служебные биты, данных в нём нет: для подсчёта
//! попаданий и промахов содержимое блоков не нужно. Размер обращения тоже не
//! учитывается: считаем, что обращение не пересекает границу блока.
//!
//! Политика записи выбирается при создании:
//!   .write_back     запись остаётся в кэше (бит dirty), в память блок уходит
//!                   при вытеснении; промах записи выделяет строку (write-allocate);
//!   .write_through  запись сразу идёт в память, промах записи строку не
//!                   выделяет (no-write-allocate).
//! Счётчики `mem_reads` и `mem_writes` показывают, сколько раз кэш ходил в память.

const std = @import("std");

pub const Params = struct {
    /// Бит индекса набора: наборов 2^s.
    s: u6,
    /// Строк в наборе (ассоциативность).
    e: u32,
    /// Бит смещения в блоке: блок 2^b байт.
    b: u6,

    pub fn numSets(p: Params) u64 {
        return @as(u64, 1) << p.s;
    }

    pub fn blockBytes(p: Params) u64 {
        return @as(u64, 1) << p.b;
    }

    /// Ёмкость C = S * E * B байт.
    pub fn capacityBytes(p: Params) u64 {
        return p.numSets() * p.e * p.blockBytes();
    }
};

/// Адрес, разобранный на три поля: тег, индекс набора, смещение в блоке.
pub const Parts = struct {
    tag: u64,
    set: u64,
    offset: u64,
};

/// Старшие биты адреса это тег, средние s бит выбирают набор, младшие b бит
/// это смещение внутри блока.
pub fn split(p: Params, addr: u64) Parts {
    const set_mask = p.numSets() - 1;
    const offset_mask = p.blockBytes() - 1;
    return .{
        .tag = addr >> @intCast(@as(u7, p.s) + p.b),
        .set = (addr >> p.b) & set_mask,
        .offset = addr & offset_mask,
    };
}

pub const Outcome = enum {
    hit,
    miss,
    /// Промах, ради которого пришлось вытеснить занятую строку.
    evict,

    pub fn name(o: Outcome) []const u8 {
        return switch (o) {
            .hit => "hit",
            .miss => "miss",
            .evict => "miss eviction",
        };
    }
};

pub const WritePolicy = enum { write_back, write_through };

pub const Stats = struct {
    hits: u64 = 0,
    misses: u64 = 0,
    evictions: u64 = 0,
    /// Блоков прочитано из памяти (каждый промах с выделением строки).
    mem_reads: u64 = 0,
    /// Записей в память: блоков при write-back, слов при write-through.
    mem_writes: u64 = 0,

    pub fn accesses(st: Stats) u64 {
        return st.hits + st.misses;
    }

    pub fn missRate(st: Stats) f64 {
        if (st.accesses() == 0) return 0;
        return @as(f64, @floatFromInt(st.misses)) / @as(f64, @floatFromInt(st.accesses()));
    }
};

pub const Line = struct {
    valid: bool = false,
    dirty: bool = false,
    tag: u64 = 0,
    /// Показание часов кэша при последнем обращении, для LRU.
    last_used: u64 = 0,
};

pub const Cache = struct {
    params: Params,
    policy: WritePolicy,
    /// Все строки подряд: набор i занимает lines[i*E .. (i+1)*E].
    lines: []Line,
    /// Часы: растут на единицу с каждым обращением.
    clock: u64 = 0,
    stats: Stats = .{},

    pub fn init(gpa: std.mem.Allocator, params: Params, policy: WritePolicy) !Cache {
        const lines = try gpa.alloc(Line, params.numSets() * params.e);
        @memset(lines, .{});
        return .{ .params = params, .policy = policy, .lines = lines };
    }

    pub fn deinit(c: *Cache, gpa: std.mem.Allocator) void {
        gpa.free(c.lines);
        c.* = undefined;
    }

    /// Строки одного набора.
    pub fn set(c: *Cache, index: u64) []Line {
        const start = index * c.params.e;
        return c.lines[start .. start + c.params.e];
    }

    pub fn read(c: *Cache, addr: u64) Outcome {
        const parts = split(c.params, addr);
        if (c.lookup(parts)) |line| return c.hit(line);
        return c.fill(parts, false);
    }

    pub fn write(c: *Cache, addr: u64) Outcome {
        const parts = split(c.params, addr);
        if (c.lookup(parts)) |line| {
            const outcome = c.hit(line);
            switch (c.policy) {
                .write_back => line.dirty = true,
                .write_through => c.stats.mem_writes += 1,
            }
            return outcome;
        }
        switch (c.policy) {
            // Write-allocate: блок читается в кэш и меняется там.
            .write_back => return c.fill(parts, true),
            // No-write-allocate: слово уходит прямо в память, кэш не трогаем.
            .write_through => {
                c.clock += 1;
                c.stats.misses += 1;
                c.stats.mem_writes += 1;
                return .miss;
            },
        }
    }

    /// Сбрасывает грязные строки в память. Нужен, чтобы при write-back
    /// в `mem_writes` попали и те блоки, которые никто не успел вытеснить.
    pub fn flush(c: *Cache) void {
        for (c.lines) |*line| {
            if (line.valid and line.dirty) c.stats.mem_writes += 1;
            line.dirty = false;
        }
    }

    fn lookup(c: *Cache, parts: Parts) ?*Line {
        for (c.set(parts.set)) |*line| {
            if (line.valid and line.tag == parts.tag) return line;
        }
        return null;
    }

    fn hit(c: *Cache, line: *Line) Outcome {
        c.clock += 1;
        line.last_used = c.clock;
        c.stats.hits += 1;
        return .hit;
    }

    /// Промах: занять свободную строку или вытеснить ту, к которой дольше
    /// всех не обращались.
    fn fill(c: *Cache, parts: Parts, dirty: bool) Outcome {
        c.clock += 1;
        c.stats.misses += 1;
        c.stats.mem_reads += 1;

        const line = c.victim(parts.set);
        const evicted = line.valid;
        if (evicted) {
            c.stats.evictions += 1;
            if (line.dirty) c.stats.mem_writes += 1;
        }
        line.* = .{ .valid = true, .dirty = dirty, .tag = parts.tag, .last_used = c.clock };
        return if (evicted) .evict else .miss;
    }

    fn victim(c: *Cache, set_index: u64) *Line {
        const lines = c.set(set_index);
        var oldest = &lines[0];
        for (lines) |*line| {
            if (!line.valid) return line;
            if (line.last_used < oldest.last_used) oldest = line;
        }
        return oldest;
    }
};

test "разбор адреса: (s, E, b) = (4, 1, 4)" {
    const p: Params = .{ .s = 4, .e = 1, .b = 4 };
    try std.testing.expectEqual(Parts{ .tag = 0x1, .set = 0x1, .offset = 0x0 }, split(p, 0x110));
    try std.testing.expectEqual(Parts{ .tag = 0x0, .set = 0x2, .offset = 0x2 }, split(p, 0x22));
    try std.testing.expectEqual(@as(u64, 256), p.capacityBytes());
}

test "прямое отображение: конфликт двух адресов с одним индексом" {
    var c = try Cache.init(std.testing.allocator, .{ .s = 4, .e = 1, .b = 4 }, .write_back);
    defer c.deinit(std.testing.allocator);
    try std.testing.expectEqual(Outcome.miss, c.read(0x10));
    try std.testing.expectEqual(Outcome.hit, c.read(0x18));
    try std.testing.expectEqual(Outcome.evict, c.read(0x110));
    try std.testing.expectEqual(Outcome.evict, c.read(0x10));
    try std.testing.expectEqual(Stats{ .hits = 1, .misses = 3, .evictions = 2, .mem_reads = 3 }, c.stats);
}

test "LRU: вытесняется строка, к которой дольше всех не обращались" {
    var c = try Cache.init(std.testing.allocator, .{ .s = 0, .e = 2, .b = 4 }, .write_back);
    defer c.deinit(std.testing.allocator);
    _ = c.read(0x00); // A
    _ = c.read(0x10); // B
    _ = c.read(0x00); // A снова: теперь B старше
    try std.testing.expectEqual(Outcome.evict, c.read(0x20)); // C выталкивает B
    try std.testing.expectEqual(Outcome.hit, c.read(0x00));
    try std.testing.expectEqual(Outcome.evict, c.read(0x10));
}

test "write-through без выделения: промах записи не заводит строку" {
    var c = try Cache.init(std.testing.allocator, .{ .s = 1, .e = 1, .b = 4 }, .write_through);
    defer c.deinit(std.testing.allocator);
    try std.testing.expectEqual(Outcome.miss, c.write(0x10));
    try std.testing.expectEqual(Outcome.miss, c.read(0x10)); // строки всё ещё нет
    try std.testing.expectEqual(Outcome.hit, c.write(0x14)); // теперь есть, слово идёт и в кэш, и в память
    try std.testing.expectEqual(Stats{ .hits = 1, .misses = 2, .mem_reads = 1, .mem_writes = 2 }, c.stats);
}

test "write-back: грязный блок уходит в память один раз, при вытеснении или flush" {
    var c = try Cache.init(std.testing.allocator, .{ .s = 0, .e = 1, .b = 4 }, .write_back);
    defer c.deinit(std.testing.allocator);
    _ = c.write(0x00);
    _ = c.write(0x04);
    _ = c.write(0x08); // три записи в один блок, память их ещё не видела
    try std.testing.expectEqual(@as(u64, 0), c.stats.mem_writes);
    _ = c.read(0x10); // вытеснение: грязный блок записывается целиком
    try std.testing.expectEqual(@as(u64, 1), c.stats.mem_writes);
    c.flush(); // чистую строку flush не трогает
    try std.testing.expectEqual(@as(u64, 1), c.stats.mem_writes);
}

$ zig test cache.zig
1/5 cache.test.разбор адреса: (s, E, b) = (4, 1, 4)...OK
2/5 cache.test.прямое отображение: конфликт двух адресов с одним индексом...OK
3/5 cache.test.LRU: вытесняется строка, к которой дольше всех не обращались...OK
4/5 cache.test.write-through без выделения: промах записи не заводит строку...OK
5/5 cache.test.write-back: грязный блок уходит в память один раз, при вытеснении или flush...OK
All 5 tests passed.

Разбери три функции, в которых живёт вся логика.

lookup это второй шаг обращения: пройти по E строкам набора и найти ту, у которой тег совпал и valid стоит. В железе эти E сравнений делаются параллельно, в симуляторе циклом; результат тот же. Заметь: split не проверяет, что тег влезает в t бит, адреса у нас 64-битные, а тег это просто всё, что выше индекса. Код-задача устроена строже, там тег обрезается до m − s − b бит.

victim это политика замещения. Сначала ищем свободную строку: пока набор не полон, никого выселять не надо, и порядок строк в наборе не важен. Когда все строки заняты, выбираем ту, у которой last_used меньше всех. Один проход по набору решает обе задачи. Настоящее LRU для 8 или 16 путей в железе стоило бы дорого (нужно помнить полный порядок строк, это log2(E!) бит на набор), поэтому процессоры используют приближения: псевдо-LRU на дереве битов или несколько бит возраста. Для симулятора честное LRU удобнее, потому что оно детерминировано и его можно проверить на бумаге.

fill это промах. Часы тикают, счётчики растут, жертва выбирается, и если жертва была занята, это уже не просто промах, а промах с вытеснением. Разделение miss и evict в Outcome нам понадобится в следующем уроке, где симулятор сверяется с эталонными трассами cachelab: там вытеснения считаются отдельно.

Посмотри на тест про LRU. Набор из двух строк, читаем A, B, потом снова A. К моменту третьего чтения B самый старый, и когда приходит C, выселяют именно B, а не A, хотя A попал в кэш раньше. LRU смотрит на последнее обращение, а не на момент загрузки. Это и есть разница между «давно лежит» и «давно не нужен».

Полностью ассоциативный кэш это крайний случай: S = 1, единственный набор, E = C / B строк, любой блок в любую строку. Индекса нет, s = 0, весь адрес кроме смещения это тег. Конфликтных промахов не бывает по построению: пока рабочее множество меньше кэша, всё лежит одновременно. Но искать блок значит сравнивать тег со всеми строками кэша параллельно, и для больших кэшей это слишком много компараторов. Поэтому полностью ассоциативными делают только маленькие кэши, где важна каждая строка: TLB на несколько десятков записей, буферы предвыборки, кэш микроопераций. Наш симулятор с s = 0 и есть такой кэш: тест про LRU гоняет как раз его.

Общее правило про ассоциативность: чем больше E, тем меньше конфликтных промахов и пробуксовки, но тем дороже каждое обращение (компараторы, мультиплексор выбора строки, энергия) и тем сложнее замещение. Поэтому L1 обычно 8 путей, L2 8 до 16, а L3, где промах стоит похода в DRAM, 12 до 16. Ниже это видно на настоящих числах.

Политики записи

До сих пор мы только читали. Запись добавляет два решения, и у каждого по два варианта.

Первое: что делать, когда записываемое слово уже в кэше, то есть при попадании на запись. Write-back: изменить слово в кэше, поставить строке бит dirty и больше ничего не делать; в память блок уйдёт при вытеснении, целиком. Write-through: изменить слово в кэше и тут же отправить его в память. Write-through проще (нет бита dirty, память всегда правдива), write-back экономит шину: если в одно слово пишут сто раз подряд, память увидит одну запись блока вместо ста записей слова.

Второе: что делать при промахе на запись. Write-allocate: подтянуть блок из памяти в кэш и записать слово туда, как будто это чтение с последующим попаданием. No-write-allocate: отправить слово прямо в память, кэш не трогать. Первое ставит на то, что за записью придут другие обращения к тому же блоку (пространственная локальность), второе на то, что не придут.

Сочетания обычно такие: write-back идёт вместе с write-allocate, потому что оба рассчитывают на повторные обращения к блоку; write-through идёт с no-write-allocate, потому что раз слово всё равно уходит в память, тащить ради него блок незачем. Симулятор урока умеет ровно эти две пары, и вот они на двух сценариях. Кэш в одну строку, чтобы каждый новый блок вытеснял предыдущий.

//! Две политики записи на двух сценариях. Кэш в один набор и одну строку,
//! блок 16 байт: любой другой блок вытесняет текущий.
const std = @import("std");
const cache = @import("cache.zig");

const Scenario = struct { name: []const u8, run: *const fn (c: *cache.Cache) void };

/// Счётчик в цикле: одно слово переписывается много раз.
fn counter(c: *cache.Cache) void {
    for (0..8) |_| _ = c.write(0x100);
}

/// Заполнение буфера: каждое слово пишется один раз и больше не нужно.
fn fillBuffer(c: *cache.Cache) void {
    for (0..8) |i| _ = c.write(0x200 + 16 * i);
}

pub fn main(init: std.process.Init) !void {
    var buf: [2048]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    const out = &w.interface;

    const scenarios = [_]Scenario{
        .{ .name = "счётчик: 8 записей в одно слово", .run = counter },
        .{ .name = "буфер: 8 записей в 8 разных блоков", .run = fillBuffer },
    };
    const params: cache.Params = .{ .s = 0, .e = 1, .b = 4 };
    for (scenarios) |sc| {
        try out.print("{s}\n", .{sc.name});
        for ([_]cache.WritePolicy{ .write_back, .write_through }) |policy| {
            var c = try cache.Cache.init(std.heap.page_allocator, params, policy);
            defer c.deinit(std.heap.page_allocator);
            sc.run(&c);
            c.flush();
            try out.print("   {s:<14} попаданий {d}, промахов {d}, блоков из памяти {d}, записей в память {d}\n", .{
                @tagName(policy), c.stats.hits, c.stats.misses, c.stats.mem_reads, c.stats.mem_writes,
            });
        }
    }
    try out.flush();
}

$ zig run writes.zig
счётчик: 8 записей в одно слово
   write_back     попаданий 7, промахов 1, блоков из памяти 1, записей в память 1
   write_through  попаданий 0, промахов 8, блоков из памяти 0, записей в память 8
буфер: 8 записей в 8 разных блоков
   write_back     попаданий 0, промахов 8, блоков из памяти 8, записей в память 8
   write_through  попаданий 0, промахов 8, блоков из памяти 0, записей в память 8

Счётчик: write-back один раз читает блок, семь раз попадает и один раз пишет блок при flush. Два похода в память на восемь записей. Write-through без выделения не заводит строку вовсе (все восемь промахи, mem_reads равен нулю) и восемь раз пишет слово в память. Буфер, в который пишут один раз и забывают: у write-back восемь чтений блоков из памяти, которые никому не были нужны, плюс восемь записей грязных блоков; у write-through ровно восемь записей слов и ни одного лишнего чтения. На таком сценарии write-through выигрывает, и настоящие процессоры знают об этом: для потоковых записей есть отдельные инструкции, которые обходят кэш (non-temporal store), а x86 объединяет соседние записи в буфере до размера линии, чтобы не читать блок ради полной перезаписи.

Какую пару выбрать на каком уровне? Чем ниже уровень, тем дольше идёт транзакция к следующему и тем важнее их экономить, поэтому L2 и L3 почти всегда write-back с выделением. На L1 в разные годы делали по-разному: write-through в L1 упрощает когерентность между ядрами (L2 всегда знает актуальное значение), и так устроены некоторые процессоры AMD и ARM. Современные Intel и Apple держат write-back на всех уровнях. Для тебя как для программиста важна модель, которую предполагает книга и наш симулятор: write-back плюс write-allocate, запись ведёт себя как чтение с последующим изменением строки. Из этой модели следует правило: локальность записей окупается так же, как локальность чтений, и программа, которая пишет разбросанно, платит за каждую запись чтение блока.

Транспонирование под микроскопом

Соберём всё вместе на упражнении, где чтения и записи идут вперемешку. Транспонирование матрицы 2 на 2 из i32: src лежит с адреса 0, dst с адреса 16, кэш прямого отображения с блоками по 8 байт, write-back с выделением. Сначала кэш на 16 байт данных, то есть два набора, потом на 32 байта, четыре набора.

//! Транспонирование 2x2 через маленький кэш прямого отображения: src лежит
//! с адреса 0, dst с адреса 16, элементы i32, блок 8 байт. Сравниваем кэш
//! на 16 байт (два набора) и на 32 байта (четыре набора).
const std = @import("std");
const cache = @import("cache.zig");

const src_base: u64 = 0;
const dst_base: u64 = 16;

fn play(out: *std.Io.Writer, params: cache.Params) !void {
    var c = try cache.Cache.init(std.heap.page_allocator, params, .write_back);
    defer c.deinit(std.heap.page_allocator);
    try out.print("кэш {d} байт, блок {d}, наборов {d}\n", .{ params.capacityBytes(), params.blockBytes(), params.numSets() });
    for (0..2) |i| {
        for (0..2) |j| {
            // dst[j][i] = src[i][j]: сначала чтение, потом запись.
            const r = c.read(src_base + 4 * (2 * i + j));
            const w = c.write(dst_base + 4 * (2 * j + i));
            try out.print("   src[{d}][{d}] {s:<4}  dst[{d}][{d}] {s:<4}\n", .{
                i, j, if (r == .hit) "hit" else "miss", j, i, if (w == .hit) "hit" else "miss",
            });
        }
    }
    try out.print("   попаданий {d}, промахов {d}\n\n", .{ c.stats.hits, c.stats.misses });
}

pub fn main(init: std.process.Init) !void {
    var buf: [2048]u8 = undefined;
    var w = std.Io.File.stdout().writer(init.io, &buf);
    try play(&w.interface, .{ .s = 1, .e = 1, .b = 3 });
    try play(&w.interface, .{ .s = 2, .e = 1, .b = 3 });
    try w.interface.flush();
}

$ zig run transpose.zig
кэш 16 байт, блок 8, наборов 2
   src[0][0] miss  dst[0][0] miss
   src[0][1] miss  dst[1][0] miss
   src[1][0] miss  dst[0][1] miss
   src[1][1] hit   dst[1][1] miss
   попаданий 1, промахов 7

кэш 32 байт, блок 8, наборов 4
   src[0][0] miss  dst[0][0] miss
   src[0][1] hit   dst[1][0] miss
   src[1][0] miss  dst[0][1] hit
   src[1][1] hit   dst[1][1] hit
   попаданий 4, промахов 4

Пройди первый прогон руками, это стоит десяти минут. Блок в 8 байт это одна строка матрицы: src[0] занимает адреса 0 до 7, src[1] 8 до 15, dst[0] 16 до 23, dst[1] 24 до 31. Два набора, индекс это бит 3 адреса: src[0] и dst[0] в набор 0, src[1] и dst[1] в набор 1. Первая итерация: src[0][0] промах, блок src[0] в наборе 0; dst[0][0] промах, блок dst[0] вытесняет src[0] из набора 0. Вторая итерация: src[0][1] промах, потому что src[0] только что вытеснили; dst[1][0] промах, холодный, набор 1. Третья: src[1][0] промах, src[1] вытесняет dst[1] из набора 1; dst[0][1] промах, dst[0] вытесняет src[0] из набора 0. Четвёртая: src[1][1] попадание, единственное: src[1] ещё в наборе 1; dst[1][1] промах, dst[1] вытесняет src[1]. Семь промахов из восьми обращений при том, что все данные это четыре блока, а кэш вмещает два.

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

Настоящие иерархии: Core i7 и Apple M4

Книга описывает Core i7 поколения Haswell, и его числа стоит знать наизусть как эталон x86 последних десяти лет. Все три уровня используют линию в 64 байта.

Кэш	Что хранит	Ёмкость C	Путей E	Наборов S	Задержка, тактов
L1 i-cache	инструкции	32 КБ	8	64	4
L1 d-cache	данные	32 КБ	8	64	4
L2	инструкции и данные	256 КБ	8	512	11
L3	инструкции и данные, общий для ядер	8 МБ	16	8192	30 до 40

Первый уровень разделён на кэш инструкций и кэш данных: процессор выбирает инструкцию и читает данные на одном такте, и два кэша могут делать это параллельно, не мешая друг другу. К тому же кэш инструкций почти никогда не пишут, и его можно упростить. Дальше кэши объединённые: L2 держит и код, и данные одного ядра, L3 общий для всех ядер кристалла. Проверь геометрию через наш инструмент: L1d с C = 32 КБ, E = 8, B = 64 даёт S = 64, то есть s = 6, b = 6, и при 48-битном адресе тег занимает t = 36 бит. Эти же параметры зашиты в тест код-задачи для строк про L1, L2 и L3.

Есть одно скрытое ограничение, которое объясняет, почему L1 именно 32 КБ на 8 путей, а не, скажем, 64 КБ на 4. Процессор работает с виртуальными адресами, а кэш хранит физические блоки. Чтобы не ждать трансляцию адреса перед поиском в кэше, L1 индексируют битами, которые у виртуального и физического адреса совпадают: младшими 12 битами, смещением внутри страницы в 4 КБ. Значит s + b ≤ 12, и один путь кэша, S × B байт, не больше страницы. У Haswell 64 наборов по 64 байта это ровно 4 КБ на путь, 8 путей дают 32 КБ. Хочешь L1 побольше, добавляй пути, а не наборы. Это ограничение называют VIPT (virtually indexed, physically tagged), и мы вернёмся к нему в уроках про виртуальную память.

Теперь машина, на которой сняты все числа последних уроков. Apple M4 Max, macOS, sysctl.

$ sysctl -n machdep.cpu.brand_string
Apple M4 Max
$ sysctl hw.perflevel0 hw.perflevel1 hw.cachelinesize hw.l1dcachesize hw.l2cachesize
hw.perflevel0.physicalcpu: 12
hw.perflevel0.l1icachesize: 196608
hw.perflevel0.l1dcachesize: 131072
hw.perflevel0.l2cachesize: 16777216
hw.perflevel0.cpusperl2: 6
hw.perflevel0.name: Performance
hw.perflevel1.physicalcpu: 4
hw.perflevel1.l1icachesize: 131072
hw.perflevel1.l1dcachesize: 65536
hw.perflevel1.l2cachesize: 4194304
hw.perflevel1.cpusperl2: 4
hw.perflevel1.name: Efficiency
hw.cachelinesize: 128
hw.l1dcachesize: 65536
hw.l2cachesize: 4194304

Читай это так. В процессоре два вида ядер, и у каждого своя иерархия: perflevel0 это ядра производительности, perflevel1 ядра экономии. У ядра производительности L1d на 128 КБ и L1i на 192 КБ, вчетверо и вшестеро больше, чем у Haswell. Линия 128 байт, вдвое длиннее, чем у x86: пространственная локальность вознаграждается щедрее, но и ложное разделение между потоками (об этом через два урока) случается чаще. L2 общий на кластер: 16 МБ на шесть ядер производительности, 4 МБ на четыре ядра экономии, и он играет роль L3 из мира x86; отдельного L3 в привычном смысле нет, есть системный кэш перед памятью, который sysctl не показывает. Ключи без префикса, hw.l1dcachesize и hw.l2cachesize, показывают 64 КБ и 4 МБ: это ядра экономии, и на них легко обмануться, если не знать про perflevel. Именно поэтому обрыв на горе памяти, которую ты снимешь в уроке про гору памяти, лежит между 128 КБ и 256 КБ, а не около 64 КБ.

Ассоциативность Apple официально не публикует, но правило VIPT её выдаёт. Страница на macOS с Apple Silicon это 16 КБ, значит один путь L1d не больше 16 КБ, а 128 КБ делятся на 16 КБ ровно на восемь. Восемь путей по 16 КБ: S = 128 наборов по 128 байт, s = 7, b = 7, тег 34 бита при 48-битном адресе. Виджет разбора адреса содержит пресет L1d Apple M4 на 64 КБ, это число ядра экономии из hw.l1dcachesize; для ядра производительности поставь s = 7 руками и сравни, как сдвигается граница между индексом и тегом.

На Linux x86-64 те же числа отдают две команды. Форма вывода такая, числа на своей машине подставишь сам:

$ lscpu | grep -i cache
L1d cache:   <размер> (<число экземпляров>)
L1i cache:   <размер>
L2 cache:    <размер>
L3 cache:    <размер>
$ getconf -a | grep CACHE
LEVEL1_DCACHE_SIZE      <C в байтах>
LEVEL1_DCACHE_ASSOC     <E>
LEVEL1_DCACHE_LINESIZE  <B>
LEVEL2_CACHE_SIZE ...
LEVEL3_CACHE_SIZE ...

getconf даёт ровно тройку (C, E, B) на уровень, остальное считается нашей geometry. На lscpu смотри число экземпляров: L1 и L2 у x86 на ядро, L3 один на кристалл, и в скобках это видно.

Напоследок про то, как выбирать параметры, если бы проектировал ты. Больше C: меньше промахов по ёмкости, но выше время попадания, большой кэш физически дальше и медленнее. Больше B: лучше пространственная локальность окупается, но при том же C строк меньше, страдает временная локальность, и промах дороже, потому что блок длиннее. Больше E: меньше конфликтов, но дороже попадание и замещение. Настоящие иерархии это компромисс, и каждый уровень решает его по-своему: L1 маленький, быстрый, восемь путей; последний уровень большой, медленный, много путей, потому что промах на нём это поход в DRAM за две сотни тактов.

Практика

Задача этого урока это split и sizes для кэша, заданного четвёркой (s, e, b, m). Заготовка даёт три структуры: CacheParams с полями s, e, b и m, AddressParts с тегом, индексом и смещением, Sizes с числом наборов, числом строк во всём кэше, ёмкостью в байтах и шириной тега. Обе функции возвращают нули, тебе их заполнить.

Скрытые тесты проверяют: четырёхбитный кэш с рисунка на всех шестнадцати адресах (смещение это младший бит, набор два средних, тег старший, адреса 0 и 8 делят набор с разными тегами); 13-битный кэш из упражнений на трёх адресах, которые мы разобрали выше; L1, L2 и L3 Core i7 на 48-битных адресах и их ёмкости; и три крайних случая: s = 0 (набор всегда нулевой), b = 0 (смещения нет) и m = 64 с одним набором и однобайтовым блоком, когда тег занимает все 64 бита. Последний случай ловит сдвиг на 64, который в Zig не компилируется или паникует: std.math.shr принимает любой сдвиг и при сдвиге за ширину типа отдаёт ноль. И не забудь обрезать тег маской из m − s − b бит, а не из 64 − s − b: на тесте с m = 12 это разные числа.

Упражнения

CHK-1★

Заполни таблицу геометрии для шести кэшей с 32-битным адресом и ёмкостью 1024 байта: блок 4 байта при E = 1 и при E = 4; блок 8 байт при E = 1 и при E = 128; блок 32 байта при E = 1 и при E = 4. Для каждого выпиши S, t, s, b. Сначала на бумаге, потом добавь эти шесть строк в массив rows программы geometry.zig и сверь. Какой из шести кэшей полностью ассоциативный и почему у него s = 0?

CHK-2★★

Обратная задача: по части параметров восстанови остальные. Адрес 32 бита во всех трёх случаях. Первый кэш: C = 2048, S = 8, t = 25; найди B и E. Второй: C = 2048, E = 4, b = 3; найди S, s и t. Третий: C = 1024, E = 2, S = 16; найди B, b и t. Запиши, какие инварианты ты использовал в каждом случае, и добавь в geometry.zig функцию, которая принимает (m, C, S, t) и возвращает (B, E), с тестом на первый кэш.

CHK-3★★

По снимку 13-битного кэша из урока выпиши все адреса, чтение по которым попадёт в набор 1, и все адреса, которые попадут в набор 6. В каждом наборе две годные строки, значит по восемь адресов. Затем напиши тест: для каждого выписанного адреса split с параметрами (s, E, b) = (3, 2, 2) должен дать нужный набор и один из двух тегов. Отдельно объясни, почему адрес 0x1FE4 в набор 1 не попадает, хотя индекс у него подходящий.

CHK-4★★

Кэш с 12-битным адресом, четырьмя путями, блоком в 4 байта и ёмкостью 64 байта. Нарисуй, какие биты адреса уходят в тег, индекс и смещение, и разбери адреса 0x834, 0x836 и 0xFFD: набор, тег, смещение, и попадают ли 0x834 и 0x836 в один блок. Потом посчитай, сколько разных адресов и сколько разных блоков памяти отображаются на набор 2, и проверь это программой: пройди все 4096 адресов через split, посчитай адреса и разные теги на каждый набор, сверь с формулой через t и B.

CHK-5★★★

Симулятор урока связывает политику записи с политикой выделения: write-back всегда с выделением, write-through всегда без. Разведи их: добавь в Cache поле allocate: bool и реализуй все четыре сочетания. Прогони сценарии счётчика и буфера из writes.zig на всех четырёх и добавь третий сценарий: цикл, который пишет в массив из 64 слов, а потом читает его целиком. Составь таблицу «блоков из памяти, записей в память» и объясни, почему write-through с выделением почти никогда не встречается в железе, а write-back без выделения не встречается вовсе.

CHK-6★★

Сними параметры кэшей своей машины: sysctl hw.perflevel0 на macOS, getconf -a | grep CACHE и lscpu на Linux. Для каждого уровня выпиши C, E, B и посчитай S, s, b, t при 48-битном адресе. Проверь правило VIPT для L1d: S × B должно быть не больше размера страницы (getconf PAGESIZE или sysctl hw.pagesize). Если ассоциативность L1d система не показывает, выведи её из этого правила и объясни, почему ответ получается единственным.

Итоги

Кэш это любой уровень иерархии, хранящий копии блоков уровня ниже. Промахи бывают холодные (данных ещё не было), конфликтные (место есть, правило размещения не пускает) и по ёмкости (рабочее множество больше кэша). Два процента промахов могут удвоить среднее время обращения.
Четыре числа задают кэш: S = 2^s наборов, E строк в наборе, B = 2^b байт в блоке, m бит адреса. Ёмкость C = S × E × B, ширина тега t = m − s − b. Адрес режется на тег (старшие биты), индекс набора (средние s бит) и смещение (младшие b бит).
Индекс берётся из средних бит, чтобы соседние блоки памяти попадали в соседние наборы; со старшими битами целые мегабайты подряд конкурировали бы за одну строку.
Прямое отображение (E = 1) ищет одним сравнением, но даёт конфликтные промахи и пробуксовку: два массива на расстоянии, кратном размеру кэша, выталкивают друг друга при каждом обращении. Лечится ассоциативностью или набивкой между массивами.
Множественно-ассоциативный кэш сравнивает тег с E строками набора параллельно и выбирает жертву по LRU: вытесняется строка, к которой дольше всех не обращались, а не та, что раньше загружена. Полностью ассоциативный (S = 1) не знает конфликтов, но годится только для маленьких кэшей.
Write-back с выделением держит запись в кэше до вытеснения и превращает сто записей слова в одну запись блока; write-through без выделения проще и выигрывает на потоковой записи в одноразовый буфер. L2 и L3 всегда write-back; книга и наш симулятор считают, что запись ведёт себя как чтение с изменением строки.
Core i7 Haswell: L1 по 32 КБ на 8 путей (4 такта), L2 256 КБ (11 тактов), L3 8 МБ на 16 путей (30 до 40 тактов), линия 64 байта. Apple M4 Max: L1d 128 КБ и L1i 192 КБ на ядро производительности, линия 128 байт, L2 16 МБ на кластер из шести ядер; hw.l1dcachesize без perflevel0 показывает ядро экономии. Правило VIPT: один путь L1 не больше страницы.

Дальше

Симулятор из этого урока уже умеет всё, что нужно лабораторной cachelab: разбирать адрес, искать по набору, вытеснять по LRU, считать попадания, промахи и вытеснения. Не хватает входа: настоящей трассы обращений, снятой с настоящей программы. В следующем уроке мы допишем к нему парсер трасс в формате valgrind lackey, интерфейс командной строки с ключами -s, -E, -b, -t, сверим счётчики с эталонными трассами и снимем свои трассы с Zig-программы через генератор из прошлого урока. А потом кэш встанет на своё настоящее место: между процессором Y86 и его памятью, и CPI получит штраф за каждый промах.

домашка

Домашка

Сними параметры всех уровней кэша своей машины (sysctl на macOS, lscpu и getconf на Linux) и для каждого уровня посчитай s, b и t при 48-битном адресе. Проверь правило: размер одного пути L1d равен размеру страницы.S
Добавь в симулятор урока отдельный флаг выделения строки при промахе записи и сравни четыре сочетания политик на сценариях счётчика и буфера. Объясни, почему настоящие кэши почти всегда выбирают write-back с выделением.S
Для кэша с 12-битным адресом, четырьмя путями и блоком в 4 байта пройди все 4096 адресов через split и посчитай, сколько адресов и сколько разных блоков приходится на каждый набор. Сверь с формулой через t и B.S

Набор	valid	тег	байт 0	байт 1	байт 2	байт 3	valid	тег	байт 0	байт 1	байт 2	байт 3
0	1	1A	40	41	42	43	0	00	·	·	·	·
1	1	2C	11	22	33	44	1	A9	55	66	77	88
2	0	3D	·	·	·	·	0	90	·	·	·	·
3	1	32	DE	AD	BE	EF	0	BC	·	·	·	·
4	1	5E	01	02	03	04	1	D1	F0	E1	D2	C3
5	1	71	9A	8B	7C	6D	0	6E	·	·	·	·
6	1	2F	AA	BB	CC	DD	1	F0	10	20	30	40
7	1	46	C0	FF	EE	00	0	DE	·	·	·	·

Набор	valid	тег	байт 0	байт 1	байт 2	байт 3	valid	тег	байт 0	байт 1	байт 2	байт 3
0	1	1A	40	41	42	43	0	00	·	·	·	·
1	1	2C	11	22	33	44	1	A9	55	66	77	88
2	0	3D	·	·	·	·	0	90	·	·	·	·
3	1	32	DE	AD	BE	EF	0	BC	·	·	·	·
4	1	5E	01	02	03	04	1	D1	F0	E1	D2	C3
5	1	71	9A	8B	7C	6D	0	6E	·	·	·	·
6	1	2F	AA	BB	CC	DD	1	F0	10	20	30	40
7	1	46	C0	FF	EE	00	0	DE	·	·	·	·

Набор	valid	тег	байт 0	байт 1	байт 2	байт 3	valid	тег	байт 0	байт 1	байт 2	байт 3
0	1	1A	40	41	42	43	0	00	·	·	·	·
1	1	2C	11	22	33	44	1	A9	55	66	77	88
2	0	3D	·	·	·	·	0	90	·	·	·	·
3	1	32	DE	AD	BE	EF	0	BC	·	·	·	·
4	1	5E	01	02	03	04	1	D1	F0	E1	D2	C3
5	1	71	9A	8B	7C	6D	0	6E	·	·	·	·
6	1	2F	AA	BB	CC	DD	1	F0	10	20	30	40
7	1	46	C0	FF	EE	00	0	DE	·	·	·	·