PIPE: риски, продвижение и остановы

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

Цели урока

• Понять, зачем машине SEQ+ и почему выбор нового PC переезжает из конца такта в его начало.
• Свободно читать имена сигналов конвейера: чем D_icode отличается от d_srcA, а M_valE от m_valM.
• Объяснить стратегию предсказания “переход берётся”, знать её цену для jXX и почему для ret предсказывать бесполезно.
• Увидеть риск по данным на настоящей программе и разобрать его такт за тактом.
• Различать два инструмента конвейера, пузырёк и останов, и понимать, почему они не взаимозаменяемы.
• Знать все пять источников продвижения и их порядок приоритета, уметь объяснить, что сломается при перестановке.
• Разобрать риск загрузки и использования и понять, почему тут продвижение бессильно.
• Посчитать цену ret в три пузырька и цену ошибочного предсказания в два пузырька.
• Понимать, как исключение доезжает до этапа записи в порядке программы и почему более молодым инструкциям запрещают менять состояние машины.
• Разложить число тактов любой программы на три слагаемых: инструкции, заполнение конвейера, штрафы.

Идея: пять инструкций в полёте

Машина SEQ из урока про execute, memory и write back исполняла ровно одну инструкцию за такт. Все шесть этапов происходили внутри одного такта, и вопрос “а что если следующая инструкция читает регистр, который пишет текущая” не возникал вовсе: к началу следующего такта запись уже случилась.

Конвейер этот вопрос порождает. Разложим пять инструкций по пяти этапам и посмотрим на один момент времени:

такт 3:   F: addq %rbx, %rcx
          D: addq %rax, %rbx      <- читает %rbx
          E: irmovq $10, %rax     <- вычисляет %rax
          M: irmovq stack, %rsp
          W: (пусто)

Инструкция в этапе декодирования хочет прочитать %rax, а %rax считает соседка, которая сейчас сидит в этапе исполнения. До регистрового файла её результат доедет только через два такта. Регистровый файл отдаст старое значение, и машина посчитает неправильно.

Это и называется риском. В Y86-64 у них пять источников, и CS:APP перечисляет их честно:

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

Два из пяти пунктов решаются сами: флаги и память. Регистры и счётчик команд разбираем подробно, а состояние машины чиним по дороге.

SEQ+ и перенос выбора PC в начало такта

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

always_comb begin
  case (icode)
    ICALL:   new_pc = valC;
    IRET:    new_pc = valM;
    IJXX:    new_pc = Cnd ? valC : valP;
    default: new_pc = valP;
  endcase
end

Посмотри на входы этого блока. Чтобы выбрать адрес, нужны icode, Cnd, valC, valM и valP. Всё это результаты текущей инструкции, и всё это появляется по ходу такта. То есть выбор адреса стоит в самом хвосте длинного комбинационного пути, а следующий такт начинается с обращения к памяти по этому адресу. Для конвейера это катастрофа: этапу выборки пришлось бы ждать конца предыдущего такта.

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

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

// Откуда брать адрес. Два случая, когда предсказание оказалось неверным:
// переход, который не взялся, и возврат из процедуры.
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

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

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

Пять этапов разделены четырьмя границами, но регистров пять: один хранит адрес для выборки, четыре хранят всё, что этап передаёт следующему. Их зовут по первым буквам этапов: F, D, E, M, W.

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;

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

Теперь соглашение об именах, без которого дальше ничего не прочитать. Оно короткое, и его стоит запомнить:

• заглавная буква и подчёркивание это содержимое конвейерного регистра. D_icode это код инструкции, которая лежит в регистре D, то есть уже выбрана и ждёт декодирования.
• строчная буква и подчёркивание это сигнал, вычисленный внутри соответствующего этапа прямо сейчас, в текущем такте. d_srcA это номер регистра, который блок декодирования вычислил по D_icode в этом такте.

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

Дальше по конвейеру та же логика. e_valE это свежий результат ALU, он появился в этом такте и ещё нигде не защёлкнут. M_valE это тот же результат, но уже через один фронт такта: он лежит в регистре M. m_valM это слово, которое память отдаёт прямо сейчас, а W_valM это оно же тактом позже. Пары “строчная и заглавная” описывают одно значение в два соседних момента времени, и именно на этом построено всё продвижение.

