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

Модель современного процессора

lead~100 мин

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

Модель современного процессора

В прошлом уроке ты довёл свёртку до combine4: вызовы вынесены, аккумулятор живёт в регистре, и CPE упал с четырёх тактов до одного на сложении целых. Но на умножении дробных та же функция стоит 3.40 такта, а на сложении дробных 2.46, хотя в цикле всё те же четыре инструкции. Откуда эти числа? Сегодня мы откроем процессор, для которого писали код, и увидим, что у каждой операции есть три числа: задержка, интервал выпуска и ёмкость. Из них вырастут две границы CPE, а ассемблер цикла превратится в граф потока данных, где длина самого длинного пути и есть ответ. В конце возьмём префиксную сумму, у которой цепочка зависимостей проходит через память, и посмотрим, что с ней делает компилятор, а что процессор.

Цели урока

Назвать, чего не было в конвейере Y86 PIPE и что добавляет настоящее ядро: суперскалярность, внеочередное исполнение, переименование регистров, функциональные блоки с разными задержками, спекуляцию с откатом.
Понять устройство в две части: блок управления инструкциями и блок исполнения, и как между ними ходят операции с тегами вместо регистров.
Читать таблицу задержка, интервал выпуска и ёмкость для операции и выводить из неё границу задержки и границу пропускной способности.
Снять эти границы на своей машине двумя цепочками, зависимой и независимой, и понять, зачем в них пустой asm.
Превращать ассемблер цикла в граф потока данных: выбрасывать лишнее, находить регистры, унесённые в следующую итерацию, и находить критический путь.
Объяснить измеренный CPE combine4 для всех четырёх колонок как длину критического пути.
Разобрать префиксную сумму: почему цепочка через память длиннее цепочки через регистр, что из этого компилятор убирает сам, и какой ценой это остаётся у процессора.

Чего не было в Y86 PIPE

В уроке про PIPE и CPI мы закончили конвейер честным списком того, чего в нём нет. Сегодня этот список становится содержанием урока, поэтому пройдём по нему ещё раз, уже как по плану настоящего ядра.

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

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

Порядок исполнения равен порядку программы. PIPE исполнял инструкции строго по порядку, и любая зависимость, которую не закрыло продвижение, останавливала всё за ней. Настоящее ядро исполняет инструкции по мере готовности операндов, а порядок программы восстанавливает только на выходе.

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

Предсказание без спекуляции. PIPE предсказывал переход и при ошибке вставлял два пузырька. Настоящее ядро уходит по предсказанному пути на десятки инструкций вперёд, исполняет их, и при ошибке откатывает всё, что успело сделать.

Все пять пунктов не косметика. Они меняют вопрос, который ты задаёшь, глядя на цикл. Для PIPE вопрос был «сколько тактов занимает инструкция». Для настоящего ядра вопрос «какая цепочка зависимостей самая длинная», и весь урок это способ его задать правильно.

Две части ядра

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

Суперскалярный

процессор работает как две мастерские, соединённые очередью заказов.

Блок управления инструкциями читает инструкции из кэша инструкций, чаще всего далеко впереди того места, где программа исполняется сейчас. Читает по предсказанию: блок предсказания переходов решает, куда пойдёт условный переход, ещё до того, как известны флаги, и выборка идёт по этому пути. Декодер разбирает каждую инструкцию на одну или несколько элементарных операций. Инструкция addq %rax, 8(%rdx) это три операции: загрузить слово по адресу, сложить, сохранить обратно. Инструкция add x8, x9, x8 на aarch64 это одна операция. Операции уходят в очередь к блоку исполнения с указанием, откуда брать операнды и куда положить результат.

Блок исполнения принимает операции из очереди и раскладывает по функциональным блокам. У Haswell их восемь, и каждый умеет своё: два умеют читать из памяти, один сохранять данные, один считать адрес сохранения, четыре считать целые, и среди этих четырёх один умножает целые, один складывает дробные, два умножают дробные, два ветвятся. Операции запускаются, когда готовы их операнды и свободен блок, и это может быть далеко не в порядке программы. Такое исполнение называется

внеочередным

и без него ни один из приёмов следующих уроков не работал бы.

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

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

Ядра Apple M-серии устроены по той же схеме, только шире. По опубликованным замерам энтузиастов у ядра производительности восемь декодеров, около шести целочисленных блоков, четыре блока дробной и векторной арифметики, три загрузки и две записи за такт, и окно в несколько сотен инструкций, внутри которого ядро свободно переставляет операции. Из этого и вырастут числа 0.16 и 0.25 в таблице границ ниже.

Переименование регистров

Самый неочевидный из пяти пунктов, и самый важный для чтения графов. Возьми две итерации combine4 на aarch64:

ldr   d1, [x0], #8      ; итерация 1: d1 = data[i]
fmul  d0, d0, d1        ; итерация 1: acc = acc * d1
ldr   d1, [x0], #8      ; итерация 2: d1 = data[i+1]
fmul  d0, d0, d1        ; итерация 2: acc = acc * d1

В PIPE вторая загрузка обязана ждать, пока первое умножение прочитает d1: иначе она перезапишет операнд. Это ложная зависимость, через имя регистра, а не через значение. Настоящее ядро её не видит.

Переименование регистров

работает так. Когда декодер видит инструкцию, пишущую в d1, он выдаёт результату свежий тег, скажем t17, и записывает в таблицу: d1 сейчас это t17. Следующее за ней умножение читает таблицу и получает: «твои операнды это t16 (прошлое значение d0) и t17». Вторая загрузка снова пишет в d1 и получает уже t19. Второе умножение читает t18 и t19. Первое и второе значения d1 теперь разные теги, и ничто не мешает второй загрузке начаться раньше первого умножения. Что осталось: второе умножение ждёт результата первого, t18, потому что зависит от него по-настоящему.

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

