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

PIPE на Verilog и CPI

lead~140 мин

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

PIPE на Verilog и CPI

В прошлом уроке ты разобрал конвейер по частям: регистры F, D, E, M и W, предсказание перехода, пять точек продвижения, останов на риске загрузки, три пузырька за ret, два за ошибочно предсказанный переход. Сегодня всё это становится одним файлом на Verilog, который собирается и запускается. Мы напишем управляющую логику, соберём верхний уровень pipe.sv, прогоним через него все двенадцать программ блока и получим трассу, совпадающую с трассой SEQ и Zig-симулятора байт в байт, только за другое число тактов. Из разницы между этими числами вырастет CPI: единица плюс три штрафа. А в конце посчитаем, во что обходится ветвление, и посмотрим, чего в этой машине всё ещё нет.

Цели урока

Понять конвейерный регистр как элемент с тремя режимами: обычная загрузка, останов и пузырёк, и увидеть, как эти режимы записываются одним блоком always_ff.
Прочитать логику продвижения как приоритетную цепочку из пяти точек и объяснить, почему порядок веток в ней обязателен.
Написать управляющую логику control.sv целиком: четыре условия и шесть выходных сигналов.
Разобрать комбинации рисков и понять, почему D_bubble содержит оговорку про load/use, и что сломалось бы без неё.
Собрать pipe.sv и тестбенч tb_pipe.sv, прогнать все двенадцать программ и сверить трассу с SEQ и с Zig.
Считать CPI по формуле “единица плюс lp плюс mp плюс rp” и проверять расчёт настоящим числом тактов.
Сравнить три стратегии предсказания перехода на бумаге и понять, откуда берётся разница между abs_sum и abs_sum_cmov.
Знать границы этой машины: многотактовые инструкции, интерфейс к кэшу, внеочередное исполнение.

Идея: пять решений на каждом фронте такта

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

Обычная работа. По фронту такта регистр принимает то, что насчитала предыдущая ступень. Так проходит почти каждый такт.

Останов. Регистр не меняется, и та же инструкция остаётся в нём ещё на такт. Останов нужен, когда значение, которого ждёт инструкция, физически ещё не появилось.

Пузырёк. Регистр обнуляется, и вместо инструкции в него приезжает nop. Пузырёк нужен, когда инструкция, уже вошедшая в конвейер, оказалась лишней или преждевременной.

Конвейерный регистр

в Verilog это блок always_ff, а три режима это порядок веток внутри него. Приоритет всегда один и тот же: сначала сброс, потом пузырёк, потом останов, и только в самом конце обычная загрузка.

// Скелет конвейерного регистра. Порядок веток задаёт приоритет режимов.
always_ff @(posedge clk) begin
  if (rst || X_bubble) begin
    // обнулить: вместо инструкции приезжает nop
  end else if (!X_stall) begin
    // обычная работа: принять то, что насчитала предыдущая ступень
  end
  // иначе не делаем ничего: содержимое регистра сохраняется
end

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

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

Логика продвижения: пять точек и один приоритет

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

Оба модуля этого урока начинаются со строки import y86_pkg::*, поэтому сначала напомню сам пакет. Он тот же, что и во всех уроках блока, и приведён целиком: логика продвижения берёт отсюда ICALL и IJXX, логика управления IMRMOVQ, IPOPQ, IRET, IJXX и SAOK, остальные имена нужны модулям этапов.

// Общие константы Y86-64: коды инструкций, функции АЛУ, номера регистров,
// коды состояния. Каждый модуль начинается со строки import y86_pkg::*,
// поэтому имена icode и Stat читаются так же, как в главе 4 CS:APP.
// Пакет общий на весь проект, поэтому любой отдельно взятый модуль берёт
// из него лишь горстку констант. Verilator считает неиспользованной каждую
// остальную и на одном только alu выдаёт три десятка предупреждений, так что
// проверка на неиспользованный параметр здесь выключена целиком.
/* verilator lint_off UNUSEDPARAM */
package y86_pkg;

  // Разрядность машинного слова и размер памяти в байтах.
  // WORD ни в один модуль не подставляется: разрядность портов записана
  // числом [63:0], как её рисует книга. Константа стоит здесь как единственное
  // место, где разрядность машины названа словом.
  localparam int WORD      = 64;
  localparam int MEM_BYTES = 4096;

  // icode: старший полубайт первого байта инструкции.
  localparam logic [3:0] IHALT   = 4'h0;
  localparam logic [3:0] INOP    = 4'h1;
  localparam logic [3:0] IRRMOVQ = 4'h2;  // сюда же попадают cmovXX
  localparam logic [3:0] IIRMOVQ = 4'h3;
  localparam logic [3:0] IRMMOVQ = 4'h4;
  localparam logic [3:0] IMRMOVQ = 4'h5;
  localparam logic [3:0] IOPQ    = 4'h6;
  localparam logic [3:0] IJXX    = 4'h7;
  localparam logic [3:0] ICALL   = 4'h8;
  localparam logic [3:0] IRET    = 4'h9;
  localparam logic [3:0] IPUSHQ  = 4'hA;
  localparam logic [3:0] IPOPQ   = 4'hB;
  localparam logic [3:0] IIADDQ  = 4'hC;  // расширение из упражнения 4.3

  // ifun для OPq, он же код операции АЛУ.
  localparam logic [3:0] ALUADD = 4'h0;
  localparam logic [3:0] ALUSUB = 4'h1;
  localparam logic [3:0] ALUAND = 4'h2;
  localparam logic [3:0] ALUXOR = 4'h3;

  // ifun для jXX и cmovXX.
  localparam logic [3:0] CALWAYS = 4'h0;
  localparam logic [3:0] CLE     = 4'h1;
  localparam logic [3:0] CL      = 4'h2;
  localparam logic [3:0] CE      = 4'h3;
  localparam logic [3:0] CNE     = 4'h4;
  localparam logic [3:0] CGE     = 4'h5;
  localparam logic [3:0] CG      = 4'h6;

  // Регистры. Их пятнадцать, номер 4'hF означает «регистра нет».
  localparam logic [3:0] RRSP  = 4'h4;
  localparam logic [3:0] RNONE = 4'hF;

  // Коды состояния машины.
  localparam logic [2:0] SAOK = 3'h1;  // всё хорошо
  localparam logic [2:0] SHLT = 3'h2;  // выполнен halt
  localparam logic [2:0] SADR = 3'h3;  // обращение за границу памяти
  localparam logic [2:0] SINS = 3'h4;  // неизвестная инструкция

endpackage
/* verilator lint_on UNUSEDPARAM */

А вот и сам блок пробросов целиком.