Одна тонкость: у поля M_valA две работы. У обычных инструкций там операнд, а у call и jXX там valP, адрес следующей инструкции. Отдельного поля valP регистру M не нужно, и в блоке продвижения ты увидишь, откуда это valP туда попадает.

Предсказание: переход берётся

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

Проблема только с jXX и ret.

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

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

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

С ret предсказывать просто нечего. Адрес возврата лежит в памяти на вершине стека, и узнать его раньше, чем ret дойдёт до этапа памяти, невозможно. Формально мы кладём в F_predPC значение valP, но это не догадка, а заглушка: всё, что выбрано после ret, будет выброшено. Как именно, разберём ниже.

Риск по данным: цепочка зависимостей

Пора смотреть на настоящую программу. В эталоне лежит programs/hazard_forward.ys, и она написана нарочно так, чтобы каждая инструкция читала регистр, который предыдущая только что записала.

        .pos 0
init:   irmovq stack, %rsp
        irmovq $10, %rax
        addq %rax, %rbx         # читает %rax, записанный такт назад
        addq %rbx, %rcx         # читает %rbx
        addq %rcx, %rdx         # читает %rcx
        rrmovq %rdx, %rsi       # читает %rdx
        addq %rsi, %rax         # читает %rsi
        halt

        .pos 0x200
stack:

Ассемблер из урока про ассемблер на Zig даёт такой листинг:

0x000: 30f40002000000000000 | init:   irmovq stack, %rsp
0x00a: 30f00a00000000000000 |         irmovq $10, %rax
0x014: 6003                 |         addq %rax, %rbx
0x016: 6031                 |         addq %rbx, %rcx
0x018: 6012                 |         addq %rcx, %rdx
0x01a: 2026                 |         rrmovq %rdx, %rsi
0x01c: 6060                 |         addq %rsi, %rax
0x01e: 00                   |         halt

Восемь инструкций. На SEQ это ровно восемь тактов. Разложим их по конвейеру и посмотрим такт за тактом, кто у кого читает.

такт 0   F: irmovq stack
такт 1   F: irmovq $10      D: irmovq stack
такт 2   F: addq %rax,%rbx  D: irmovq $10     E: irmovq stack
такт 3   F: addq %rbx,%rcx  D: addq %rax,%rbx E: irmovq $10      M: irmovq stack
такт 4   F: addq %rcx,%rdx  D: addq %rbx,%rcx E: addq %rax,%rbx  M: irmovq $10     W: irmovq stack
такт 5   F: rrmovq          D: addq %rcx,%rdx E: addq %rbx,%rcx  M: addq %rax,%rbx W: irmovq $10
такт 6   F: addq %rsi,%rax  D: rrmovq         E: addq %rcx,%rdx  M: addq %rbx,%rcx W: addq %rax,%rbx
такт 7   F: halt            D: addq %rsi,%rax E: rrmovq          M: addq %rcx,%rdx W: addq %rbx,%rcx

Смотрим на такт 3. В этапе декодирования сидит addq %rax, %rbx, её d_srcA равен номеру %rax. В этапе исполнения сидит irmovq $10, %rax, её e_dstE равен номеру %rax, а e_valE равен десяти. Значение существует, оно вот здесь, в соседнем этапе. Оно просто не записано в регистровый файл и запишется только через два такта.

Тот же расклад повторяется на тактах 4, 5, 6 и 7. Каждый раз читатель отстаёт от писателя ровно на один этап, и каждый раз нужное значение уже посчитано соседним этапом.

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

Покрути лестницу в виджете и посмотри, что происходит при выключенном продвижении. Программа честно доедет до halt, но в регистрах будут нули там, где ожидалась десятка: виджет положит две колонки рядом, “получилось” и “должно быть”.

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

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

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

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

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

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_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;

Полный модуль управления с таблицей “какая ситуация какие сигналы поднимает” ты напишешь в следующем уроке, когда будешь собирать PIPE на Verilog целиком. Здесь нам нужны только сами условия, чтобы понимать цену каждой ситуации в тактах.