У Haswell 168 физических целочисленных регистров и 168 дробных на 16 архитектурных имён каждого вида. У ядер Apple по опубликованным замерам порядка четырёхсот тех и других. Заканчиваются они редко, и в ближайших уроках мы упрёмся не в них.

Три числа на операцию

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

операция, Haswell	задержка	интервал выпуска	ёмкость
сложение целых	1	1	4
умножение целых	3	1	1
деление целых	3 до 30	3 до 30	1
сложение дробных	3	1	1
умножение дробных	5	1	2
деление дробных	3 до 15	3 до 15	1
загрузка	4	1	2
сохранение	1	1	1

Задержка это сколько тактов проходит от запуска операции до готовности результата. Следующая операция, которой нужен этот результат, раньше не начнётся.

Интервал выпуска

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

Ёмкость это сколько блоков умеют эту операцию. Сложение целых умеют четыре блока Haswell, умножение целых один, загрузку два.

Из трёх чисел выводятся две границы, между которыми обязан лежать CPE любого цикла.

Граница задержки. Если каждая операция цикла ждёт результата предыдущей, за элемент нельзя заплатить меньше, чем задержка операции. Для combine4 на умножении дробных это пять тактов на Haswell.

Граница пропускной способности. Если операции независимы, за такт можно запустить их столько, сколько блоков и сколько позволяет ширина выдачи. Ёмкость два при интервале один даёт 0.5 такта на операцию. Обратная величина пропускной способности и есть эта граница.

Книжная таблица границ для Haswell:

граница, Haswell	целое сложение	целое умножение	дробное сложение	дробное умножение
задержки	1.00	3.00	3.00	5.00
пропускной способности	0.50	1.00	1.00	0.50

Обрати внимание на 0.50 у целого сложения. Сумматоров четыре, а граница 0.50, а не 0.25: каждому элементу нужна загрузка, загрузчиков два, и цикл упирается в них, а не в сумматоры. Граница пропускной способности берётся по самому занятому блоку, и это не всегда блок самой операции.

Снимаем границы на своей машине

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

Первая ловушка в том, что компилятор сворачивает цепочку acc = acc + step из n шагов в одно умножение acc + n * step, и мерить становится нечего. Лечится пустым asm, который объявляет значение изменённым: после него компилятор обязан считать, что в регистре что-то новое.

//! Границы CPE: задержка и пропускная способность одной операции.
//!
//! Задержка меряется одной цепочкой зависимых операций: следующая ждёт
//! результата предыдущей, и время на операцию равно её задержке.
//! Пропускная способность меряется несколькими независимыми цепочками
//! сразу: их столько, что задержка закрыта, и упираемся уже в число
//! функциональных блоков и ширину выдачи.

const std = @import("std");
const builtin = @import("builtin");

pub const Op = enum { add, mul };

/// Пустой asm: после него компилятор считает значение неизвестным, и
/// цепочка `acc = blackBox(acc + step)` не сворачивается в `acc + n * step`.
pub inline fn blackBox(value: anytype) @TypeOf(value) {
    var v = value;
    switch (@typeInfo(@TypeOf(value))) {
        .float => switch (builtin.cpu.arch) {
            .aarch64 => asm volatile (""
                : [v] "+w" (v),
            ),
            .x86_64 => asm volatile (""
                : [v] "+x" (v),
            ),
            else => asm volatile (""
                : [v] "+r" (v),
            ),
        },
        else => asm volatile (""
            : [v] "+r" (v),
        ),
    }
    return v;
}

inline fn apply(comptime T: type, comptime op: Op, a: T, b: T) T {
    return switch (@typeInfo(T)) {
        .int => if (op == .add) a +% b else a *% b,
        else => if (op == .add) a + b else a * b,
    };
}

/// Второй операнд: для дробного умножения близкий к единице, чтобы значение
/// не убежало в бесконечность или в денормализованные числа, на которых
/// процессор заметно замедляется.
fn seed(comptime T: type, comptime op: Op) T {
    return switch (@typeInfo(T)) {
        .float => if (op == .mul) 1.0000001 else 1.5,
        else => if (op == .mul) 3 else 7,
    };
}

/// Сколько независимых цепочек гонять для пропускной способности.
/// Больше, чем задержка умножить на число блоков у любого ядра.
pub const chains = 16;

/// Одна цепочка из n операций: каждая ждёт предыдущую.
pub fn latency(comptime T: type, comptime op: Op, n: usize) T {
    var acc: T = blackBox(@as(T, 1));
    const step: T = blackBox(seed(T, op));
    var i: usize = 0;
    while (i < n) : (i += 1) {
        acc = blackBox(apply(T, op, acc, step));
    }
    return acc;
}

/// `chains` независимых цепочек, всего n операций.
pub fn throughput(comptime T: type, comptime op: Op, n: usize) T {
    var acc: [chains]T = undefined;
    inline for (0..chains) |j| acc[j] = blackBox(@as(T, 1));
    const step: T = blackBox(seed(T, op));
    var i: usize = 0;
    while (i + chains <= n) : (i += chains) {
        inline for (0..chains) |j| acc[j] = blackBox(apply(T, op, acc[j], step));
    }
    var total = acc[0];
    inline for (1..chains) |j| total = apply(T, op, total, acc[j]);
    return total;
}

test "цепочки считают то же, что и обычный цикл" {
    try std.testing.expectEqual(@as(i64, 1 + 7 * 100), latency(i64, .add, 100));
    try std.testing.expectEqual(@as(i64, chains + 7 * 160), throughput(i64, .add, 160));
}

