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

Принципы конвейера: задержка и пропускная способность

senior~80 мин

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

Принципы конвейера: задержка и пропускная способность

В прошлом уроке ты собрал SEQ целиком и увидел, как одна инструкция за один такт проходит fetch, decode, execute, memory, write back и pc update. Схема работает, программы идут, трасса сходится с симулятором. И она медленная, причём медленная по одной конкретной причине: такт обязан быть длиннее, чем самый длинный путь сигнала через всю машину, а этот путь идёт насквозь через все шесть блоков. Пока execute считает, память простаивает. Пока память отвечает, ALU уже никому не нужен. Этот урок про то, как перестать ждать: разрезать длинный путь регистрами и запустить в машину несколько инструкций одновременно. Считать будем на числах, каждое из которых ты сможешь проверить сам.

Цели урока

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

Идея: две величины, а не одна

“Быстрее” это не одно число, а два, и они тянут в разные стороны.

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

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

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

Дальше весь урок это арифметика вокруг этих двух величин. Никакого нового железа, никакого нового Verilog: только задержки, регистры и деление.

Схема без конвейера: 300 пс логики и 20 пс регистра

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

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

такт = логика + регистр = 300 + 20 = 320 пс

Отсюда обе величины:

задержка одной инструкции = 320 пс
пропускная способность    = 1000 / 320 = 3.13 GIPS

Деление на 1000 стоит объяснить один раз, дальше оно будет везде. Такт в пикосекундах, в наносекунде тысяча пикосекунд, значит 1000 / такт это сколько инструкций уходит за наносекунду. А инструкция в наносекунду это ровно миллиард инструкций в секунду, то есть один GIPS. При такте 320 пс получается 3.13 инструкции за наносекунду.

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

Режем на три этапа

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

Такт считается по самому медленному этапу, а не по сумме:

такт = самый медленный этап + регистр = 100 + 20 = 120 пс

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

Теперь обе величины:

пропускная способность = 1000 / 120 = 8.33 GIPS
задержка одной инструкции = 3 такта по 120 пс = 360 пс

Сравни с исходной машиной. Пропускная способность выросла с 3.13 до 8.33, то есть в 2.67 раза. Задержка выросла с 320 до 360 пс, то есть стала хуже на восьмую часть. Ровно как с пиццей: очередь поехала быстрее, а твоя пицца приехала позже.

Откуда взялись лишние 40 пс задержки, тоже видно из арифметики. Полезной логики по-прежнему 300 пс. А защёлок теперь три вместо одной, и каждая стоит 20 пс: 300 + 3 * 20 = 360. Каждый разрез добавляет к пути одной инструкции ровно одну задержку регистра.

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

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

// Один конвейерный регистр: перегородка между соседними этапами.
// По фронту такта он защёлкивает то, что предыдущий этап досчитал за такт,
// и держит это значение весь следующий такт, пока следующий этап с ним работает.
module pipe_reg #(
  parameter int WIDTH = 64
) (
  input  logic             clk,
  input  logic             rst,
  input  logic [WIDTH-1:0] in,
  output logic [WIDTH-1:0] out
);

  always_ff @(posedge clk) begin
    if (rst) out <= '0;
    else     out <= in;
  end

endmodule

Заметь в нём три вещи: из них растёт вся следующая пара уроков.

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

Второе: ширина. Между этапами едет не одно число, а весь контекст инструкции: icode, ifun, rA, rB, valC, valP, valA, valB, Stat. В настоящем PIPE каждый из регистров F, D, E, M и W это связка из десятка таких полей, защёлкиваемых одним always_ff. Отсюда и цена глубокого конвейера в транзисторах: каждый разрез это не одна защёлка, а сотня бит защёлок.

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

Диаграмма тактов: три инструкции в полёте

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

Машина без конвейера, такт 320 пс. Пока инструкция не прошла всю логику, следующая не начинается:

такт      1        2        3        4
I1      [ABC]
I2               [ABC]
I3                        [ABC]
I4                                 [ABC]

Та же логика, разрезанная на три этапа, такт 120 пс. Как только I1 ушла с этапа A, туда сразу входит I2:

такт      1     2     3     4     5     6
I1        A     B     C
I2              A     B     C
I3                    A     B     C
I4                          A     B     C