// Блок пробросов, рисунок 4.60 книги.
// Регистровый файл отдаёт значение, записанное в него на прошлых тактах.
// Но нужное значение может ещё лететь по конвейеру и не дойти до записи.
// Поэтому мы смотрим на пять точек и берём значение из самой ранней из них,
// то есть из самой свежей инструкции.
//
// Порядок приоритета обязателен: если два порта записи метят в один регистр,
// побеждает тот, который ближе к началу конвейера, потому что он моложе.
module forward (
  input  logic [3:0]  D_icode,
  input  logic [63:0] D_valP,

  input  logic [3:0]  d_srcA,
  input  logic [3:0]  d_srcB,
  input  logic [63:0] d_rvalA,
  input  logic [63:0] d_rvalB,

  input  logic [3:0]  e_dstE,   // результат АЛУ, ещё в этапе исполнения
  input  logic [63:0] e_valE,
  input  logic [3:0]  M_dstM,   // слово из памяти, читается прямо сейчас
  input  logic [63:0] m_valM,
  input  logic [3:0]  M_dstE,   // результат АЛУ, дошёл до этапа памяти
  input  logic [63:0] M_valE,
  input  logic [3:0]  W_dstM,   // слово из памяти, дошло до записи
  input  logic [63:0] W_valM,
  input  logic [3:0]  W_dstE,   // результат АЛУ, дошёл до записи
  input  logic [63:0] W_valE,

  output logic [63:0] d_valA,
  output logic [63:0] d_valB
);

  import y86_pkg::*;

  // Порт A. У call и jXX через него передаётся valP: этап памяти положит его
  // на стек как адрес возврата, а этап выборки возьмёт как точку отката,
  // если предсказание перехода не сбылось.
  always_comb begin
    if      (D_icode == ICALL || D_icode == IJXX) d_valA = D_valP;
    else if (d_srcA == e_dstE)                    d_valA = e_valE;
    else if (d_srcA == M_dstM)                    d_valA = m_valM;
    else if (d_srcA == M_dstE)                    d_valA = M_valE;
    else if (d_srcA == W_dstM)                    d_valA = W_valM;
    else if (d_srcA == W_dstE)                    d_valA = W_valE;
    else                                          d_valA = d_rvalA;
  end

  // Порт B устроен так же, только без особого случая для call и jXX.
  always_comb begin
    if      (d_srcB == e_dstE) d_valB = e_valE;
    else if (d_srcB == M_dstM) d_valB = m_valM;
    else if (d_srcB == M_dstE) d_valB = M_valE;
    else if (d_srcB == W_dstM) d_valB = W_valM;
    else if (d_srcB == W_dstE) d_valB = W_valE;
    else                       d_valB = d_rvalB;
  end

endmodule

Это не мультиплексор, а именно цепочка if с приоритетом: else if в always_comb синтезируется в дерево вентилей, где первое совпавшее условие выигрывает. Порядок веток кодирует возраст инструкций. Ступень исполнения ближе к началу конвейера, значит инструкция в ней моложе той, что уже дошла до памяти, значит её значение свежее. Переставь две строки местами, и машина начнёт брать устаревшее значение в тот момент, когда две инструкции подряд пишут в один регистр. Такая перестановка не ломает ни одну из двенадцати программ сразу, она ломает только те, где цепочка зависимостей длиннее двух звеньев, и найти её потом тяжело.

Управляющая логика: четыре условия и шесть сигналов

Теперь то, что пробросы закрыть не могут. Ситуаций ровно четыре, и каждая из них это одна строка на Verilog.

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

ret_in_pipe. Инструкция ret находится в декодировании, исполнении или обращении к памяти. Адрес возврата лежит в памяти и станет известен, только когда ret доедет до записи.

mispredicted. В исполнении стоит условный переход, а его условие не сработало. Мы предсказываем “переход берётся”, значит две инструкции уже выбраны не с той стороны, и их надо отменить.

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

Останов и пузырёк

раздаются пяти регистрам шестью сигналами. Вот весь модуль.

// Блок управления конвейером, рисунок 4.68 книги.
// Три ситуации, с которыми не справляются пробросы, плюс исключения:
//
//   1. load/use. Инструкция в этапе исполнения читает память, а следующая
//      сразу хочет прочитанное. Значение появится только на такт позже,
//      пробрасывать нечего, поэтому конвейер тормозится на один такт.
//   2. ret. Адрес возврата известен только когда ret дойдёт до записи.
//      До этого выборка стоит, а в декодирование три такта идут пузырьки.
//   3. Непредсказанный переход. Мы всегда предполагаем, что переход берётся.
//      Если условие не сработало, две уже выбранные инструкции надо убить.
//   4. Исключение. Инструкции, вошедшие в конвейер после сбойной, не должны
//      менять состояние машины, поэтому этап памяти обнуляется, а запись стоит.
module control (
  input  logic [3:0] D_icode,
  input  logic [3:0] E_icode,
  input  logic [3:0] M_icode,
  input  logic [3:0] E_dstM,
  input  logic [3:0] d_srcA,
  input  logic [3:0] d_srcB,
  input  logic       e_Cnd,
  input  logic [2:0] m_stat,
  input  logic [2:0] W_stat,

  output logic       F_stall,
  output logic       D_stall,
  output logic       D_bubble,
  output logic       E_bubble,
  output logic       M_bubble,
  output logic       W_stall
);

  import y86_pkg::*;

  logic load_use;
  logic ret_in_pipe;
  logic mispredicted;
  logic exception;

  always_comb load_use = ((E_icode == IMRMOVQ) || (E_icode == IPOPQ)) &&
                         ((E_dstM == d_srcA) || (E_dstM == d_srcB));

  always_comb ret_in_pipe = (D_icode == IRET) || (E_icode == IRET) || (M_icode == IRET);

  always_comb mispredicted = (E_icode == IJXX) && !e_Cnd;

  always_comb exception = (m_stat != SAOK) || (W_stat != SAOK);

  // Выборка стоит и при load/use, и пока ret не доехал до записи.
  always_comb F_stall = load_use || ret_in_pipe;

  // Декодирование стоит только при load/use: инструкция должна дождаться операнда.
  always_comb D_stall = load_use;

  // Пузырёк в декодирование: после непредсказанного перехода, а также вслед
  // за ret, но только если конвейер не остановлен по load/use.
  always_comb D_bubble = mispredicted || (ret_in_pipe && !load_use);

  // Пузырёк в исполнение: непредсказанный переход убивает уже раскодированную
  // инструкцию, а load/use вставляет такт ожидания.
  always_comb E_bubble = mispredicted || load_use;

  always_comb M_bubble = exception;
  always_comb W_stall  = (W_stat != SAOK);

endmodule

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

Комбинации рисков

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

Риск загрузки требует, чтобы в исполнении стояла mrmovq или popq. Ошибочное предсказание требует, чтобы в исполнении стоял jXX. Одна ступень, две разные инструкции: пара невозможна. Точно так же невозможна пара “ошибочное предсказание плюс ret в исполнении” и “риск загрузки плюс ret в исполнении”.

Остаются ровно две пары, и обе связаны с ret в декодировании.

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

Комбинация B: загрузка пишет в регистр, который тут же нужен инструкции ret. На практике это загрузка в %rsp: ret читает %rsp, чтобы снять со стека адрес возврата.

Вторая комбинация и есть та самая ошибка, которую книга находит систематическим анализом, а не прогоном программ. Посмотри на условия. При комбинации B истинны и load_use, и ret_in_pipe. Обработка ret требует пузырька в D. Риск загрузки требует останова в D. Если написать D_bubble наивно, ступень D получит на одном фронте и “обнулить”, и “сохранить содержимое”. Это не просто конфликт двух сигналов, это противоречивая команда, на которую железо ответит чем угодно.

Правильное поведение однозначно: побеждает риск загрузки. Инструкция ret должна дождаться своего %rsp, а её собственная обработка откладывается на такт. Отсюда оговорка в листинге:

always_comb D_bubble = mispredicted || (ret_in_pipe && !load_use);