Разберём blackBox. Ограничение "+r" говорит: значение v лежит в регистре, asm его читает и записывает. Тела у asm нет, регистр не меняется, но компилятор этого не знает и не имеет права ни сворачивать цепочку, ни переставлять операции через эту точку. Для дробных на aarch64 регистр векторный, ограничение "+w", на x86-64 "+x". Цена приёма нулевая: инструкций не добавляется, и по одному такту на сложение цепочка идёт ровно так, как шла бы без него.

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

Измеритель CPE из урока про границы компилятора здесь в сокращённом виде: калибровка частоты цепочкой сложений, минимум из семи прогонов на каждом размере, прямая по точкам.

//! Маленький измеритель CPE, общий для бенчей урока.
//! Частота калибруется цепочкой зависимых сложений (один такт на сложение),
//! для каждого n берётся минимум из серии прогонов, по точкам проводится прямая.

const std = @import("std");
const builtin = @import("builtin");

/// Пустой asm: после него компилятор считает значение неизвестным.
pub inline fn blackBox(value: anytype) @TypeOf(value) {
    var v = value;
    switch (@typeInfo(@TypeOf(value))) {
        .float => switch (builtin.cpu.arch) {
            .aarch64 => asm volatile (""
                : [v] "+w" (v),
            ),
            .x86_64 => asm volatile (""
                : [v] "+x" (v),
            ),
            else => asm volatile (""
                : [v] "+r" (v),
            ),
        },
        else => asm volatile (""
            : [v] "+r" (v),
        ),
    }
    return v;
}

fn now(io: std.Io) std.Io.Timestamp {
    return std.Io.Timestamp.now(io, .awake);
}

fn elapsedNs(io: std.Io, started: std.Io.Timestamp) f64 {
    return @floatFromInt(started.durationTo(now(io)).nanoseconds);
}

/// Короткая цепочка и много попыток: одна попытка укладывается в квант
/// планировщика, и минимум по попыткам не зависит от того, чем ещё занята
/// машина. Одна длинная цепочка, наоборот, ловит все переключения подряд.
const calibration_adds: usize = 4_000_000;
const calibration_attempts: usize = 40;

fn addChain(n: usize) u64 {
    var acc: u64 = 1;
    const step: u64 = blackBox(@as(u64, 7));
    var i: usize = 0;
    while (i < n) : (i += 1) acc = blackBox(acc +% step);
    return acc;
}

/// Частота ядра в гигагерцах: лучшая из калибровок.
pub fn calibrateGhz(io: std.Io) f64 {
    var best_ns: f64 = std.math.inf(f64);
    var attempt: usize = 0;
    while (attempt < calibration_attempts) : (attempt += 1) {
        const started = now(io);
        const result = addChain(calibration_adds);
        const ns = elapsedNs(io, started);
        std.mem.doNotOptimizeAway(result);
        best_ns = @min(best_ns, ns);
    }
    return @as(f64, @floatFromInt(calibration_adds)) / best_ns;
}

pub const sizes = [_]usize{ 256, 512, 1024, 2048, 4096, 8192 };

/// CPE функции `ctx.run(n)`: минимум из 7 прогонов на каждом n, наклон прямой.
pub fn measure(io: std.Io, ghz: f64, ctx: anytype) f64 {
    var xs: [sizes.len]f64 = undefined;
    var ys: [sizes.len]f64 = undefined;
    for (sizes, 0..) |n, k| {
        const reps = @max(1, 1_000_000 / n);
        var warm: usize = 0;
        while (warm < 2) : (warm += 1) repeat(ctx, n, reps);
        var best: f64 = std.math.inf(f64);
        var run: usize = 0;
        while (run < 7) : (run += 1) {
            const started = now(io);
            repeat(ctx, n, reps);
            best = @min(best, elapsedNs(io, started) / @as(f64, @floatFromInt(reps)));
        }
        xs[k] = @floatFromInt(n);
        ys[k] = best * ghz;
    }
    return slope(&xs, &ys);
}

fn repeat(ctx: anytype, n: usize, reps: usize) void {
    var rep: usize = 0;
    while (rep < reps) : (rep += 1) ctx.run(n);
}

/// Наклон прямой методом наименьших квадратов.
fn slope(xs: []const f64, ys: []const f64) f64 {
    const count: f64 = @floatFromInt(xs.len);
    var sx: f64 = 0;
    var sy: f64 = 0;
    var sxx: f64 = 0;
    var sxy: f64 = 0;
    for (xs, ys) |x, y| {
        sx += x;
        sy += y;
        sxx += x * x;
        sxy += x * y;
    }
    return (count * sxy - sx * sy) / (count * sxx - sx * sx);
}

И сам бенч, который печатает восемь чисел:

//! Снимает границы задержки и пропускной способности для четырёх колонок.
const std = @import("std");
const cpe = @import("cpe.zig");
const bounds = @import("bounds.zig");

fn Chain(comptime T: type, comptime op: bounds.Op, comptime kind: enum { latency, throughput }) type {
    return struct {
        pub fn run(_: @This(), n: usize) void {
            const result = if (kind == .latency) bounds.latency(T, op, n) else bounds.throughput(T, op, n);
            std.mem.doNotOptimizeAway(result);
        }
    };
}