Продвижение из пяти точек

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

Портов записи у регистрового файла два: порт E принимает результат ALU, порт M принимает слово из памяти. Значит, у каждой летящей инструкции есть до двух свежих результатов. Инструкция в этапе исполнения дала результат ALU. Инструкция в этапе памяти дала и результат ALU, и прочитанное слово. Инструкция в этапе записи дала то же самое, но тактом позже.

Считаем: этап исполнения даёт один источник, этап памяти два, этап записи два. Итого пять.

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

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

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

Прежде чем читать модуль, напомню пакет с константами, файл hdl/lib/y86_pkg.sv. Ты написал его в уроке про вентили и комбинационную логику, и с тех пор каждый модуль подтягивает его строкой import y86_pkg::*. Обрати внимание на обёртку из директив линтера вокруг пакета: любой отдельный модуль берёт из него горстку констант, и без этой обёртки verilator ругался бы на все остальные.

// Общие константы 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 */

А вот и сам блок продвижения целиком, файл hdl/pipe/forward.sv эталона:

// Блок пробросов, рисунок 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, и это не стилистика. Именно цепочка задаёт приоритет: первое совпавшее условие выигрывает, остальные даже не рассматриваются. Если написать пять независимых assign, схема получит несколько драйверов на один провод, и это будет ошибка.

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

Особый случай для порта A. Он стоит первым, до всех пяти источников. У call и jXX через порт A едет не операнд, а valP. Для call это адрес возврата, который этап памяти положит на стек. Для jXX это адрес следующей инструкции, точка отката, если предсказание не сбылось: как раз то M_valA, которое ты видел в выборе f_pc. У порта B такого случая нет, поэтому вторая половина модуля короче на одну строку.

Про RNONE тут ничего не проверяется. Значение 4'hF означает “регистра нет”. Если инструкция ничего не пишет, её порт назначения равен RNONE; если инструкция ничего не читает, её d_srcA тоже равен RNONE. Совпадение “нет с нет” даст на выходе мусор, но этот выход никто не прочитает, потому что этап исполнения не станет использовать операнд, которого у инструкции нет. Книга поступает так же, и лишняя проверка только удлинила бы критический путь.

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

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

В SEQ отмену делал этап записи, и этого хватало. В конвейере не хватает: номер регистра назначения уходит в блок продвижения раньше, чем инструкция дойдёт до записи, и если не отменить его здесь, машина продвинет значение, которого не должно быть. Такая ошибка тихая и вылезает только на программе, где сразу за cmov идёт зависимость от его регистра. Ловит её программа abs_sum_cmov.ys из эталона, и это ровно тот случай, ради которого её туда положили.

Практика

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

Риск загрузки и использования

Продвижение решает почти всё. Почти.

        .pos 0
init:   irmovq stack, %rsp
        irmovq data, %rdi
        mrmovq (%rdi), %rax     # %rax равен 7
        addq %rax, %rax         # использование сразу за загрузкой
        mrmovq 8(%rdi), %rbx    # %rbx равен 35
        addq %rbx, %rax
        halt

        .align 8
data:   .quad 7
        .quad 35

        .pos 0x200
stack:

Разложим первую пару по тактам. Инструкция mrmovq (%rdi), %rax в такте 4 сидит в этапе исполнения: там она считает адрес, но само слово из памяти ещё не читала. Читатель addq %rax, %rax в этом же такте сидит в этапе декодирования и хочет %rax немедленно, потому что в следующем такте он попадёт в этап исполнения и ALU должно получить операнд.

Значение появится в такте 5, когда mrmovq дойдёт до этапа памяти. Продвигать в такте 4 нечего: значение ещё не существует нигде в машине. Провода в прошлое не бывает.

Это риск загрузки и использования, и лечится он единственным способом: потребителя надо задержать на один такт. Тогда в следующем такте он окажется в том же этапе декодирования, но mrmovq уже будет в этапе памяти, и сработает продвижение из m_valM.

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