Читай эту картинку по двум направлениям, и она расскажет обе величины урока.

По строке читается задержка. Инструкция I1 занимает три клетки, то есть три такта по 120 пс, итого 360 пс. Ни одна инструкция не пройдёт машину быстрее.

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

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

без конвейера: 320 * n
с конвейером:  120 * (n + 2)

Для одной инструкции конвейер проигрывает, 360 против 320. Для двух уже выигрывает, 480 против 640. Для ста даёт 12240 пс против 32000, то есть ускорение в 2.61 раза при теоретическом пределе 2.67. Чем длиннее программа, тем ближе реальность к формуле, потому что разгон и опустошение размазываются по всем инструкциям.

Режем на шесть этапов, и дальше

Разрежем ту же логику на шесть кусков по 50 пс:

такт = 50 + 20 = 70 пс
пропускная способность = 1000 / 70 = 14.29 GIPS
задержка = 6 тактов по 70 пс = 420 пс

Пропускная способность выросла ещё в 1.7 раза, задержка ещё на 60 пс. Общая формула для равномерного разреза на n этапов при логике L и регистре R:

такт = L / n + R
пропускная способность = 1000 / (L / n + R)
задержка = n * такт = L + n * R

Задержка это исходная логика плюс по регистру на каждый этап. Она растёт линейно с числом этапов и никогда не убывает. Пропускная способность растёт, но всё медленнее: слагаемое L / n тает, а R остаётся.

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

const std = @import("std");

// Модель урока: комбинационная логика на 300 пс, конвейерный регистр на 20 пс.
const logic_ps: f64 = 300.0;
const reg_ps: f64 = 20.0;

// Такт равен самому медленному этапу плюс задержка регистра.
fn clockPs(slowest_stage_ps: f64) f64 {
    return slowest_stage_ps + reg_ps;
}

// Пропускная способность в GIPS. Такт в пикосекундах, значит 1000 / такт
// это инструкции на наносекунду, то есть миллиарды инструкций в секунду.
fn throughputGips(clock_ps: f64) f64 {
    return 1000.0 / clock_ps;
}

// Задержка одной инструкции: она проходит все этапы, по такту на этап.
fn latencyPs(stages: f64, clock_ps: f64) f64 {
    return stages * clock_ps;
}

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

    try out.print("этапов  этап, пс  такт, пс  GIPS    задержка, пс\n", .{});
    for (1..13) |n| {
        const stages: f64 = @floatFromInt(n);
        const stage_ps = logic_ps / stages;
        const clock = clockPs(stage_ps);
        try out.print("{d:>6}  {d:>8.1}  {d:>8.1}  {d:>6.2}  {d:>12.1}\n", .{
            n,
            stage_ps,
            clock,
            throughputGips(clock),
            latencyPs(stages, clock),
        });
    }

    // Предел: сколько бы этапов ни было, такт не станет короче задержки регистра.
    try out.print("\nпредел при бесконечном числе этапов: {d:.2} GIPS\n", .{throughputGips(reg_ps)});
    try out.flush();
}

zig run throughput.zig

этапов  этап, пс  такт, пс  GIPS    задержка, пс
     1     300.0     320.0    3.13         320.0
     2     150.0     170.0    5.88         340.0
     3     100.0     120.0    8.33         360.0
     4      75.0      95.0   10.53         380.0
     5      60.0      80.0   12.50         400.0
     6      50.0      70.0   14.29         420.0
     7      42.9      62.9   15.91         440.0
     8      37.5      57.5   17.39         460.0
     9      33.3      53.3   18.75         480.0
    10      30.0      50.0   20.00         500.0
    11      27.3      47.3   21.15         520.0
    12      25.0      45.0   22.22         540.0

предел при бесконечном числе этапов: 50.00 GIPS

Прочитай таблицу как историю убывающей отдачи. Первый разрез, с одного этапа на два, добавляет 2.75 GIPS. Разрез с двух на три ещё 2.45. С одиннадцати на двенадцать уже 1.07. А задержка каждый раз прибавляет ровно 20 пс, честно и без скидок.

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

Предел: регистр не даёт разогнаться