pub fn main(init: std.process.Init) !void {
    const io = init.io;
    const ghz = cpe.calibrateGhz(io);
    var buf: [512]u8 = undefined;
    var stdout = std.Io.File.stdout().writer(io, &buf);
    const w = &stdout.interface;
    try w.print("частота ядра по калибровке: {d:.2} ГГц\n", .{ghz});
    try w.print("{s:<6} {s:>9} {s:>12}\n", .{ "опер.", "задержка", "пропускная" });
    inline for (.{ .{ i64, .add, "i64 +" }, .{ i64, .mul, "i64 *" }, .{ f64, .add, "f64 +" }, .{ f64, .mul, "f64 *" } }) |entry| {
        const T = entry[0];
        const lat = cpe.measure(io, ghz, Chain(T, entry[1], .latency){});
        const thr = cpe.measure(io, ghz, Chain(T, entry[1], .throughput){});
        try w.print("{s:<6} {d:9.2} {d:12.2}\n", .{ entry[2], lat, thr });
    }
    try w.flush();
}

Прогон на Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-13, машина в это время больше ничем не занята:

$ zig build-exe bounds_bench.zig -O ReleaseFast && ./bounds_bench
частота ядра по калибровке: 3.83 ГГц
опер. задержка пропускная
i64 +       1.02         0.16
i64 *       3.06         0.35
f64 +       2.63         0.27
f64 *       3.58         0.27

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

Числа, на которые дальше опираются уроки и виджет, сняты тем же способом полным измерителем эталона на Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-09:

граница, Apple M4 Max	`i64` сложение	`i64` умножение	`f64` сложение	`f64` умножение
задержки	1.00	2.99	2.49	3.42
пропускной способности	0.16	0.33	0.25	0.25

Сравни с Haswell. Задержки почти те же: сложение целых по-прежнему такт, умножение три. Дробные операции чуть короче: сложение около двух с половиной вместо трёх, умножение три с половиной вместо пяти. А пропускная способность выросла втрое и вчетверо: шесть сложений целых за такт вместо четырёх (0.16 это одна шестая), четыре дробных операции за такт вместо одной и двух. Расстояние между границами стало больше, и это главное, что изменилось за десять лет: у современного ядра простаивает больше блоков, и работа следующих уроков в том, чтобы их занять.

Дробные значения вроде 2.49 и 3.42 у задержек не ошибка измерения. Ядро может переключать частоту между калибровкой и замером, а сложение может занимать два такта в одном сочетании операндов и три в другом. Сотые ничего не значат, и в уроках мы округляем.

От ассемблера к графу потока данных

Теперь главный инструмент урока. Возьмём цикл combine4 и посмотрим, что из него сделал компилятор. Чтобы тело цикла было видно, функция помечена export: иначе LLVM встроит её в вызывающего и отдельного листинга не будет.

//! Циклы урока в виде export-функций: так их тело видно в ассемблере,
//! а не встраивается в вызывающего.

export fn combine4_fmul(data: [*]const f64, n: usize) f64 {
    var acc: f64 = 1.0;
    var i: usize = 0;
    while (i < n) : (i += 1) {
        acc = acc * data[i];
    }
    return acc;
}

export fn combine4_iadd(data: [*]const i64, n: usize) i64 {
    var acc: i64 = 0;
    var i: usize = 0;
    while (i < n) : (i += 1) {
        acc = acc +% data[i];
    }
    return acc;
}

export fn psum1(a: [*]const f64, p: [*]f64, n: usize) void {
    if (n == 0) return;
    p[0] = a[0];
    var i: usize = 1;
    while (i < n) : (i += 1) {
        p[i] = p[i - 1] + a[i];
    }
}

export fn psum1a(a: [*]const f64, p: [*]f64, n: usize) void {
    if (n == 0) return;
    var last = a[0];
    p[0] = last;
    var i: usize = 1;
    while (i < n) : (i += 1) {
        last = last + a[i];
        p[i] = last;
    }
}

$ zig build-obj loops_asm.zig -O ReleaseFast -femit-asm=loops_arm.s -fno-emit-bin -target aarch64-macos
$ zig build-obj loops_asm.zig -O ReleaseFast -femit-asm=loops_x86.s -fno-emit-bin -target x86_64-linux

На aarch64 цикл combine4_fmul это четыре инструкции, ровно как в книге:

LBB3_2:
	ldr   d1, [x0], #8      ; загрузить data[i], сдвинуть указатель
	fmul  d0, d0, d1        ; acc = acc * data[i]
	subs  x1, x1, #1        ; n -= 1, выставить флаги
	b.ne  LBB3_2            ; пока n не ноль

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

Под x86-64 тот же цикл выглядит иначе: LLVM развернул его на восемь элементов.

.LBB3_5:
	mulsd   xmm0, qword ptr [rdi + 8*rcx]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 8]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 16]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 24]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 32]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 40]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 48]
	mulsd   xmm0, qword ptr [rdi + 8*rcx + 56]
	add     rcx, 8
	cmp     rsi, rcx
	jne     .LBB3_5

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

Граф строится в три шага, и удобнее всего делать их на aarch64-версии, где инструкций четыре.

Шаг первый: инструкции превращаются в операции. Инструкция с обращением к памяти разбивается: ldr d1, [x0], #8 это загрузка по адресу x0 плюс сложение x0 + 8. subs это вычитание, оно же сравнение, а b.ne это переход по флагам. У combine4 получается пять операций: load, fmul, add (для указателя), cmp (для счётчика) и jne. В книжной версии на x86-64 то же самое: vmulsd (%rdx), %xmm0, %xmm0 это load плюс mul, addq $8, %rdx это add, cmpq и jne сами по себе.