Виджет ниже даёт покрутить это руками: ты выбираешь первую инструкцию, вторую и расстояние между ними, а он собирает из них программу, гоняет её через конвейер и показывает, какой риск получился, во что он обошёлся в тактах и как выглядит лестница этапов. Комбинация A там собирается прямо из списка: поставь первой “jne, переход не берётся”, второй ret и расстояние ноль.

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

# Комбинация A: переход, который не берётся, а по адресу за ним стоит ret.
        .pos 0
init:   irmovq stack, %rsp
        call f
        halt

f:      irmovq $1, %rax
        andq %rax, %rax
        je back                 # не берётся, за ним сразу ret
back:   ret

        .pos 0x200
stack:

Комбинация B требует загрузки прямо в %rsp. Положим в память адрес ячейки, которая сыграет роль вершины стека, и в этой ячейке адрес возврата.

# Комбинация B: загрузка в %rsp, а следом ret, которому %rsp нужен сразу.
        .pos 0
init:   irmovq p, %rbx
        mrmovq (%rbx), %rsp     # в %rsp приходит вершина стека из памяти
        ret                     # снимает адрес возврата по загруженному %rsp
        halt                    # сюда не попадаем

        .align 8
p:      .quad frame
frame:  .quad done

done:   irmovq $42, %rax
        halt

        .pos 0x200
stack:

Прогоняем обе через конвейер и сверяем с Zig-симулятором, для которого никаких рисков не существует.

$ zig build run -- asm build/comb_a.ys --hex build/comb_a.hex -o build/comb_a.yo
$ zig build run -- sim build/comb_a.yo > build/comb_a.zig
$ bash hdl/run.sh pipe build/comb_a.hex > build/comb_a.pipe
$ cat build/comb_a.pipe
0x000 30 AOK
0x00a 80 AOK
0x014 30 AOK
0x01e 62 AOK
0x020 73 AOK
0x029 90 AOK
0x013 00 HLT
$ bash tools/compare-trace.sh build/comb_a.zig build/comb_a.pipe
cycles: comb_a.zig=7 comb_a.pipe=16
traces match

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

$ bash tools/compare-trace.sh build/comb_b.zig build/comb_b.pipe
cycles: comb_b.zig=5 comb_b.pipe=13
traces match

Пять инструкций, тринадцать тактов. Четыре такта на заполнение конвейера, один на риск загрузки и три на ret. Если убрать оговорку && !load_use из D_bubble, эта программа перестанет работать: сама ret исчезнет вместе с обнулённой ступенью D, машина поедет дальше на halt по адресу 0x015 и остановится, не дойдя до done. В трассе это видно сразу, строки с 0x014 90 в ней просто не будет.

Верхний уровень: pipe.sv

Файл длинный, поэтому пойдём по разделам. Комбинационные модули ступеней (fetch, decode, execute, memory_stage, stat) взяты из SEQ без единой правки. Конвейер добавляет к ним регистры, пробросы и управление, и больше ничего.

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