Последняя строка вывода это главное число раздела. Задержка регистра R стоит в такте всегда, сколько бы этапов ты ни нарезал:

такт = L / n + R,  при большом n такт стремится к R = 20 пс
предел пропускной способности = 1000 / 20 = 50 GIPS

Никакая глубина не даст больше пятидесяти GIPS на этой модели. Двенадцать этапов дают 22.22, то есть меньше половины предела, а стоят двенадцати защёлок и задержки в 540 пс. Чтобы добраться до сорока пяти GIPS, то есть девяноста процентов предела, нужен такт 22.22 пс, значит 300 / n = 2.22, значит около 135 этапов. Задержка при этом станет три наносекунды вместо трёхсот двадцати пикосекунд: десятикратный проигрыш по задержке ради последних десяти процентов пропускной способности.

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

Проверка на пальцах: сколько инструкций в машине

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

Проверим на трёх машинах урока. Машина без конвейера: 3.13 инструкции за наносекунду на 0.320 нс задержки даёт 1.0. Одна инструкция внутри, как и должно быть. Трёхэтапная: 8.33 на 0.360 даёт 3.0. Шестиэтапная: 14.29 на 0.420 даёт 6.0.

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

Соотношение полезно и в обратную сторону, как предупреждение. Если инструкции в программе выстроены в одну цепочку зависимостей, где каждая ждёт результата предыдущей, конвейер заполнить нечем: внутри живёт одна инструкция вместо шести. Такая программа увидит не пропускную способность в 14.29 GIPS, а задержку в 420 пс на инструкцию, то есть будет работать медленнее, чем на машине без конвейера вообще. Глубина окупается только тем кодом, в котором есть чем её занять, а раздел про обратную связь ниже покажет, почему настоящий машинный код таким бывает не всегда.

Неравномерные этапы: такт задаёт самый медленный

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

Возьмём цепочку из шести блоков с задержками 80, 30, 60, 50, 70 и 10 пикосекунд. Сумма те же 300 пс, регистр те же 20 пс. Назовём блоки A, B, C, D, E, F.

A: 80    B: 30    C: 60    D: 50    E: 70    F: 10

Разрежем на два этапа. Разрез можно поставить в пяти местах, и такт каждый раз задаёт более длинная половина:

Разрез после	Этап 1	Этап 2	Медленный	Такт	GIPS
A	80	220	220	240	4.17
B	110	190	190	210	4.76
C	170	130	170	190	5.26
D	220	80	220	240	4.17
E	290	10	290	310	3.23

Лучший разрез после C: 170 и 130, такт 190 пс, 5.26 GIPS, задержка 380 пс. Место разреза решает. Разрез после E почти ничего не даёт, 3.23 против 3.13 без конвейера, потому что оставляет один этап длиной 290 пс. Идеальный ровный разрез пополам дал бы 150 и 150, такт 170 пс и 5.88 GIPS, но такого места в цепочке просто нет.

Теперь три этапа. Лучший разрез это A с B, C с D, и E с F:

110 | 110 | 80   такт = 110 + 20 = 130 пс   7.69 GIPS   задержка 390 пс

И вот главный сюрприз этого раздела. Разрежем на пять этапов и на шесть:

пять этапов:  80 | 30 | 60 | 50 | 80     такт = 80 + 20 = 100 пс   10.00 GIPS   задержка 500 пс
шесть этапов: 80 | 30 | 60 | 50 | 70 | 10  такт = 80 + 20 = 100 пс   10.00 GIPS   задержка 600 пс

Шестой регистр не дал ничего. Пропускная способность та же самая, потому что узкое место это блок A на 80 пс, а его мы не разрезали и разрезать не можем. Зато задержка выросла на сто пикосекунд, с 500 до 600. Разрез, который не трогает узкое место, это чистый убыток.

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

Обратная связь: почему процессор это не завод

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

С инструкциями это не так, и в этом вся сложность процессорного конвейера. Посмотри на тело цикла из sum.ys, программы, которую твоя машина гоняла в прошлом уроке:

loop:   mrmovq (%rdi), %r10     # взять *start
        addq %r10, %rax         # прибавить к сумме
        addq %r8, %rdi          # сдвинуть указатель на элемент
        subq %r9, %rsi          # уменьшить счётчик, флаги