Шаг второй: рёбра. Ребро идёт от операции к операции, если вторая читает результат первой. load отдаёт значение в fmul. fmul отдаёт acc, но кому? Никому в этой итерации: следующее чтение acc будет в fmul следующей итерации. Значит, ребро уходит вниз, к копии графа для следующей итерации. Такие рёбра несут регистры, которые цикл тащит с собой: аккумулятор, указатель, счётчик. Ребро add идёт к load следующей итерации (новый адрес) и к самому add следующей итерации. cmp отдаёт флаги в jne, и на этом ветка обрывается: результат jne никому не нужен, это только выбор адреса выборки, а выборка идёт по предсказанию и в поток данных не входит.

Шаг третий: выбросить лишнее. Операции, результат которых не тянется в следующую итерацию, не влияют на длину цепочки при достаточно большом числе итераций. cmp и jne уходят. Остаются две цепочки: fmul за fmul, через acc, и add за add, через указатель, к которой каждую итерацию цепляется load.

Теперь разверни граф на k итераций и найди критический путь. У combine4 на умножении дробных это цепочка из k умножений по 3.42 такта на M4 плюс одна загрузка в начале. Цепочка указателей идёт параллельно и стоит по одному такту, она короче и на CPE не влияет. Делим на k элементов, и при большом k получаем 3.42 такта на элемент. Измерено 3.40. Для сложения целых цепочка аккумулятора стоит по такту, цепочка указателя тоже по такту, они равной длины, и CPE выходит 1.00. Измерено 1.06.

Виджет: граф, путь и две границы

Ниже граф для шести циклов, и четыре из них ты ещё не видел: они появятся в следующем уроке. Пока держись combine4 и psum1. Переключи операцию, чтобы увидеть, как одна и та же форма графа даёт разный CPE, и переключи машину с Haswell на M4, чтобы увидеть, что форма не зависит от процессора, а числа зависят.

Что попробовать.

Поставь одну итерацию и посмотри на путь: загрузка плюс операция. Поставь шесть: загрузка одна, операций шесть. Граница задержки считается как прирост пути от ещё одной итерации, поэтому первая загрузка в неё не входит.
Возьми combine4 на сложении целых для Haswell. Граница задержки 1.00, граница пропускной способности 0.50, и упирается она в загрузки, а не в сумматоры. Для M4 та же граница 0.33 и тоже по загрузкам: три загрузчика на три загрузки.
Переключи на psum1. Критический путь идёт через store и load следующей итерации, и это самый длинный путь из всех шести циклов. Что это значит, разберём ниже.

Подпись «измерено» под предсказанием берётся из замеров эталона на M4 Max и есть только у версий combine. Для Haswell измерений у нас нет, но книжные числа с ним сходятся: 1.00, 3.00, 3.00 и 5.00 для combine4.

Критический путь как нижняя граница

Соберём вместе предсказание и измерение для combine4 на M4 Max.

`combine4`, M4 Max	`i64` сложение	`i64` умножение	`f64` сложение	`f64` умножение
граница задержки	1.00	2.99	2.49	3.42
измерено	1.06	2.99	2.46	3.40
граница пропускной способности	0.16	0.33	0.25	0.25

Во всех четырёх колонках combine4 лежит на границе задержки. Не потому, что ядру не хватает блоков: у M4 шесть сумматоров, а цикл использует один. Потому что в графе есть цепочка acc за acc, и по ней операции обязаны идти друг за другом. Пока цепочка одна, число блоков не имеет значения, и вся ширина ядра простаивает.

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

Задачка на эту мысль, вместо книжного упражнения про отделение операций. Цикл делает три вещи: складывает элемент в acc, умножает тот же элемент на константу и складывает в acc2, и сдвигает указатель. Какой у него CPE на M4 при дробных acc и acc2? Ответ: цепочек две, и обе из сложений. В первой acc за acc. Во второй тоже только сложение: умножение берёт элемент и константу, от прошлой итерации не зависит и в цепочку не входит. Обе цепочки по 2.49 на элемент, CPE 2.49. Умножение бесплатно, оно идёт параллельно. Проверишь это в упражнении.

Префиксная сумма и цепочка через память

Книга открывает главу о производительности префиксной суммой, и мы вернёмся к ней сейчас, когда есть чем её объяснить. Задача: по массиву a построить массив p, где p[i] это сумма a[0] до a[i]. Три версии.

//! Префиксная сумма: p[i] = p[i-1] + a[i].
//! Три версии считают одно и то же, но у них разный критический путь.

const std = @import("std");

inline fn add(comptime T: type, a: T, b: T) T {
    return if (@typeInfo(T) == .int) a +% b else a + b;
}

/// Версия 1: каждый шаг читает предыдущую сумму из памяти, из p[i-1].
/// p и a могут перекрываться, поэтому компилятор обязан читать честно.
pub fn psum1(comptime T: type, a: []const T, p: []T) void {
    if (a.len == 0) return;
    p[0] = a[0];
    var i: usize = 1;
    while (i < a.len) : (i += 1) {
        p[i] = add(T, p[i - 1], a[i]);
    }
}

/// Версия 2: развёртка 2 к 1, последняя сумма живёт в регистре last.
pub fn psum2(comptime T: type, a: []const T, p: []T) void {
    if (a.len == 0) return;
    var last = a[0];
    p[0] = last;
    var i: usize = 1;
    while (i + 1 < a.len) : (i += 2) {
        const first = add(T, last, a[i]);
        p[i] = first;
        last = add(T, first, a[i + 1]);
        p[i + 1] = last;
    }
    while (i < a.len) : (i += 1) {
        last = add(T, last, a[i]);
        p[i] = last;
    }
}