такт 3   F: addq %rax,%rax    D: mrmovq (%rdi)   E: irmovq data     M: irmovq stack
такт 4   F: mrmovq 8(%rdi)    D: addq %rax,%rax  E: mrmovq (%rdi)   M: irmovq data
         оба стоят               оба стоят          load/use, дальше пузырёк
такт 5   F: mrmovq 8(%rdi)    D: addq %rax,%rax  E: пузырёк         M: mrmovq (%rdi)
         теперь m_valM равен семи, продвижение сработало на оба порта

В такте 5 у addq %rax, %rax оба источника, и d_srcA, и d_srcB, равны %rax, поэтому оба порта берут одно и то же m_valM. Дальше конвейер идёт как ни в чём не бывало, ровно до второй пары mrmovq и addq, где всё повторяется.

Итого: семь инструкций, два останова. Проверяем на модели:

$ bash hdl/run.sh pipe programs/load_use.hex
0x000 30 AOK
0x00a 30 AOK
0x014 50 AOK
0x01e 60 AOK
0x020 50 AOK
0x02a 60 AOK
0x02c 00 HLT
halt cycles=13
%rax 0x0000000000000031
...

Тринадцать тактов против семи на SEQ. Разница раскладывается на четыре такта заполнения конвейера и два потерянных такта на два останова.

Хорошая новость: этот штраф программист может убрать сам. Если переставить обе загрузки перед обоими сложениями, между загрузкой и использованием окажется чужая инструкция, и останавливаться будет не из-за чего. Это домашнее задание, и число тактов там получится другое.

ret и три пузырька

Возврат из процедуры дороже всего.

        .pos 0
init:   irmovq stack, %rsp
        call f
        addq %rax, %rax
        halt

f:      irmovq $21, %rax
        ret

        .pos 0x200
stack:

Адрес возврата лежит в памяти. Прочитать его можно только в этапе памяти, а воспользоваться им этап выборки сможет только после того, как значение защёлкнется в регистр W: вспомни выбор f_pc, там стоит W_valM. Между тактом, в котором ret выбран, и тактом, в котором известен адрес возврата, проходит три такта. Всё это время выбирать нечего.

Правило такое: пока ret находится в любом из трёх этапов, D, E или M, этап выборки стоит, а в этап декодирования идут пузырьки.

такт 3   F: ret              D: irmovq $21     E: call         M: irmovq stack
такт 4   F: стоит            D: ret            E: irmovq $21   M: call
такт 5   F: стоит            D: пузырёк        E: ret          M: irmovq $21
такт 6   F: стоит            D: пузырёк        E: пузырёк      M: ret
такт 7   F: addq %rax,%rax   D: пузырёк        E: пузырёк      M: пузырёк   W: ret

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

$ bash hdl/run.sh pipe programs/ret_bubbles.hex
0x000 30 AOK
0x00a 80 AOK
0x016 30 AOK
0x020 90 AOK
0x013 60 AOK
0x015 00 HLT
halt cycles=13
%rax 0x000000000000002a
...
mem 0x1f8 0x0000000000000013

Шесть инструкций дают тринадцать тактов: шесть плюс четыре на заполнение плюс три на ret. На SEQ было шесть.

Последняя строка трассы это единственное изменившееся слово памяти: call положил на стек адрес 0x013, адрес инструкции сразу за собой. Он же приехал обратно через W_valM и стал новым значением f_pc.

Заметь порядок строк в трассе: 0x013 идёт после 0x020. Это не ошибка, это программа: call уходит в процедуру, а addq по адресу 0x013 исполняется после возврата. Трасса печатает инструкции в порядке завершения, а он совпадает с порядком программы. Это свойство конвейера, на котором держится весь следующий раздел про исключения.

Реальные процессоры этот штраф давно научились обходить: у них есть отдельный стек адресов возврата, который угадывает адрес по последнему call. У нас его нет, и в этом смысле ret в Y86-64 честно показывает, откуда взялась целая область инженерии.

Ошибочно предсказанный переход и два пузырька

Последняя из трёх ситуаций. Программа mispredict.ys устроена так, чтобы показать обе стороны стратегии “переход берётся”: один переход вперёд, который не берётся, и один переход назад в цикле, который берётся почти всегда.

        .pos 0