test:   jne loop                # пока счётчик не ноль

Здесь три разные обратные связи, и каждая ломает наивную картинку.

Первая это зависимость по данным. Инструкция addq %r10, %rax читает %r10, а пишет его предыдущая инструкция mrmovq, причём пишет на самом последнем этапе, в write back. В SEQ проблемы нет: инструкция целиком завершилась, прежде чем началась следующая. В конвейере addq доберётся до decode, когда mrmovq ещё только в execute, и прочитает из регистрового файла старое значение.

Разложи это по тактам, и станет видно, насколько промах велик:

такт      1     2     3     4     5     6
mrmovq    F     D     E     M     W
addq            F     D     E     M     W
                      ^           ^
                      здесь       а записано будет только здесь
                      нужен %r10

Значение нужно на такте 3, а появляется на такте 5. Два такта разрыва, и никакая перестановка проводов внутри этапа их не закроет.

Вторая связь идёт через коды условий. Инструкция jne решает, куда идти, по флагам, которые выставил subq. Флаги ставятся в execute, а нужны они переходу тоже в execute, и инструкции идут подряд.

Третья самая неприятная: зависимость по адресу следующей инструкции. Чтобы начать инструкцию, нужен PC. Обычно valP вычисляется на fetch, и следующая инструкция стартует немедленно. Но для jne следующий адрес зависит от флагов, то есть от результата execute, а для ret он лежит в памяти и станет известен только после memory. Заводской конвейер знает, какая деталь придёт следующей. Процессорный конвейер этого не знает: следующую работу определяет результат текущей.

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

Время программы: такты, период и CPI

Соберём всё в одну формулу, которой дальше будем мерить обе машины:

время программы = число инструкций * CPI * период такта

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

Разложим CPI конвейера на две части. Первая это разгон и опустошение: n инструкций на пятиэтапной машине занимают минимум n + 4 такта. Вторая это остановы из-за обратной связи, и вот они уже зависят от того, что за программа.

Возьми программу sum: она исполняет 34 инструкции. Идеальный пятиэтапный конвейер прошёл бы её за 38 тактов. Реальный PIPE из эталона тратит 50. Двенадцать лишних тактов это и есть цена трёх обратных связей, посчитанная в тактах. Для bubble с её 173 инструкциями идеал 177, реальность 230, потеряно 53 такта.

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

Сколько стоит такт SEQ

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

Блок SEQ	Что делает	Задержка
fetch	чтение десяти байт из памяти инструкций, разбор полей, `valP`	80 пс
decode	чтение двух портов регистрового файла	60 пс
execute	ALU и вычисление `Cnd`	90 пс
memory	чтение или запись восьмибайтного слова	110 пс
write back	запись двух портов регистрового файла	40 пс
pc update	мультиплексор выбора следующего адреса	20 пс

Сумма ровно 400 пс. Плюс защёлка на 20 пс, и такт SEQ равен 420 пс. Пятиэтапный разрез сделаем так, как его делает настоящий PIPE: логика выбора PC уезжает в fetch (это превращение SEQ в SEQ+, и разбирать его будет следующий урок), остальные блоки становятся этапами F, D, E, M и W как есть.

Считаем программой, чтобы не ошибиться в делении.

const std = @import("std");

const reg_ps: f64 = 20.0;

const Stage = struct { name: []const u8, ps: f64 };

// Задержки шести блоков SEQ, в пикосекундах.
const seq_stages = [_]Stage{
    .{ .name = "fetch", .ps = 80 },
    .{ .name = "decode", .ps = 60 },
    .{ .name = "execute", .ps = 90 },
    .{ .name = "memory", .ps = 110 },
    .{ .name = "write back", .ps = 40 },
    .{ .name = "pc update", .ps = 20 },
};

// Разрез на пять этапов: выбор следующего PC переезжает в fetch.
const pipe_stages = [_]Stage{
    .{ .name = "F", .ps = 80 + 20 },
    .{ .name = "D", .ps = 60 },
    .{ .name = "E", .ps = 90 },
    .{ .name = "M", .ps = 110 },
    .{ .name = "W", .ps = 40 },
};