// Конвейерная реализация Y86-64: те же шесть этапов, но теперь они работают
// одновременно над разными инструкциями. Между этапами стоят конвейерные
// регистры F, D, E, M и W. Комбинационные модули этапов взяты из SEQ без
// изменений: конвейер добавляет к ним регистры, пробросы и управление.
//
// Соглашение об именах из книги: заглавная буква это содержимое регистра
// (D_icode), строчная это сигнал внутри соответствующего этапа (d_srcA).
// Соглашение об именах взято из книги целиком, поэтому F_predPC и f_predPC
// это разные провода, отличающиеся только регистром букв. Verilator считает
// такие пары опечаткой, здесь это осознанный стиль всей главы.
/* verilator lint_off SIMILARNAME */
module pipe (
  input  logic        clk,
  input  logic        rst,

  // Наблюдательные выходы для тестбенча. Инструкция считается завершённой,
  // когда она попала в регистр W и не является пузырьком.
  output logic        retire,
  output logic [63:0] retire_pc,
  output logic [3:0]  retire_icode,
  output logic [3:0]  retire_ifun,
  output logic [2:0]  retire_stat
);

  import y86_pkg::*;

  // ------------------------------------------------------------------
  // Конвейерные регистры.
  // Поля valid и iPC книге не нужны, они добавлены только ради трассы:
  // valid отличает настоящий nop от пузырька, iPC хранит адрес инструкции.
  // ------------------------------------------------------------------
  logic [63:0] F_predPC;

  logic        D_valid;  logic [2:0] D_stat;  logic [3:0] D_icode, D_ifun;
  logic [3:0]  D_rA, D_rB;  logic [63:0] D_valC, D_valP, D_iPC;

  logic        E_valid;  logic [2:0] E_stat;  logic [3:0] E_icode, E_ifun;
  logic [63:0] E_valC, E_valA, E_valB, E_iPC;  logic [3:0] E_dstE, E_dstM;

  logic        M_valid;  logic [2:0] M_stat;  logic [3:0] M_icode, M_ifun;
  logic        M_Cnd;    logic [63:0] M_valE, M_valA, M_iPC;
  logic [3:0]  M_dstE, M_dstM;

  logic        W_valid;  logic [2:0] W_stat;  logic [3:0] W_icode, W_ifun;
  logic [63:0] W_valE, W_valM, W_iPC;  logic [3:0] W_dstE, W_dstM;

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

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

  // ------------------------------------------------------------------
  // Этап выборки
  // ------------------------------------------------------------------
  logic [63:0] f_pc, f_predPC;
  logic [79:0] imem_bytes;
  logic        imem_error_raw, f_imem_error, f_instr_valid;
  logic [3:0]  f_icode, f_ifun, f_rA, f_rB;
  logic [63:0] f_valC, f_valP;
  logic        f_need_regids, f_need_valC;
  logic [2:0]  f_stat;

  // Откуда брать адрес. Два случая, когда предсказание оказалось неверным:
  // переход, который не взялся, и возврат из процедуры.
  always_comb begin
    if      ((M_icode == IJXX) && !M_Cnd) f_pc = M_valA;   // valP несработавшего перехода
    else if (W_icode == IRET)             f_pc = W_valM;   // адрес возврата из памяти
    else                                  f_pc = F_predPC;
  end

  fetch u_fetch (
    .pc            (f_pc),
    .imem_bytes    (imem_bytes),
    .imem_error_in (imem_error_raw),
    .icode         (f_icode),
    .ifun          (f_ifun),
    .rA            (f_rA),
    .rB            (f_rB),
    .valC          (f_valC),
    .valP          (f_valP),
    .instr_valid   (f_instr_valid),
    .imem_error    (f_imem_error),
    .need_regids   (f_need_regids),
    .need_valC     (f_need_valC)
  );

  stat u_f_stat (
    .imem_error  (f_imem_error),
    .instr_valid (f_instr_valid),
    .dmem_error  (1'b0),
    .icode       (f_icode),
    .Stat        (f_stat)
  );

  // Предсказание: переход всегда берётся. Для call это даже не предсказание,
  // адрес известен точно. Для ret предсказывать нечего, туда пойдёт valP,
  // и он всё равно будет отброшен, когда ret дойдёт до записи.
  always_comb f_predPC = ((f_icode == IJXX) || (f_icode == ICALL)) ? f_valC : f_valP;

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

Дальше декодирование и исполнение. Декодирование это чистый вызов модуля из SEQ, а вот в исполнении появляется строка, которой в SEQ не было.

  // ------------------------------------------------------------------
  // Этап декодирования
  // ------------------------------------------------------------------
  logic [3:0]  d_srcA, d_srcB, d_dstE, d_dstM;
  logic [63:0] d_rvalA, d_rvalB, d_valA, d_valB;

  decode u_decode (
    .icode (D_icode),
    .rA    (D_rA),
    .rB    (D_rB),
    .srcA  (d_srcA),
    .srcB  (d_srcB),
    .dstE  (d_dstE),
    .dstM  (d_dstM)
  );

  // ------------------------------------------------------------------
  // Этап исполнения
  // ------------------------------------------------------------------
  logic [63:0] e_aluA, e_aluB, e_valE;
  logic [3:0]  e_alufun, e_dstE;
  logic        e_set_cc_raw, e_set_cc, e_Cnd;
  logic        e_new_ZF, e_new_SF, e_new_OF;
  logic        cc_ZF, cc_SF, cc_OF;

  execute u_execute (
    .icode  (E_icode),
    .ifun   (E_ifun),
    .valA   (E_valA),
    .valB   (E_valB),
    .valC   (E_valC),
    .ZF     (cc_ZF),
    .SF     (cc_SF),
    .OF     (cc_OF),
    .aluA   (e_aluA),
    .aluB   (e_aluB),
    .alufun (e_alufun),
    .set_cc (e_set_cc_raw),
    .valE   (e_valE),
    .Cnd    (e_Cnd),
    .new_ZF (e_new_ZF),
    .new_SF (e_new_SF),
    .new_OF (e_new_OF)
  );

  // В SEQ несработавшую условную пересылку отменял этап записи. В конвейере
  // это надо сделать здесь: номер регистра e_dstE уходит в пробросы,
  // и он обязан быть уже окончательным.
  always_comb e_dstE = ((E_icode == IRRMOVQ) && !e_Cnd) ? RNONE : E_dstE;

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

Дальше память и исключения.

  // ------------------------------------------------------------------
  // Этап обращения к памяти
  // ------------------------------------------------------------------
  logic [63:0] mem_addr, mem_data, m_valM;
  logic        mem_read, mem_write, dmem_error;
  logic [2:0]  m_stat;

  // valP инструкции call едет по конвейеру внутри valA: пробросы кладут туда
  // D_valP, поэтому отдельного поля valP регистру M не нужно.
  memory_stage u_memory_stage (
    .icode     (M_icode),
    .valA      (M_valA),
    .valE      (M_valE),
    .valP      (M_valA),
    .mem_addr  (mem_addr),
    .mem_data  (mem_data),
    .mem_read  (mem_read),
    .mem_write (mem_write)
  );

  always_comb m_stat = dmem_error ? SADR : M_stat;

  // ------------------------------------------------------------------
  // Исключения: инструкции моложе сбойной не должны ничего менять
  // ------------------------------------------------------------------
  logic m_exception, W_exception;
  always_comb m_exception = (m_stat != SAOK);
  always_comb W_exception = (W_stat != SAOK);

  // Флаги не обновляются, если впереди по конвейеру уже есть исключение.
  always_comb e_set_cc = e_set_cc_raw && !m_exception && !W_exception;

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

Затем сборка: управление, пробросы, регистровый файл и память.

  // ------------------------------------------------------------------
  // Управление конвейером
  // ------------------------------------------------------------------
  logic F_stall, D_stall, D_bubble, E_bubble, M_bubble, W_stall;

  control u_control (
    .D_icode  (D_icode),
    .E_icode  (E_icode),
    .M_icode  (M_icode),
    .E_dstM   (E_dstM),
    .d_srcA   (d_srcA),
    .d_srcB   (d_srcB),
    .e_Cnd    (e_Cnd),
    .m_stat   (m_stat),
    .W_stat   (W_stat),
    .F_stall  (F_stall),
    .D_stall  (D_stall),
    .D_bubble (D_bubble),
    .E_bubble (E_bubble),
    .M_bubble (M_bubble),
    .W_stall  (W_stall)
  );

  // ------------------------------------------------------------------
  // Пробросы и регистровый файл
  // ------------------------------------------------------------------
  forward u_forward (
    .D_icode (D_icode),
    .D_valP  (D_valP),
    .d_srcA  (d_srcA),
    .d_srcB  (d_srcB),
    .d_rvalA (d_rvalA),
    .d_rvalB (d_rvalB),
    .e_dstE  (e_dstE),
    .e_valE  (e_valE),
    .M_dstM  (M_dstM),
    .m_valM  (m_valM),
    .M_dstE  (M_dstE),
    .M_valE  (M_valE),
    .W_dstM  (W_dstM),
    .W_valM  (W_valM),
    .W_dstE  (W_dstE),
    .W_valE  (W_valE),
    .d_valA  (d_valA),
    .d_valB  (d_valB)
  );

  regfile u_regs (
    .clk      (clk),
    .rst      (rst),
    .srcA     (d_srcA),
    .srcB     (d_srcB),
    .valA     (d_rvalA),
    .valB     (d_rvalB),
    .write_en (!W_exception),
    .dstE     (W_dstE),
    .valE     (W_valE),
    .dstM     (W_dstM),
    .valM     (W_valM)
  );

  memory u_mem (
    .clk        (clk),
    .imem_addr  (f_pc),
    .imem_bytes (imem_bytes),
    .imem_error (imem_error_raw),
    .dmem_addr  (mem_addr),
    .dmem_read  (mem_read),
    // Запись в память запрещена, если инструкция старше уже сбойнула.
    .dmem_write (mem_write && !W_exception),
    .dmem_wdata (mem_data),
    .dmem_rdata (m_valM),
    .dmem_error (dmem_error)
  );

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

  // ------------------------------------------------------------------
  // Конвейерные регистры по фронту такта
  // ------------------------------------------------------------------
  always_ff @(posedge clk) begin
    if (rst) begin
      F_predPC <= 64'd0;
    end else if (!F_stall) begin
      F_predPC <= f_predPC;
    end
  end

  always_ff @(posedge clk) begin
    if (rst || D_bubble) begin
      D_valid <= 1'b0;  D_stat <= SAOK;  D_icode <= INOP;  D_ifun <= 4'h0;
      D_rA    <= RNONE; D_rB   <= RNONE; D_valC  <= 64'd0; D_valP <= 64'd0;
      D_iPC   <= 64'd0;
    end else if (!D_stall) begin
      D_valid <= 1'b1;  D_stat <= f_stat; D_icode <= f_icode; D_ifun <= f_ifun;
      D_rA    <= f_rA;  D_rB   <= f_rB;   D_valC  <= f_valC;  D_valP <= f_valP;
      D_iPC   <= f_pc;
    end
  end

  always_ff @(posedge clk) begin
    if (rst || E_bubble) begin
      E_valid <= 1'b0;  E_stat <= SAOK;  E_icode <= INOP;  E_ifun <= 4'h0;
      E_valC  <= 64'd0; E_valA <= 64'd0; E_valB  <= 64'd0;
      E_dstE  <= RNONE; E_dstM <= RNONE; E_iPC   <= 64'd0;
    end else begin
      E_valid <= D_valid; E_stat <= D_stat; E_icode <= D_icode; E_ifun <= D_ifun;
      E_valC  <= D_valC;  E_valA <= d_valA; E_valB  <= d_valB;
      E_dstE  <= d_dstE;  E_dstM <= d_dstM; E_iPC   <= D_iPC;
    end
  end

  always_ff @(posedge clk) begin
    if (rst || M_bubble) begin
      M_valid <= 1'b0;  M_stat <= SAOK;  M_icode <= INOP;  M_ifun <= 4'h0;
      M_Cnd   <= 1'b0;  M_valE <= 64'd0; M_valA  <= 64'd0;
      M_dstE  <= RNONE; M_dstM <= RNONE; M_iPC   <= 64'd0;
    end else begin
      M_valid <= E_valid; M_stat <= E_stat; M_icode <= E_icode; M_ifun <= E_ifun;
      M_Cnd   <= e_Cnd;   M_valE <= e_valE; M_valA  <= E_valA;
      M_dstE  <= e_dstE;  M_dstM <= E_dstM; M_iPC   <= E_iPC;
    end
  end

  always_ff @(posedge clk) begin
    if (rst) begin
      W_valid <= 1'b0;  W_stat <= SAOK;  W_icode <= INOP;  W_ifun <= 4'h0;
      W_valE  <= 64'd0; W_valM <= 64'd0; W_dstE  <= RNONE; W_dstM <= RNONE;
      W_iPC   <= 64'd0;
    end else if (!W_stall) begin
      W_valid <= M_valid; W_stat <= m_stat;  W_icode <= M_icode; W_ifun <= M_ifun;
      W_valE  <= M_valE;  W_valM <= m_valM;  W_dstE  <= M_dstE;  W_dstM <= M_dstM;
      W_iPC   <= M_iPC;
    end
  end

  // Регистр флагов. В конвейере его пишет этап исполнения, а не записи:
  // условие следующей инструкции должно увидеть свежие флаги вовремя.
  always_ff @(posedge clk) begin
    if (rst) begin
      cc_ZF <= 1'b1;
      cc_SF <= 1'b0;
      cc_OF <= 1'b0;
    end else if (e_set_cc) begin
      cc_ZF <= e_new_ZF;
      cc_SF <= e_new_SF;
      cc_OF <= e_new_OF;
    end
  end

Заметь распределение режимов. Регистры F, D и W умеют останавливаться, регистры D, E и M умеют обнуляться, а E и M останавливаться не умеют вообще: у них в блоке нет ветки else if. Это не упрощение, а прямое следствие того, какие сигналы вырабатывает управляющая логика. Пятнадцать возможных пар “регистр, режим” ужимаются до шести реально нужных.

И регистр флагов. В SEQ его писал этап записи, в конвейере пишет исполнение. Иначе условие следующей инструкции сравнивалось бы с флагами, которые ещё не обновились, и jle после subq читал бы состояние трёхтактовой давности.

Последний кусок файла нужен только трассе.

  // ------------------------------------------------------------------
  // Признак завершения инструкции для трассы
  // ------------------------------------------------------------------
  // Пока регистр W стоит, в нём лежит та же инструкция, что и на прошлом
  // такте, и печатать её второй раз нельзя. Поэтому запоминаем, приняла ли
  // ступень W новое содержимое на последнем фронте.
  logic w_loaded;

  always_ff @(posedge clk) begin
    if (rst) w_loaded <= 1'b0;
    else     w_loaded <= !W_stall;
  end

  always_comb retire       = W_valid && w_loaded;
  always_comb retire_pc    = W_iPC;
  always_comb retire_icode = W_icode;
  always_comb retire_ifun  = W_ifun;
  always_comb retire_stat  = W_stat;

  // Сигналы, которые этапы выставляют для наглядности схемы, но верхнему
  // уровню не нужны.
  /* verilator lint_off UNUSEDSIGNAL */
  logic unused_ok;
  always_comb unused_ok = &{1'b0, f_need_regids, f_need_valC, e_aluA, e_aluB, e_alufun};
  /* verilator lint_on UNUSEDSIGNAL */

endmodule
/* verilator lint_on SIMILARNAME */

Сигнал retire это ответ на вопрос “завершилась ли сейчас настоящая инструкция”. Условий два, и оба нужны. Инструкция не должна быть пузырьком, отсюда W_valid. И ступень W должна была принять новое содержимое на последнем фронте, отсюда w_loaded: при исключении регистр W стоит бесконечно, и без этой проверки трасса печатала бы сбойную инструкцию каждый такт до конца времён.

Тестбенч

Формат трассы тот же, что у SEQ. Это принципиально: две реализации сравниваются построчно обычным diff, и любое расхождение сразу видно.

// Тестбенч конвейерной машины. Формат трассы тот же, что у SEQ, поэтому
// трассы двух реализаций сравниваются построчно. Отличается только строка
// halt cycles=: у конвейера тактов больше на глубину конвейера, пузырьки и остановы.
module tb_pipe;

  import y86_pkg::*;

  localparam int CYCLE_LIMIT = 100000;

  logic clk;
  logic rst;

  logic        retire;
  // Адрес приходит полным словом, а печатаются младшие двенадцать разрядов:
  // памяти всего четыре килобайта, старшие разряды всегда нулевые.
  /* verilator lint_off UNUSEDSIGNAL */
  logic [63:0] retire_pc;
  /* verilator lint_on UNUSEDSIGNAL */
  logic [3:0]  retire_icode;
  logic [3:0]  retire_ifun;
  logic [2:0]  retire_stat;

  pipe dut (
    .clk          (clk),
    .rst          (rst),
    .retire       (retire),
    .retire_pc    (retire_pc),
    .retire_icode (retire_icode),
    .retire_ifun  (retire_ifun),
    .retire_stat  (retire_stat)
  );

  // Копия загруженного образа: по ней в конце ищем изменившиеся слова.
  logic [7:0] image [0:MEM_BYTES-1];

  string prog;
  int    cycles;

  initial clk = 1'b0;
  always #5 clk = ~clk;

  function automatic string stat_name(logic [2:0] s);
    case (s)
      SAOK:    stat_name = "AOK";
      SHLT:    stat_name = "HLT";
      SADR:    stat_name = "ADR";
      SINS:    stat_name = "INS";
      default: stat_name = "???";
    endcase
  endfunction

  task automatic dump_state(int n);
    logic [63:0] word;
    logic [63:0] orig;
    $display("halt cycles=%0d", n);
    $display("%%rax 0x%016h", dut.u_regs.regs[0]);
    $display("%%rcx 0x%016h", dut.u_regs.regs[1]);
    $display("%%rdx 0x%016h", dut.u_regs.regs[2]);
    $display("%%rbx 0x%016h", dut.u_regs.regs[3]);
    $display("%%rsp 0x%016h", dut.u_regs.regs[4]);
    $display("%%rbp 0x%016h", dut.u_regs.regs[5]);
    $display("%%rsi 0x%016h", dut.u_regs.regs[6]);
    $display("%%rdi 0x%016h", dut.u_regs.regs[7]);
    $display("%%r8 0x%016h",  dut.u_regs.regs[8]);
    $display("%%r9 0x%016h",  dut.u_regs.regs[9]);
    $display("%%r10 0x%016h", dut.u_regs.regs[10]);
    $display("%%r11 0x%016h", dut.u_regs.regs[11]);
    $display("%%r12 0x%016h", dut.u_regs.regs[12]);
    $display("%%r13 0x%016h", dut.u_regs.regs[13]);
    $display("%%r14 0x%016h", dut.u_regs.regs[14]);
    for (int a = 0; a < MEM_BYTES; a += 8) begin
      for (int i = 0; i < 8; i++) begin
        word[8*i +: 8] = dut.u_mem.mem[a + i];
        orig[8*i +: 8] = image[a + i];
      end
      if (word !== orig) $display("mem 0x%03h 0x%016h", a[11:0], word);
    end
  endtask

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

  initial begin
    if (!$value$plusargs("prog=%s", prog)) begin
      $display("ERROR: expected +prog=<file.hex>");
      $finish(0);
    end
    for (int i = 0; i < MEM_BYTES; i++) begin
      image[i] = 8'h00;
      dut.u_mem.mem[i] = 8'h00;
    end
    $readmemh(prog, image);
    $readmemh(prog, dut.u_mem.mem);

    cycles = 0;
    rst = 1'b1;
    @(posedge clk);
    #1 rst = 1'b0;

    forever begin
      @(negedge clk);
      cycles = cycles + 1;
      // Печатаем только настоящие инструкции: пузырьки в трассу не попадают.
      if (retire) begin
        $display("0x%03h %h%h %s", retire_pc[11:0], retire_icode, retire_ifun,
                 stat_name(retire_stat));
        if (retire_stat != SAOK) begin
          dump_state(cycles);
          $finish(0);
        end
      end
      if (cycles >= CYCLE_LIMIT) begin
        $display("ERROR: cycle limit %0d reached", CYCLE_LIMIT);
        $finish(0);
      end
    end
  end

endmodule

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

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

Прогон: SEQ против PIPE на двенадцати программах

Собираем каждую программу блока, гоняем её через три реализации и сравниваем.

$ mkdir -p build
$ for p in programs/*.ys; do
>   n=$(basename "$p" .ys)
>   zig build run -- asm "$p" --hex "build/$n.hex" -o "build/$n.yo" > /dev/null
>   zig build run -- sim "build/$n.yo" > "build/$n.zig"
>   bash hdl/run.sh seq  "build/$n.hex" > "build/$n.seq"
>   bash hdl/run.sh pipe "build/$n.hex" > "build/$n.pipe"
>   s=$(sed -n 's/^halt cycles=//p' "build/$n.seq")
>   q=$(sed -n 's/^halt cycles=//p' "build/$n.pipe")
>   ok=$(bash tools/compare-trace.sh "build/$n.zig" "build/$n.pipe" | tail -1)
>   printf '%-16s seq=%-4s pipe=%-4s %s\n' "$n" "$s" "$q" "$ok"
> done
abs_sum_cmov     seq=61   pipe=75   traces match
abs_sum          seq=64   pipe=90   traces match
bubble           seq=173  pipe=230  traces match
hazard_forward   seq=8    pipe=12   traces match
iaddq_sum        seq=32   pipe=48   traces match
load_use         seq=7    pipe=13   traces match
mispredict       seq=16   pipe=24   traces match
push_pop_rsp     seq=7    pipe=11   traces match
ret_bubbles      seq=6    pipe=13   traces match
rsum             seq=65   pipe=95   traces match
sum              seq=34   pipe=50   traces match
switchv          seq=23   pipe=41   traces match

Двенадцать программ, три реализации, ни одного расхождения в трассе. Это и есть главный результат блока: три разные машины (интерпретатор на Zig, комбинационная схема SEQ и конвейер PIPE) видны программе как одна и та же ISA. Различаются они только временем.

Программа	Инструкций	Тактов SEQ	Тактов PIPE	Лишних тактов
`sum`	34	34	50	16
`rsum`	65	65	95	30
`abs_sum`	64	64	90	26
`abs_sum_cmov`	61	61	75	14
`bubble`	173	173	230	57
`hazard_forward`	8	8	12	4
`load_use`	7	7	13	6
`mispredict`	16	16	24	8
`push_pop_rsp`	7	7	11	4
`ret_bubbles`	6	6	13	7
`iaddq_sum`	32	32	48	16
`switchv`	23	23	41	18

У SEQ число тактов равно числу инструкций, потому что за такт сигнал проходит все шесть этапов насквозь. И это ровно та причина, по которой такт SEQ приходится делать длинным: он обязан вместить сложение всех задержек. Такт PIPE короче втрое с лишним, как мы считали в уроке про принципы конвейера, а тактов у него больше. Вопрос “что быстрее” решается умножением, и вот тут нужна метрика.

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

А вот у ret_bubbles шесть инструкций и семь лишних тактов: четыре на заполнение и три за единственный ret. У load_use семь инструкций и шесть лишних: четыре плюс два останова на двух парах “загрузка и сразу использование”.

CPI: единица плюс штрафы

CPI

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

Посмотри на этап исполнения. В каждом такте через него проходит либо настоящая инструкция, либо пузырёк. Если за прогон через исполнение прошло Ci инструкций и Cb пузырьков, то тактов потребовалось примерно Ci + Cb, а значит

CPI = (Ci + Cb) / Ci = 1 + Cb / Ci

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

CPI = 1 + lp + mp + rp

Здесь lp это пузырьки на остановах по риску загрузки, mp пузырьки от ошибочно предсказанных переходов, rp пузырьки за инструкцией ret, и каждое слагаемое поделено на общее число инструкций. Цена одного события известна из прошлого урока: риск загрузки стоит один пузырёк, ошибочное предсказание два, ret три.

Виджет ниже считает эту формулу интерактивно: ты задаёшь долю загрузок в потоке инструкций и то, как часто они попадают в риск, долю условных переходов и точность их предсказания, долю возвратов, а он показывает три слагаемых и итоговый CPI. Ползунки штрафов рядом отвечают на вопрос “а если бы ret стоил не три такта, а один”. Ниже он же прогоняет выбранную программу блока на настоящем конвейере и кладёт рядом CPI по формуле и CPI по тактам: расхождение между ними это те самые такты заполнения. Последняя панель сравнивает три стратегии предсказания на переходах этой программы, и к ней мы вернёмся через два раздела.

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

Штраф	Доля инструкций	Частота случая	Пузырьков	Слагаемое
`lp`, риск загрузки	0.25	0.20	1	0.05
`mp`, ошибка предсказания	0.20	0.40	2	0.16
`rp`, возврат	0.02	1.00	3	0.06

Сумма 0.27, то есть CPI около 1.27. Обрати внимание, куда уходит основная часть: больше половины всего штрафа даёт ошибочное предсказание. Условные переходы встречаются часто, стратегия “переход всегда берётся” ошибается почти в половине случаев, и каждая ошибка стоит двух инструкций. Если вкладываться в улучшение конвейера, вкладываться надо сюда.

Теперь то же самое, но не по книжным частотам, а по нашим программам. Число ret и число ошибок предсказания видно прямо в трассе: ret это код 90, а ошибка предсказания это условный переход, за которым следующей выполненной инструкцией оказался адрес самого перехода плюс девять. Риски загрузки считаются по исходнику: пары “загрузка и следующая инструкция, читающая тот же регистр”.

Программа	`Ci`	Пузырьки load/use	Пузырьки mispredict	Пузырьки ret	`lp`	`mp`	`rp`	CPI по формуле	Тактов на инструкцию
`sum`	34	4	2	6	0.118	0.059	0.176	1.353	1.471
`rsum`	65	0	8	18	0.000	0.123	0.277	1.400	1.462
`abs_sum`	64	6	10	6	0.094	0.156	0.094	1.344	1.406
`abs_sum_cmov`	61	0	4	6	0.000	0.066	0.098	1.164	1.230
`bubble`	173	15	32	6	0.087	0.185	0.035	1.306	1.329
`iaddq_sum`	32	4	2	6	0.125	0.063	0.188	1.375	1.500
`switchv`	23	1	4	9	0.043	0.174	0.391	1.609	1.783

Два последних столбца не совпадают, и это не ошибка в расчёте. Формула сознательно игнорирует такты заполнения конвейера, а их всегда четыре. Разница между столбцами это в точности четыре, делённые на число инструкций: для bubble это 0.023, для switchv целых 0.174. Чем длиннее прогон, тем меньше вклад заполнения, и на реальной программе из миллионов инструкций им можно пренебречь.

Три наблюдения из этой таблицы.

Рекурсия дорога. У rsum штраф за возврат 0.277, больше двух третей всей платы. Шесть ret на шестьдесят пять инструкций, каждый по три пузырька: рекурсия входит в себя пять раз, и каждый вход когда-нибудь возвращается. Итеративная sum считает то же самое двумя возвратами, и rp у неё падает до 0.176.

Таблица переходов дороже всего. У switchv штраф за возврат 0.391, и CPI по формуле 1.609. Причина в том, что прямого перехода по регистру в Y86-64 нет, и таблица переходов реализована через pushq адреса и ret. Инструкция ret тут работает косвенным переходом, и конвейер платит за неё полную цену. Ровно поэтому настоящие процессоры держат отдельный предсказатель адреса возврата.

Экономия инструкций и экономия тактов это разные вещи. Расширение iaddq складывает с регистром непосредственное значение, поэтому константы 8 и 1 больше не нужно раскладывать по регистрам заранее. Из пролога уходят две irmovq, тело цикла не меняется вовсе: sum выполняет 34 инструкции, iaddq_sum только 32. Но штрафы у них одинаковые до последнего пузырька, поэтому выигрыш в тактах ровно тот же, что и в инструкциях: 50 против 48. Зато CPI у iaddq_sum выше, чем у sum, потому что те же двенадцать пузырьков делятся на меньшее число инструкций. Хороший повод не путать CPI с производительностью.

Переход против условной пересылки

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

Тело цикла с переходом выглядит так:

asloop: mrmovq (%rdi), %r10     # x
        andq %r10, %r10         # флаги по x
        jge aspos               # x неотрицательный, брать как есть
        irmovq $0, %r11
        subq %r10, %r11         # %r11 равен нулю минус x
        rrmovq %r11, %r10
aspos:  addq %r10, %rax

А тело цикла с пересылкой так:

acloop: mrmovq (%rdi), %r10     # x
        irmovq $0, %r11
        subq %r10, %r11         # %r11 равен нулю минус x, флаги по нему
        cmovg %r11, %r10        # минус x положителен, значит x был меньше нуля
        addq %r10, %rax

Пятнадцать тактов разницы раскладываются на три части.

Три такта дают сами инструкции. Версия с переходом выполняет 64 инструкции, версия с пересылкой 61. Это неожиданно: обычно условная пересылка считает обе ветки и потому выполняет больше работы. Посчитай по телам циклов. Версия с пересылкой тратит пять инструкций на каждый элемент, всегда. Версия с переходом тратит четыре на неотрицательном числе и семь на отрицательном, потому что там разворачивается ветка с отрицанием. В массиве три отрицательных числа из шести, так что она экономит три инструкции на положительных и теряет шесть на отрицательных. Итого плюс три.

Шесть тактов дают риски загрузки. В версии с переходом за mrmovq сразу идёт andq %r10, %r10, читающая только что загруженный регистр. Это риск загрузки на каждой из шести итераций. В версии с пересылкой между загрузкой и её первым использованием вклинилась irmovq $0, %r11, и риска нет вообще. Обрати внимание: это не заслуга cmov, это заслуга порядка инструкций. Ту же одну инструкцию можно было бы переставить и в версии с переходом.

Шесть тактов дают ошибки предсказания. Версия с переходом ошибается пять раз, версия с пересылкой два. Пять ошибок это je на входе в цикл (не берётся), три jge внутри цикла (на отрицательных числах не берутся) и последний jne на выходе из цикла. У версии с пересылкой остались только je на входе и jne на выходе, а внутренний переход исчез вместе с ветвлением.

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

Три стратегии предсказания на бумаге

Наша машина предсказывает “переход берётся всегда”. Это не единственный вариант, и цену каждого можно посчитать, не запуская ничего. Возьмём abs_sum, потому что у неё есть переходы всех сортов.

Условных переходов в прогоне тринадцать. Разложим их по адресу цели и по фактическому поведению:

Переход	Куда	Сколько раз	Берётся	Не берётся
`je asdone`	вперёд	1	0	1
`jge aspos`	вперёд	6	3	3
`jne asloop`	назад	6	5	1

Всего берётся восемь раз, не берётся пять.

Всегда берётся. Ошибка на каждом невзятом переходе: пять ошибок, десять пузырьков. Точность 8 из 13, то есть 62 процента. Это то, что делает наша машина.

Никогда не берётся. Ошибка на каждом взятом: восемь ошибок, шестнадцать пузырьков. Точность 5 из 13, то есть 38 процентов. Хуже, и понятно почему: цикл крутится назад пять раз подряд, и стратегия ошибается на каждом витке.

Назад берётся, вперёд не берётся. Переход назад почти всегда виток цикла, переход вперёд часто выход из условия. Считаем: je asdone вперёд и не берётся, угадали. Из шести jge aspos вперёд угадали три невзятых и промахнулись на трёх взятых. Из шести jne asloop назад угадали пять взятых и промахнулись на одном невзятом. Итого четыре ошибки, восемь пузырьков. Точность 9 из 13, то есть 69 процентов.

Остальные штрафы от стратегии не зависят: программа выполняет те же 64 инструкции, те же шесть тактов на два ret и те же шесть на риски загрузки, плюс четыре на заполнение. База получается 80 тактов, а дальше добавляются пузырьки предсказания:

Стратегия	Ошибок	Пузырьков	Всего тактов
всегда берётся	5	10	90
никогда не берётся	8	16	96
назад берётся, вперёд нет	4	8	88

Строка “всегда берётся” совпала с измеренными 90 тактами, значит расчёт верен. Третья стратегия выигрывает у нашей всего два такта на этой программе, но на длинных циклах разрыв растёт: там доля переходов назад выше.

Есть и цена. Стратегия “назад берётся, вперёд нет” требует сравнить valC с valP в этапе выборки, а после ошибки уметь восстановиться в обе стороны, значит через конвейер надо тащить оба адреса, а не один. У нашей машины сейчас едет только valP внутри valA. Это и есть содержание домашнего задания.

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

Чего в этой машине нет

Конвейер работает, трассы совпадают, CPI посчитан. Честно перечислим, что осталось за кадром.

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

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

Что делают настоящие процессоры. Пятиступенчатый конвейер вроде нашего это середина восьмидесятых: MIPS, SPARC, Intel i486. Его потолок жёсткий: не больше одной инструкции за такт, CPI никогда меньше единицы. Дальше индустрия пошла в суперскалярность (выбирать и исполнять несколько инструкций за такт, отчего вместо CPI стали мерить обратную величину IPC) и во внеочередное исполнение: инструкции исполняются по мере готовности операндов, возможно в другом порядке, а видимый результат всё равно собирается в порядке программы. Это следующий уровень той же идеи, что двигала весь блок: снаружи ISA, внутри что угодно, лишь бы поведение совпадало. Разбирать внеочередной процессор мы будем в уроке про модель современного процессора, уже с точки зрения того, кто пишет код, а не проектирует железо.

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

Практика

Задача собирает вместе весь урок в одном модуле. Тебе дан скелет control.sv с полным списком портов и объявленными константами, а внутри шесть выходов, прибитых к нулю. Собери четыре условия (load_use, ret_in_pipe, mispredicted, exception) и шесть управляющих сигналов из них. Скрытый тестбенч подаёт двенадцать ситуаций по порядку: спокойное состояние, две формы риска загрузки, загрузку без использования, ret на каждом из трёх этапов, ошибочное и верное предсказание, комбинацию “риск загрузки плюс ret”, исключение в памяти и исключение в записи. Десятая ситуация и есть комбинация B: одиннадцать строк совпадут даже у наивного D_bubble, а на ней он выдаст Db=1 там, где нужен ноль.

Упражнения

CHK-1★★

Напиши на ассемблере Y86-64 две программы: одну, вызывающую комбинацию A (несработавший переход, а по адресу за ним ret), другую, вызывающую комбинацию B (загрузка в %rsp, следом ret). Прогони обе через hdl/run.sh pipe и сверь трассу с Zig-симулятором. Затем убери из D_bubble оговорку && !load_use, пересобери и покажи, что именно ломается: какая из двух программ падает, на какой инструкции и почему.

CHK-2★★★

Собери дешёвый вариант конвейера без пробросов (форма упражнения 4.53 книги): в forward.sv оставь только чтение из регистрового файла и особый случай call/jXX, а все зависимости по данным закрывай остановом до тех пор, пока инструкция, вырабатывающая значение, не пройдёт запись. Управляющую логику придётся переписать: комбинаций особых случаев станет больше, потому что теперь останов вызывает почти каждая пара соседних инструкций. Разбери их так же систематически, как мы разбирали комбинации A и B. Прогони все двенадцать программ, заполни таблицу “тактов с пробросами, тактов без” и посчитай, сколько процентов производительности стоит логика продвижения.

CHK-3★★★

Наш конвейер тормозит при риске загрузки всегда, но иногда это лишнее (форма упражнения 4.57). Если вторая инструкция не считает по загруженному значению, а просто кладёт его в память (rmmovq или pushq), значение нужно ей только в этапе памяти, и его можно пробросить прямо туда, в поле valA регистра M. Запиши новое условие риска загрузки, которое не срабатывает в этом случае, и объясни, почему popq %rdx с последующей rmmovq %rax, 0(%rdx) под это послабление не подходит. Найди в программах блока место, где новый путь даёт выигрыш (подсказка: посмотри на switchv), и посчитай, сколько тактов он там экономит.

CHK-4★★★

Реализуй две другие стратегии предсказания (формы упражнений 4.55 и 4.56): “условные переходы не берутся никогда, безусловные и call берутся всегда” и “назад берётся, вперёд не берётся”. Со второй придётся придумать, как дотащить до регистра M оба адреса, valC и valP, иначе восстановиться после ошибки будет нечем. Сравнение знаковое: беззнаковой арифметики в Y86-64 нет. Перед запуском посчитай на бумаге ожидаемое число тактов для bubble и switchv тем же способом, что мы применили к abs_sum, а потом сверь с настоящим прогоном.

CHK-5★★

Расширение iaddq уже поддержано в нашем конвейере (форма упражнения 4.54). Выясни точно, чего оно стоило: пройди по control.sv, forward.sv и по этапам, выпиши все места, где IIADDQ должен был бы упоминаться, и объясни, почему в управляющей логике его нет ни разу. Потом сломай его нарочно: убери IIADDQ из таблицы dstE в декодировании, прогони iaddq_sum и покажи по трассе, в какой момент результат разошёлся с Zig-симулятором.

CHK-6★★★

Регистровый файл у нас с двумя портами записи, но второй порт нужен ровно одной инструкции, popq (форма упражнения 4.58). Слей оба порта в один: значение и номер регистра выбираются мультиплексором, а popq управляющая логика разворачивает в пару шагов, эквивалентную iaddq $8, %rsp и mrmovq -8(%rsp), rA. Порядок этих шагов важен, объясни почему, вспомнив разбор popq %rsp. Прогони push_pop_rsp и убедись, что %rsp в конце равен 0x123, а не 0x200. В конце сравни три версии пузырьковой сортировки по тактам (форма упражнения 4.59) и объясни, за счёт чего выигрывает лучшая.

Итоги

Конвейерный регистр это элемент с тремя режимами: обычная загрузка, останов и пузырёк. Приоритет в блоке always_ff всегда один: сброс, потом пузырёк, потом останов, потом загрузка. Останов не пишется кодом вовсе, он и есть отсутствие присваивания.
Логика продвижения это приоритетная цепочка if по пяти точкам конвейера, и порядок веток в ней кодирует возраст инструкций: чем ближе точка к началу конвейера, тем свежее значение.
Управляющая логика это четыре булевых условия (load_use, ret_in_pipe, mispredicted, exception) и шесть сигналов, собранных из них. Шестьдесят пять строк на весь конвейер.
Одновременно могут возникнуть только две пары особых случаев, и обе связаны с ret в декодировании. Комбинация A обрабатывается сама собой, комбинация B требует оговорки && !load_use в D_bubble, иначе ступень D получает разом останов и пузырёк.
Отмена несработавшей условной пересылки в конвейере переезжает из записи в исполнение: номер регистра уходит в пробросы и обязан быть окончательным уже там.
Регистр флагов в конвейере пишет этап исполнения, а не записи, иначе следующая инструкция сравнивала бы устаревшее состояние.
Все двенадцать программ блока дают на PIPE ту же трассу, что на SEQ и на Zig-симуляторе. Различается только число тактов, и это доказательство того, что ISA скрывает реализацию.
CPI равен единице плюс три штрафа: lp за риски загрузки, mp за ошибки предсказания, rp за возвраты. Формула игнорирует такты заполнения конвейера, поэтому на коротких программах она занижает результат ровно на четыре такта, делённые на число инструкций.
На книжном наборе частот CPI выходит около 1.27, и больше половины штрафа даёт ошибочное предсказание. На наших программах картина та же: дороже всего обходятся switchv с таблицей переходов через ret и рекурсивная rsum.
Версия abs_sum с условной пересылкой быстрее версии с переходом на пятнадцать тактов: шесть дают ошибки предсказания, шесть риски загрузки (из-за порядка инструкций, а не из-за самой пересылки) и три лишние инструкции.
Стратегия “назад берётся, вперёд нет” на abs_sum даёт 88 тактов против наших 90 и против 96 у стратегии “никогда не берётся”, но требует тащить через конвейер оба адреса.
Чего в машине нет: многотактовых инструкций, настоящего интерфейса к памяти с кэшем и промахами, суперскалярности и внеочередного исполнения. Приёмы для первых двух те же самые, останов и продвижение.

Дальше

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

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

домашка

Домашка

Собери вариант PIPE без пробросов, где все зависимости по данным закрываются остановом, и посчитай на программах урока, во сколько тактов обошёлся отказ от продвижения.L
Добавь путь продвижения загрузки в поле valA регистра M, перепиши условие load/use так, чтобы оно не срабатывало на сохранении, и покажи выигрыш на switchv.L
Реализуй стратегию предсказания «назад берётся, вперёд не берётся» и сверь настоящее число тактов на всех двенадцати программах с бумажным расчётом.L