/// Версия 1a: аккумулятор в регистре, но без развёртки.
pub fn psum1a(comptime T: type, a: []const T, p: []T) void {
    if (a.len == 0) return;
    var last = a[0];
    p[0] = last;
    var i: usize = 1;
    while (i < a.len) : (i += 1) {
        last = add(T, last, a[i]);
        p[i] = last;
    }
}

/// Эталон для тестов: наивно и без оптимизаций.
pub fn reference(comptime T: type, a: []const T, p: []T) void {
    var acc: T = 0;
    for (a, p) |x, *out| {
        acc = add(T, acc, x);
        out.* = acc;
    }
}

test "три версии совпадают с эталоном на целых" {
    var a: [11]i64 = undefined;
    for (&a, 0..) |*x, i| x.* = @as(i64, @intCast(i)) * 3 - 7;
    var expected: [11]i64 = undefined;
    reference(i64, &a, &expected);

    var p: [11]i64 = undefined;
    psum1(i64, &a, &p);
    try std.testing.expectEqualSlices(i64, &expected, &p);
    psum2(i64, &a, &p);
    try std.testing.expectEqualSlices(i64, &expected, &p);
    psum1a(i64, &a, &p);
    try std.testing.expectEqualSlices(i64, &expected, &p);
}

test "пустой и одноэлементный вход" {
    var empty: [0]f64 = .{};
    var out_empty: [0]f64 = .{};
    psum1(f64, &empty, &out_empty);
    psum2(f64, &empty, &out_empty);
    psum1a(f64, &empty, &out_empty);

    const one = [_]f64{2.5};
    var out_one: [1]f64 = undefined;
    psum2(f64, &one, &out_one);
    try std.testing.expectEqual(@as(f64, 2.5), out_one[0]);
}

$ zig test psum.zig
1/2 psum.test.три версии совпадают с эталоном на целых...OK
2/2 psum.test.пустой и одноэлементный вход...OK
All 2 tests passed.

Версии различаются одним: откуда берётся предыдущая сумма. psum1 читает её из p[i - 1], то есть из памяти, куда её только что записала. psum1a держит её в локальной переменной last. psum2 делает то же и обрабатывает по два элемента за итерацию.

Задачка по книжному упражнению о критическом пути psum1. Нарисуй граф для psum1 на модели Haswell и найди путь. Что получается: в каждой итерации load читает p[i - 1], fadd складывает, store пишет p[i]. Следующая итерация читает p[i], то есть значение, которое store только что положил. Ребро store к load уходит в следующую итерацию, и это ребро через память. Путь на итерацию: загрузка 4 такта, сложение 3, плюс продвижение из буфера сохранений в загрузку, которое книга оценивает ещё в пару тактов. Всего 9. Ровно столько книга и намерила для psum1 на Haswell. Загрузка a[i] в путь не входит: она не зависит от предыдущей итерации и идёт параллельно.

Вторая задачка из книги. Как переписать psum1, чтобы предыдущая сумма не читалась из памяти? Ответ у тебя перед глазами, это psum1a: сохранить последнюю сумму в переменной, и ребро между итерациями станет ребром через регистр. В графе остаются fadd за fadd, путь 3 такта на Haswell, втрое короче. Сохранение из графа никуда не делось, но оно теперь висит сбоку: ни одна операция следующей итерации его результата не ждёт.

Виджет выше умеет и то, и другое: пресеты psum1 и psum2, колонка зафиксирована на дробном сложении, как в книге. Убедись, что на Haswell выходит 9 и 3, а на M4 модель даёт 4 плюс 3 плюс 2 против 3.

Что сделал компилятор

Теперь неприятный сюрприз, который стоит пережить один раз, чтобы потом всегда проверять. Мы перевели psum1 под aarch64 тем же loops_asm.zig, где она записана один в один, p[i] = p[i - 1] + a[i]. Вот тело цикла:

LBB1_3:
	ldr   d1, [x9], #8      ; d1 = a[i]
	fadd  d0, d0, d1        ; d0 = d0 + a[i]
	str   d0, [x1], #8      ; p[i] = d0
	subs  x8, x8, #1
	b.ne  LBB1_3

Загрузки p[i - 1] нет. LLVM держит предыдущую сумму в d0 и переписал psum1 в psum1a без нашего участия. Тело psum1a под тем же компилятором совпадает инструкция в инструкцию, и под x86-64 картина та же, только с развёрткой на четыре.

Почему компилятор имеет на это право, если в прошлом уроке мы говорили, что он обязан читать из памяти честно, потому что p и a могут перекрываться? Потому что перекрытие тут ни при чём. Значение, которое читает p[i - 1], это ровно то, что записал store на предыдущей итерации, и между записью и чтением в программе нет ни одной другой записи. Какой бы адрес ни был у a, он не меняет p[i - 1] между этими двумя точками: чтение a[i] это чтение, а не запись. Компилятор видит пару «запись по адресу, чтение по тому же адресу без записей между ними» и заменяет чтение на записанное значение. Это законно всегда. А вот a[i] он честно читает из памяти каждую итерацию: вдруг p[i - 1], которое он только что записал, и есть a[i].

Отсюда два вывода. Первый: оптимизация из второй задачки книги сегодня делается компилятором сама, и psum1 с psum1a в машинном коде не различить. Второй: чтобы увидеть цену цепочки через память, её надо от компилятора спрятать. Приём тот же blackBox, только теперь через него проходит не значение, а указатель. Компилятор не может доказать, что два указателя, полученных из чёрного ящика, равны, и обязан читать p[i - 1] из памяти.

//! psum1, у которой компилятор не может убрать чтение p[i-1] из памяти:
//! указатель на p пропускается через пустой asm на каждой итерации, и
//! доказать, что читается только что записанное значение, уже нельзя.
//! Так цепочка «запись, чтение, сложение» остаётся в машинном коде,
//! как в книжном psum1.