// Реальные такты эталона: программа, такты SEQ, такты PIPE.
const Program = struct { name: []const u8, seq: f64, pipe: f64 };
const programs = [_]Program{
    .{ .name = "sum", .seq = 34, .pipe = 50 },
    .{ .name = "rsum", .seq = 65, .pipe = 95 },
    .{ .name = "abs_sum", .seq = 64, .pipe = 90 },
    .{ .name = "abs_sum_cmov", .seq = 61, .pipe = 75 },
    .{ .name = "bubble", .seq = 173, .pipe = 230 },
    .{ .name = "switchv", .seq = 23, .pipe = 41 },
};

fn total(stages: []const Stage) f64 {
    var sum: f64 = 0;
    for (stages) |s| sum += s.ps;
    return sum;
}

fn slowest(stages: []const Stage) Stage {
    var best = stages[0];
    for (stages) |s| {
        if (s.ps > best.ps) best = s;
    }
    return best;
}

fn gips(clock_ps: f64) f64 {
    return 1000.0 / clock_ps;
}

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

    // SEQ: все шесть блоков в одном такте, поэтому такт равен их сумме.
    const seq_clock = total(&seq_stages) + reg_ps;
    try out.print("SEQ:  такт {d:.0} пс, {d:.3} GIPS, задержка {d:.0} пс\n", .{
        seq_clock, gips(seq_clock), seq_clock,
    });

    // PIPE: такт задаёт самый медленный этап, задержка это пять тактов.
    const neck = slowest(&pipe_stages);
    const pipe_clock = neck.ps + reg_ps;
    const pipe_latency = @as(f64, pipe_stages.len) * pipe_clock;
    try out.print("PIPE: такт {d:.0} пс (узкое место {s}, {d:.0} пс), {d:.3} GIPS, задержка {d:.0} пс\n", .{
        pipe_clock, neck.name, neck.ps, gips(pipe_clock), pipe_latency,
    });
    try out.print("идеальное ускорение по тактовой частоте: {d:.2}\n", .{seq_clock / pipe_clock});

    const even = total(&pipe_stages) / @as(f64, pipe_stages.len) + reg_ps;
    try out.print("ровный разрез на пять этапов дал бы {d:.0} пс и {d:.2} GIPS\n\n", .{ even, gips(even) });

    try out.print("программа       SEQ, нс  PIPE, нс  ускорение  CPI PIPE\n", .{});
    for (programs) |p| {
        const seq_ns = p.seq * seq_clock / 1000.0;
        const pipe_ns = p.pipe * pipe_clock / 1000.0;
        try out.print("{s:<14}{d:>8.2}{d:>10.2}{d:>11.2}{d:>10.2}\n", .{
            p.name, seq_ns, pipe_ns, seq_ns / pipe_ns, p.pipe / p.seq,
        });
    }
    try out.flush();
}

zig run seq_vs_pipe.zig

SEQ:  такт 420 пс, 2.381 GIPS, задержка 420 пс
PIPE: такт 130 пс (узкое место M, 110 пс), 7.692 GIPS, задержка 650 пс
идеальное ускорение по тактовой частоте: 3.23
ровный разрез на пять этапов дал бы 100 пс и 10.00 GIPS

программа       SEQ, нс  PIPE, нс  ускорение  CPI PIPE
sum              14.28      6.50       2.20      1.47
rsum             27.30     12.35       2.21      1.46
abs_sum          26.88     11.70       2.30      1.41
abs_sum_cmov     25.62      9.75       2.63      1.23
bubble           72.66     29.90       2.43      1.33
switchv           9.66      5.33       1.81      1.78

Разберём вывод по строкам, здесь весь урок в четырёх числах.

Такт 420 против 130 пс. SEQ платит за то, что все шесть блоков лежат в одном такте. PIPE платит только за самый медленный этап, а это память на 110 пс. Отношение 3.23 это то, что обещает формула, и это чистая тактовая частота, ещё без единого пузырька.

Узкое место это M. Этап F после переезда логики PC вырос до ста пикосекунд и почти догнал память. Дальнейшее ускорение машины упирается в чтение данных: ускоришь ALU на десять пикосекунд, и такт не изменится ни на пикосекунду. Это тот самый закон узкого места, только теперь на своей схеме.