init:   irmovq stack, %rsp
        irmovq $1, %rax
        andq %rax, %rax         # флаг нуля сброшен
        je never                # вперёд и не берётся, предсказание ошиблось
        irmovq $2, %rbx
        jmp loop
never:  irmovq $3, %rbx
loop:   irmovq $3, %rcx
        irmovq $1, %r8
back:   subq %r8, %rcx
        jne back                # назад и берётся, пока счётчик не ноль
        addq %rbx, %rax
        halt

        .pos 0x200
stack:

Условие проверяется в этапе исполнения: там ALU и там же читаются флаги, результат это сигнал e_Cnd. К этому моменту этап выборки уже успел выбрать две инструкции по предсказанному адресу. Обе неправильные, обе надо убить.

такт 4   F: irmovq $3,%rbx   D: je never       E: andq %rax,%rax
         выбрано по адресу never, то есть по предсказанию
такт 5   F: irmovq $3,%rcx   D: irmovq $3,%rbx E: je never
         e_Cnd равен нулю, предсказание ошиблось, оба пузырька подняты
такт 6   F: irmovq $2,%rbx   D: пузырёк        E: пузырёк      M: je never
         f_pc взят из M_valA, то есть из valP несработавшего перехода

Убить надо ровно две: ту, что в этапе декодирования, и ту, что в этапе выборки. Первая гасится пузырьком в регистр E, вторая пузырьком в регистр D. Инструкция, которая была в этапе исполнения, это сам переход, и он честно доезжает до конца, чтобы отдать valP этапу выборки.

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

Теперь вторая половина программы. Цикл back крутится три раза: subq уменьшает счётчик с трёх до нуля, jne исполняется три раза и берётся дважды. Оба взятых перехода предсказаны верно и не стоят ничего. Третий, на выходе из цикла, не берётся и стоит два такта.

$ bash hdl/run.sh pipe programs/mispredict.hex
...
halt cycles=24
%rax 0x0000000000000003
%rcx 0x0000000000000000
%rdx 0x0000000000000000
%rbx 0x0000000000000002
...

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

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

Исключения в конвейере

Осталось разобраться с последним источником рисков. Инструкция может отвалиться: halt останавливает машину, обращение за границу памяти даёт код ADR, неизвестный код инструкции даёт INS. В SEQ это было просто: инструкция одна, отвалилась и всё. В конвейере за сбойной инструкцией уже летят три другие, и они не должны ничего испортить.

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

Код состояния едет вместе с инструкцией. Ты видел поле stat в каждом конвейерном регистре. Ошибку замечает этап выборки или этап памяти, а объявляет её машина только тогда, когда инструкция доезжает до этапа записи. Пока она едет, машина работает как обычно.

Более молодым инструкциям запрещено менять состояние. Как только исключение видно в этапе памяти или в этапе записи, машина перекрывает все каналы изменения состояния:

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;

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

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

Именно поэтому трасса конвейера строка в строку совпадает с трассой симулятора на Zig и с трассой SEQ. Отличается только строка с числом тактов.

В тестбенче есть одна хитрость. Пока регистр 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;

Флаг w_loaded помнит, приняла ли ступень W новое содержимое на последнем фронте. Поле valid отличает настоящий nop от пузырька. Ни того ни другого в книге нет, они нужны только трассе, но без них трассы двух реализаций не сойдутся.

Арифметика тактов

Теперь можно собрать всё в одну формулу. Число тактов конвейерной машины раскладывается на три слагаемых:

такты = инструкции + заполнение + штрафы

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

Проверим на всех пяти программах эталона. Числа сняты запуском, а не выведены:

Разбираем колонку штрафов по каждой строке.

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

load_use: два. Две пары “загрузка и сразу использование”, по одному такту на каждую.

ret_bubbles: три. В программе один ret, и он стоит ровно три пузырька. А вот call не стоит ничего: его адрес назначения записан прямо в инструкции, так что этап выборки не гадает, а знает.