const std = @import("std");
const cpe = @import("cpe.zig");

pub fn psum1mem(comptime T: type, a: []const T, p: []T) void {
    if (a.len == 0) return;
    p[0] = a[0];
    var i: usize = 1;
    while (i < a.len) : (i += 1) {
        const out: [*]T = cpe.blackBox(p.ptr);
        const prev: [*]const T = cpe.blackBox(p.ptr);
        out[i] = if (@typeInfo(T) == .int) prev[i - 1] +% a[i] else prev[i - 1] + a[i];
    }
}

test "psum1mem считает префиксную сумму" {
    const a = [_]f64{ 1, 2, 3, 4, 5 };
    var p: [5]f64 = undefined;
    psum1mem(f64, &a, &p);
    try std.testing.expectEqualSlices(f64, &[_]f64{ 1, 3, 6, 10, 15 }, &p);
}

Бенч гонит все версии на дробных и на целых:

//! CPE трёх версий префиксной суммы на f64 и i64.
const std = @import("std");
const cpe = @import("cpe.zig");
const psum = @import("psum.zig");
const mem = @import("psum_mem.zig");

const max_n = 8192;

fn Bench(comptime T: type, comptime version: anytype) type {
    return struct {
        a: []const T,
        p: []T,
        pub fn run(self: @This(), n: usize) void {
            version(T, self.a[0..n], self.p[0..n]);
            std.mem.doNotOptimizeAway(self.p[n - 1]);
        }
    };
}

fn row(w: *std.Io.Writer, io: std.Io, ghz: f64, comptime T: type, name: []const u8, comptime version: anytype) !void {
    var a: [max_n]T = undefined;
    var p: [max_n]T = undefined;
    for (&a, 0..) |*x, i| x.* = if (@typeInfo(T) == .int) @intCast(i % 13) else @floatFromInt(i % 13);
    const ctx = Bench(T, version){ .a = &a, .p = &p };
    try w.print("{s:<9} {s:<4} {d:6.2}\n", .{ name, @typeName(T), cpe.measure(io, ghz, ctx) });
}

pub fn main(init: std.process.Init) !void {
    const io = init.io;
    const ghz = cpe.calibrateGhz(io);
    var buf: [512]u8 = undefined;
    var stdout = std.Io.File.stdout().writer(io, &buf);
    const w = &stdout.interface;
    try w.print("частота ядра по калибровке: {d:.2} ГГц\n", .{ghz});
    try w.print("{s:<9} {s:<4} {s:>6}\n", .{ "версия", "тип", "CPE" });
    inline for (.{ f64, i64 }) |T| {
        try row(w, io, ghz, T, "psum1", psum.psum1);
        try row(w, io, ghz, T, "psum1mem", mem.psum1mem);
        try row(w, io, ghz, T, "psum1a", psum.psum1a);
        try row(w, io, ghz, T, "psum2", psum.psum2);
    }
    try w.flush();
}

$ zig build-exe psum_bench.zig -O ReleaseFast && ./psum_bench
частота ядра по калибровке: 3.62 ГГц
версия тип    CPE
psum1     f64    2.23
psum1mem  f64    2.47
psum1a    f64    2.22
psum2     f64    2.19
psum1     i64    1.01
psum1mem  i64    1.30
psum1a    i64    1.03
psum2     i64    1.03

Apple M4 Max, Zig 0.16.0, ReleaseFast, 2026-09-13, два прогона подряд отличаются в сотых.

Читаем. psum1, psum1a и psum2 на дробных стоят одинаково, и стоят они как граница задержки дробного сложения: компилятор сделал из всех трёх один и тот же цикл с цепочкой fadd за fadd. psum1mem, у которой чтение из памяти осталось, дороже: 2.47 против 2.23, то есть ребро через память добавило четверть такта, а не шесть, как предсказывает книжная модель Haswell. Ядро Apple продвигает записанное значение в загрузку прямо из буфера сохранений, а адрес загрузки известен задолго до того, как готовы данные, поэтому почти вся цена продвижения прячется за задержкой самого сложения.

Модель в виджете этого не знает: у неё для M4 такие же 4 плюс 3 плюс 2, и она честно ошибается. Числа таблицы дают границу, а не гарантию, и там, где ядро умеет больше, чем модель, измерение обязано побеждать. На x86-64 продвижение из буфера стоит по опубликованным таблицам от четырёх до пяти тактов сверх загрузки, и там разрыв между psum1mem и psum1a должен быть куда заметнее. Это и есть третья домашняя работа.

На целых разница видна лучше, потому что операция в цепочке стоит один такт и ей нечем прикрыть память: 1.30 против 1.03. Ребро через память стоит здесь почти столько же, около трети такта, но на фоне однотактового сложения это уже тридцать процентов. psum2 на целых ничего не выигрывает у psum1a: сложение целых идёт по такту, и цепочка last за last короче не становится, сколько ни разворачивай.

Это ещё не всё, что можно сказать о памяти: буфер сохранений, продвижение и то, когда загрузка обязана ждать сохранение, а когда нет, разберём через урок, когда дойдём до memset и копирования со сдвигом. Сегодня достаточно того, что ребро через память в графе есть, оно длиннее ребра через регистр, и компилятор умеет его убирать только тогда, когда может доказать, что читает то же, что записал.

Практика: границы своей машины

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