Ровный разрез дал бы 100 пс. Сумма пяти этапов 400 пс, разделить на пять это 80 пс, плюс защёлка 100 пс, то есть 10 GIPS. Мы получаем 7.69, потому что этапы неравные. Почти четверть пропускной способности теряется на том, что блоки процессора разной длины, а порезать память пополам не выйдет без её переделки.

Задержка выросла с 420 до 650 пс. Полторы SEQ-задержки на инструкцию. Для программы это не важно, потому что инструкций много и они идут потоком. Для одной инструкции важно, и вот тут появляется цена ошибочного предсказания: если конвейер угадал не туда, он потратил эти 650 пс зря.

Таблица программ это честный итог. Такты SEQ и PIPE взяты не из головы: это halt cycles реальных прогонов эталона, левая колонка от симулятора на Zig и Verilog-SEQ (у них одинаково, потому что обе машины делают одну инструкцию за такт), правая от Verilog-PIPE. Ускорение нигде не 3.23, а от 1.81 до 2.63, потому что конвейер тратит лишние такты на остановы. Колонка CPI показывает, сколько именно: от 1.23 до 1.78 такта на инструкцию.

Самая говорящая пара строк это abs_sum и abs_sum_cmov. Это одна и та же задача, сумма модулей: первая версия выбирает знак условным переходом, вторая условной пересылкой cmovg. На SEQ разница мизерная, 64 такта против 61, потому что SEQ платит по одному такту за инструкцию и ветвление ему ничего не стоит. На PIPE разница уже 90 против 75: каждый неверно предсказанный переход выбрасывает работу. То самое сравнение перехода и cmov, которое ты видел на x86-64 в уроке про флаги и cmov, здесь получает точную цену в тактах на собственной машине.

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

zig build run -- asm programs/abs_sum_cmov.ys --hex abs_sum_cmov.hex
bash hdl/run.sh seq  abs_sum_cmov.hex | grep 'halt cycles'
bash hdl/run.sh pipe abs_sum_cmov.hex | grep 'halt cycles'

halt cycles=61
halt cycles=75

Упражнения

CHK-1★

Возьми модель урока (логика 300 пс, регистр 20 пс) и посчитай на бумаге такт, пропускную способность и задержку для разреза на четыре этапа и на десять этапов. Сверься с таблицей из первого листинга. Затем ответь словами: во сколько раз выросла пропускная способность при переходе с четырёх этапов на десять и во сколько раз выросла задержка.

CHK-2★★

Цепочка из шести блоков с задержками 80, 30, 60, 50, 70 и 10 пс, регистр 20 пс. Резать можно только по границам блоков. Найди лучший разрез на два этапа и лучший разрез на три этапа: для каждого выпиши, где стоят регистры, какой этап оказался узким местом, чему равны такт, пропускная способность и задержка. Это переформулированное упражнение 4.28 из CS:APP, и разбирать нужно все варианты разреза, а не первый подошедший.

CHK-3★★

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

CHK-4★★

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

CHK-5★★

Прогони через эталон программы rsum и switchv: собери каждую в hex-образ, запусти на seq и на pipe, выпиши halt cycles обеих. Посчитай для каждой программы CPI конвейера, время в наносекундах при такте 420 пс для SEQ и 130 пс для PIPE, и настоящее ускорение. Объясни, почему у switchv ускорение заметно хуже, чем у rsum, хотя частота у обеих машин одна и та же.

CHK-6★★★

Выпиши тело цикла acloop из программы abs_sum_cmov и пройди по нему сверху вниз, отмечая каждую пару инструкций, где вторая нуждается в результате первой. Для каждой пары укажи, что именно передаётся (регистр, флаги или адрес следующей инструкции) и на каком этапе конвейера значение станет готово, если считать, что регистры пишутся в W, флаги ставятся в E, а адрес перехода известен после E. Отдельно выпиши пару, где значение нужно раньше, чем оно вообще может появиться.

Итоги