mispredict: четыре. Два ошибочных предсказания по два такта: je вперёд, который не взялся, и последний jne на выходе из цикла. Два верных предсказания взятого jne внутри цикла и один jmp не стоили ничего.

sum: двенадцать. Самая интересная строка, разложим её полностью. В программе четыре итерации цикла, и в каждой стоит пара mrmovq (%rdi), %r10 и addq %r10, %rax. Это четыре такта на риск загрузки и использования. Дальше два возврата из процедур, sum и main, по три такта каждый, итого шесть. И один jne на выходе из цикла, два такта. Четыре плюс шесть плюс два равно двенадцать.

$ bash hdl/run.sh seq programs/sum.hex | grep cycles
halt cycles=34
$ bash hdl/run.sh pipe programs/sum.hex | grep cycles
halt cycles=50

Тридцать четыре инструкции за пятьдесят тактов. Отношение равно примерно 1.47, и это CPI нашей машины на этой программе. Единица плюс штрафы. Разложением этого числа по вкладам и сравнением стратегий предсказания мы займёмся в следующем уроке.

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

Упражнения

        .pos 0
init:   irmovq stack, %rsp
        irmovq data, %rdi
        mrmovq (%rdi), %rax
        addq %rax, %rbx
        rrmovq %rbx, %rcx
        halt

        .align 8
data:   .quad 5

        .pos 0x200
stack:

Итоги

• Конвейер держит пять инструкций в полёте, и они спорят за общие ресурсы. Источников риска пять: регистры, счётчик команд, флаги, память и состояние машины. Память и флаги в Y86-64 решаются сами, остальное надо чинить.
• SEQ+ переносит выбор нового PC из конца такта в начало. Это перетактовка схемы: вместо “вычислить адрес и запомнить” получается “запомнить входы и вычислить адрес”. Поведение то же, длинный путь разрезан там, где нужно конвейеру.
• Конвейерных регистров пять: F, D, E, M, W. Заглавная буква с подчёркиванием это содержимое регистра, строчная это сигнал внутри этапа. Пара e_valE и M_valE описывает одно значение в два соседних такта.
• Стратегия предсказания у нас одна: переход берётся, идём на valC. Для call это не догадка, а точное знание. Для ret предсказывать нечего, адрес лежит в памяти.
• Обычный риск по данным лечится продвижением и стоит ноль тактов. Источников ровно пять: e_valE, m_valM, M_valE, W_valM, W_valE, и они проверяются именно в этом порядке, от самой молодой инструкции к самой старой.
• Порядок приоритета не украшение. Если два источника метят в один регистр, читатель обязан увидеть значение более молодого писателя, иначе программа с двумя записями в один регистр посчитает неправильно.
• Пузырёк и останов делают разное. Пузырёк очищает регистр и отменяет работу. Останов замораживает регистр и откладывает работу. При риске загрузки и использования нужны оба сразу.
• Риск загрузки и использования продвижением не лечится: значение появляется на такт позже, чем нужно. Цена один такт, и программист может убрать её перестановкой инструкций.
• ret стоит три пузырька, потому что адрес возврата известен только в этапе записи. Ошибочное предсказание стоит два, потому что за время от выборки перехода до вычисления условия успевают войти ровно две инструкции.
• Исключение едет по конвейеру вместе со своей инструкцией и объявляется только в этапе записи. Всё, что моложе, теряет право менять регистры, память и флаги. Порядок программы соблюдается сам, потому что конвейер не переупорядочивает инструкции.
• Число тактов раскладывается на три слагаемых: инструкции, четыре такта заполнения, сумма штрафов. Заполнение платится один раз, штрафы каждый раз.

Дальше

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

В следующем уроке появится управляющая логика: таблица “какая ситуация какие сигналы поднимает”, разбор комбинаций, когда две ситуации случаются в одном такте, и топ-модуль PIPE, который гоняет все двенадцать программ эталона с той же трассой, что и SEQ. А потом мы посчитаем CPI по-настоящему: разложим его по вкладам, сравним стратегии предсказания и посмотрим, сколько тактов стоит ветвление в программе abs_sum, если переписать её на условную пересылку.