Собери bounds_bench.zig и psum_bench.zig в ReleaseFast и запусти каждый три раза подряд. Калибровка частоты в первой строке должна быть стабильной; если она скачет, машина занята чем-то ещё, и остальные числа тоже врут.
Заполни таблицу границ для четырёх колонок. Посчитай, сколько блоков каждого вида выходит по пропускной способности: единица, делённая на границу.
Сравни psum1mem с psum1a на дробных и на целых. Разница между ними это цена ребра через память на твоём ядре.
Если у тебя x86-64, сверь задержки с таблицами uops.info для своего ядра. Если Apple, с таблицами Dougall Johnson. Расхождение больше половины такта это повод разобраться, а не округлить.

Упражнения

CHK-1★

Выпиши для ядра Haswell из таблицы урока, какие операции цикла combine4 на умножении целых уходят в какие блоки, и посчитай границу пропускной способности вручную: одна загрузка на два загрузчика, одно умножение на один умножитель, сложение указателя и сравнение на четыре сумматора. Сверь с виджетом и объясни, почему граница получилась по умножителю, а не по загрузкам.

CHK-2★★

Напиши цикл с двумя аккумуляторами из задачки урока: acc копит сумму элементов, acc2 копит сумму элементов, умноженных на константу. Сними CPE на дробных через измеритель cpe.zig и покажи, что умножение стоит бесплатно: CPE равен границе задержки сложения, а не сумме задержек.

CHK-3★★

Сними ассемблер combine4_iadd под aarch64 и под x86-64 и нарисуй граф потока данных для x86-64-версии, где LLVM развернул цикл на восемь. Покажи, что критический путь на один элемент не изменился по сравнению с четырёхинструкционной версией, и объясни, что именно развёртка сэкономила.

CHK-4★★★

Сделай psum1mem на целых по-настоящему дорогой: замени сложение на умножение по модулю, чтобы операция в цепочке стала трёхтактовой, и сними CPE для версии через регистр и версии через память. Объясни по графу, почему разница между ними не зависит от задержки самой операции.

CHK-5★★★

Добавь в dataflow-math.ts пресет для схемы Горнера из прошлого урока (acc = acc * x + c[i]) и для многочлена в лоб (acc += c[i] * xpwr; xpwr *= x). Убедись, что тесты модуля остаются зелёными, и проверь виджетом, что на M4 в лоб выходит граница задержки умножения, а по Горнеру сумма задержек умножения и сложения. Сверь с CPE, снятым в прошлом уроке.

Итоги

Настоящее ядро отличается от Y86 PIPE пятью вещами: несколько инструкций за такт, разные задержки у операций, исполнение по готовности операндов, переименование регистров и спекуляция с откатом. Вместо вопроса «сколько тактов занимает инструкция» появляется вопрос «какая цепочка зависимостей самая длинная».
Ядро это блок управления инструкциями и блок исполнения. Первый выбирает по предсказанию, декодирует в операции и отставляет результаты в порядке программы; второй запускает операции в функциональные блоки, как только готовы операнды.
Переименование регистров заменяет имена тегами. Ложные зависимости через одно имя исчезают, остаются только настоящие, через значение, и граф потока данных состоит ровно из них.
У операции три числа: задержка, интервал выпуска и ёмкость. Из них две границы CPE: граница задержки на цепочке зависимостей и граница пропускной способности по самому занятому блоку.
На M4 Max границы задержки 1.00, 2.99, 2.49 и 3.42 такта, пропускной способности 0.16, 0.33, 0.25 и 0.25 для четырёх колонок. Расстояние между границами больше, чем у Haswell: у современного ядра простаивает больше блоков.
Границы измеряются двумя цепочками, зависимой и шестнадцатью независимыми, а пустой asm с ограничением "+r" не даёт компилятору свернуть цепочку.
Граф потока данных строится в три шага: инструкции в операции, рёбра по результатам, лишнее долой. Остаются регистры, унесённые в следующую итерацию, и критический путь идёт по самой дорогой из этих цепочек.
combine4 во всех четырёх колонках лежит на границе задержки, потому что у него одна цепочка аккумулятора. Пока цепочка одна, число блоков не имеет значения.
У префиксной суммы psum1 цепочка идёт через память: запись, чтение, сложение. На модели Haswell это 9 тактов против 3 у версии через регистр.
Компилятор заменяет чтение только что записанного значения на само значение, когда между записью и чтением нет других записей, и превращает psum1 в psum1a сам. Чтобы увидеть цену ребра через память, указатель нужно спрятать за blackBox.

Дальше

Сегодня ты научился читать цикл как граф и находить в нём цепочку, которая всё решает. У combine4 она одна, и поэтому CPE упирается в задержку операции, хотя у ядра простаивает пять сумматоров из шести. Следующий урок ровно про то, как эти блоки занять: развёртка k к 1 сократит накладные расходы и упрётся в ту же границу, несколько аккумуляторов разрежут цепочку на независимые части и уронят CPE к границе пропускной способности, а переупорядочение операций сделает то же с одним аккумулятором. На каждый приём будет своя версия свёртки, combine5 до combine7, свой граф в виджете этого урока и своё измерение, и всё это ты уже умеешь предсказывать до запуска.

домашка

Домашка

Нарисуй граф потока данных для схемы Горнера из прошлого урока, найди критический путь на модели M4 и предскажи CPE. Сними CPE на своей машине и объясни расхождение, если оно больше десяти процентов.L
Прогони bounds_bench на своей машине, заполни таблицу задержки и пропускной способности для четырёх колонок и подпиши, сколько блоков каждого вида у твоего ядра выходит по измерению.S
Собери psum_bench под x86-64 и прогони в виртуалке или в песочнице раннера. Сравни цену цепочки через память на x86-64 с той, что снята на M4, и объясни, откуда разница, по таблицам uops.info.L