“Быстрее” это две величины. Задержка это время одной инструкции от входа до записи результата, пропускная способность это сколько инструкций машина завершает за секунду. Конвейер улучшает вторую и ухудшает первую.
Такт конвейера равен задержке самого медленного этапа плюс задержке конвейерного регистра. По сумме этапов считается только машина без конвейера, где вся логика лежит в одном такте.
Для ровного разреза логики L на n этапов при регистре R: такт равен L / n + R, пропускная способность равна 1000 / такт в GIPS при такте в пикосекундах, задержка равна L + n * R.
Задержка растёт линейно с числом этапов и никогда не убывает: каждый разрез добавляет к пути инструкции ровно одну защёлку. Пропускная способность растёт с убывающей отдачей.
Предел глубины задаёт регистр. При R равном 20 пс никакая глубина не даст больше 50 GIPS, а девяносто процентов предела стоят около ста тридцати пяти этапов и десятикратной задержки.
Конвейерный регистр ничего не вычисляет, он только запоминает. Поэтому конвейер не уменьшает суммарную работу, он лишь перестаёт ждать её окончания, и каждый разрез добавляет к работе накладные расходы.
Короткая программа выигрывает меньше длинной: n инструкций на конвейере из k этапов занимают минимум n + k - 1 тактов, и разгон с опустошением размазываются тем лучше, чем длиннее программа.
Число инструкций, живущих в машине одновременно, равно пропускной способности, умноженной на задержку, и для ровного конвейера оно совпадает с числом этапов. Программа из одной цепочки зависимостей конвейер не заполняет и видит задержку, а не пропускную способность.
Неравномерные этапы съедают выигрыш: такт определяет узкое место, а не среднее. На нашей схеме ровный разрез дал бы 10 GIPS, а настоящий даёт 7.69, потому что память на 110 пс не режется.
Разрез, который не трогает узкое место, ничего не даёт по пропускной способности и при этом честно добавляет такт к задержке. Ускорять имеет смысл только самый медленный этап.
Такт SEQ это сумма всех шести блоков плюс защёлка, 420 пс. Пятиэтапный разрез даёт такт 130 пс и обещает ускорение в 3.23 раза по частоте.
Обещание не выполняется, потому что инструкции не независимы. Три обратные связи: значение регистра пишется в W, а нужно в D; флаги ставятся в E, а нужны следующему переходу; адрес следующей инструкции для jXX зависит от E, а для ret от M.
Время программы это число инструкций, умноженное на CPI и на период такта. Реальные прогоны эталона дают ускорение от 1.81 до 2.63 при CPI конвейера от 1.23 до 1.78, и разрыв между 3.23 и этими числами есть цена обратной связи.
Цена ветвления в конвейере видна на паре abs_sum и abs_sum_cmov: на SEQ 64 такта против 61, на PIPE уже 90 против 75. Условная пересылка выигрывает именно там, где есть конвейер.

Дальше

Ты посчитал, сколько конвейер обещает, и увидел, почему он обещанного не отдаёт. Дальше идёт самый большой урок про конвейер, где обещание превращается в схему. Сначала SEQ станет SEQ+: логика выбора следующего PC переедет в начало такта, чтобы этап F знал, что выбирать, ещё до всего остального. Потом между этапами встанут настоящие конвейерные регистры F, D, E, M и W, и по машине одновременно поедут пять инструкций. И сразу же придётся чинить все три обратные связи из этого урока: значение будет продвигаться назад из пяти разных точек конвейера прямо на вход decode, переход будет предсказываться заранее с откатом на два пузырька при ошибке, ret будет стоить три пузырька, а связка загрузки и немедленного использования заставит конвейер остановиться на такт. Числа 1.23 и 1.78 из таблицы CPI получат поимённое объяснение, откуда каждый лишний такт взялся.

домашка

Домашка

Разрежь цепочку блоков A до F на k этапов всеми способами для k от 1 до 6, найди для каждого k лучший разрез и сведи такт, пропускную способность и задержку в таблицу. Проверь свои числа программой.S
Найди глубину конвейера и частоту любого настоящего процессора, посчитай по ним задержку одной инструкции в наносекундах и сравни с задержкой нашей пятиэтапной машины.S
Прогони четыре программы эталона на SEQ и на PIPE, сведи такты в таблицу, посчитай CPI конвейера и настоящее ускорение по времени, объясни разрыв с идеальным.S