Процессор на коленке ч.6. Классический 5-этапный конвейер

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

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

2. Память отвечает на следующем такте, то есть если первая инструкция посчитает адрес второй, то вторая будет прочитана на следующем такте и никакой параллельности не получится.

3. Частота просела до 34 МГц, маловато будет.

Все эти факты в сумме говорят, что пора переходить с 3-х этапного на 5-этапный конвейер. Можно почитать здесь и здесь, как устроен классический конвейер RISC-V. Реализацию для данной статьи можно посмотреть на Github в соответствующей ветке.

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

Частота: 34 МГц slow / 75 МГц fast
Коремарки: 2.6 (38 тиков)
Полный размер SoC: 4518 LUT / 2059 reg
Ядро: 2536 LUT / 879 reg

Запрос инструкций

Первое, что мы сделаем — это запрос инструкций вслепую. Это значит, что нулевой этап (fetch) будет увеличивать счётчик инструкций и запрашивать следующую без лишних вопросов, а когда исполнение дойдёт до ветки, следующий этап просигналит о смене адреса. И тогда нулевой этап переставит регистр pc на новый адрес, а то что успел запросить до этого, попросит выкинуть.
Звучит просто, да и реализация короткая, но, как говорится, счастливой отладки. А ещё такой простор для оптимизаций, тот же предсказатель переходов чего стоит. Ладно, пора писать код.
Для начала заведём сигналы следующего адреса и факта прыжка, вычисляемые на этапе исполнения. Тут возникает первая проблема. Инструкция может быть многотактовой, так что если бездумно инкрементить счетчик, к концу инструкции можно оказаться в неожиданном месте, поэтому у нулевого этапа тоже появляется флаг затора (jam_up).

wire [31:0] stage_e_pc_next; // адрес, вычисленный инструкцией, бывший stage0_pc wire stage_f_jump;           // был ли в текущей инструкции переход wire stage_f_jam_up;         // надо ли переходить к следующей инструкции 

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

reg stage_f_pc_actual; stage_f_pc_actual <= reset ? 0 : !stage_f_jump; assign instruction_address = !stage_f_pc_actual ? pc : pc + 4; // это отправляется на шину адреса wire stage_d_empty = !stage_f_pc_actual || !instruction_ready; // а это следующему этапу 

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

wire [31:0] stage_f_pc = stage_f_jump ? stage_e_pc_next :  stage_f_jam_up ? pc : pc + 4; //pc <= stage_f_pc; это делается в модуле регистров wire enable_write_pc = !stage_d_pause || stage_f_jump; 

Саму инструкцию сохраняем отдельно, ну и для повтора многотактовой инструкции запоминаем флаг затора.

reg stage_f_instruction_repeat; // инструкция многотактовая stage_f_instruction_repeat  <= reset ? 0 : stage_f_jam_up && !stage_f_jump; reg [31:0] last_instruction; last_instruction <= reset ? 0 : instruction; wire [31:0] instruction = stage_d_empty ? 0 :  stage_f_instruction_repeat ? last_instruction :  instruction_data; 

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

Частота: 38 МГц slow / 88 МГц fast
Коремарки: 2.3 (43 тика)
Полный размер SoC: 4667 LUT / 2093 reg
Ядро: 2572 LUT / 913 reg

Переход в итоге срабатывает за 2 такта.

2a90:fe0718e3bneza4,2a80 <ee_printf+0x80> 

Обращение к памяти

При обращении к памяти длина цепочки примерно такая же, как при запросе инструкции. Точно так же берётся значение регистра и к нему прибавляется константа, а потом используется в качестве адреса. Значит будем резать. Раньше после этапа обработки у нас был этап записи в регистр и ожидания памяти при необходимости, а первый запрос к памяти делался прямо из этапа выполнения. Теперь добавится промежуточный этап (memory), куда будет записываться адрес памяти и всё прочее, необходимое для запроса, а следующий станет называться write back. Но хоть они так и называются, фактически, если место свободно, регистр может быть записан из этапа memory, а если память с одного раза не ответила, может быть перезапрошена с этапа write back. Что ж, к коллайдеру.
Заведём пачку регистров для запроса памяти и для записи результата.

reg [2:0]  stage_m_funct3; // как расширить знак прочитанного значения reg        stage_m_data_read; reg        stage_m_data_write; reg [31:0] stage_m_address; reg [31:0] stage_m_data_out; // значение для записи в память  reg [31:0] stage_m_rd_value; // значение для записи в регистр-назначение reg [4:0]  stage_m_rd_index; reg        stage_m_is_rd_changed;  reg        stage_m_empty; // предыдущий этап ещё в раздумьях, а у нас тут пузырёк 

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

if (!stage_m_wait) begin stage_m_rd_value   <= stage_e_rd_value; stage_m_address    <= stage_e_address; ... stage_m_empty      <= stage_e_not_ready; // выполнение инструкции ещё в процессе end 

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

wire stage_m_no_retry = stage_m_empty || !(stage_m_data_read || stage_m_data_write); 

Запись регистра

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

if (!stage_wb_wait) begin stage_wb_funct3     <= stage_m_funct3; stage_wb_data_read  <= stage_m_data_read; stage_wb_data_write <= stage_m_data_write; stage_wb_address    <= stage_m_address; stage_wb_data_out   <= stage_m_data_out; stage_wb_rd_index   <= stage_m_rd_index; stage_wb_is_rd_changed <= stage_m_is_rd_changed; stage_wb_empty      <= stage_m_no_retry; end 

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

wire stage_wb_memory_wait = !stage_wb_empty && !data_ready; 

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

assign data_read    = stage_wb_memory_wait ? stage_wb_data_read   : stage_m_data_read; assign data_write   = stage_wb_memory_wait ? stage_wb_data_write  : stage_m_data_write; assign data_out     = stage_wb_memory_wait ? stage_wb_data_out    : stage_m_data_out; assign data_address = stage_wb_memory_wait ? stage_wb_address     : stage_m_address; assign data_width   = stage_wb_memory_wait ? stage_wb_funct3[1:0] : stage_m_funct3[1:0]; 

Теперь вроде бы надо отработать ответ памяти, но ответ — это запись в регистр, так что с ней и будем разбираться. Аналогично надо выбрать, с какого этапа брать данные, и здесь можно получить весёлые часы отладки, если взять тот же самый флаг memory_wait, а всё потому что запрос посылается на одном такте, а ответ получается на другом. Для всех этапов, где можно, заведём флаг has_rd, который означает, что в конечном итоге инструкция собирается поменять регистр. Для текущего этапа он будет выглядеть так

wire stage_wb_has_rd = !stage_wb_empty && stage_wb_is_rd_changed; 

Теперь можно расшифровывать ответ памяти. Заметьте, data_width тоже пересчитывается по этому флагу.

wire [1:0] data_width_read = stage_wb_has_rd ? stage_wb_funct3[1:0] : stage_m_funct3[1:0]; wire load_signed = ~(stage_wb_has_rd ? stage_wb_funct3[2] : stage_m_funct3[2]);  wire [31:0] rd_load = data_width_read == 0 ? {{24{load_signed & data_in[7]}}, data_in[7:0]} : //0-byte                       data_width_read == 1 ? {{16{load_signed & data_in[15]}}, data_in[15:0]} : //1-half                       data_in; //2-word 

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

wire [31:0] selected_rd_value = stage_wb_has_rd ? rd_load : stage_m_rd_value; wire [4:0]  selected_rd_index = stage_wb_has_rd ? stage_wb_rd_index : stage_m_rd_index; wire stage_wb_enable_write_rd = !stage_wb_wait && (stage_wb_has_rd || stage_m_has_rd); RiscVRegs regs( ... .enable_write_rd(stage_wb_enable_write_rd), //пишем результат обработки операции .rd_index(selected_rd_index), .rd(selected_rd_value) ); 

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

wire [`REG_COUNT-1:0] stage_e_dirty_regs =  stage_e_working && stage_e_is_write_rd || !stage_e_empty && stage_e_is_op_load ?  (1 << stage_e_rd_index) : 0;  wire [`REG_COUNT-1:0] stage_m_dirty_regs =  !stage_m_empty && stage_m_data_read ?  (1 << stage_m_rd_index) : 0;  wire [`REG_COUNT-1:0] stage_wb_dirty_regs =  stage_wb_wait && stage_wb_has_rd ?  (1 << stage_wb_rd_index) : 0;  wire [`REG_COUNT-1:0] dirty_regs = stage_e_dirty_regs | stage_m_dirty_regs | stage_wb_dirty_regs; 

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

// подобные флаги ставим на каждом этапе // для второго регистра аналогично wire stage_wb_rs1_equal = (stage_wb_rd_index == op_rs1); wire stage_wb_rs1_used = stage_wb_has_rd && stage_wb_rs1_equal;  // это читаем из регистрового файла wire [31:0] reg_s1_file;  // это выдаём вместо ответа от регистрового файла assign reg_s1 = stage_e_rs1_used ? stage_e_rd_value : stage_m_rs1_used ? stage_m_rd_value : stage_wb_rs1_used ? rd_load : reg_s1_file; 

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

Частота: 45 МГц slow / 103 МГц fast
Коремарки: 2.1 (48 тиков)
Полный размер SoC: 4758 LUT / 2169 reg
Ядро: 2691 LUT / 989 reg

Частота растёт, коремарки падают. Вот к примеру, как инструкция задерживается на 1 такт из-за того, что за один раз память не ответила, на второй раз адрес берётся с этапа write back.

2a20:44f12a23swa5,1108(sp) 2a24:00054783lbua5,0(a0) 2a28:44410713addia4,sp,1092 

Декодирование инструкции

С обращением по адресам памяти разобрались, теперь надо разобраться с адресами регистров, они тоже добавляют задержку. Для этого первый этап разделим на этап декодирования и запроса регистров (decode) и этап исполнения (execute). На этапе декодирования останется расчёт флажков типа is_op_alu и т.п., формирование immediate — константы, встроенной в инструкцию, и получение регистров. Проверка доступности регистров теперь будет красивой.

wire use_rs1 = type_r || type_i || type_s || type_b; wire use_rs2 = type_r || type_s || type_b; assign stage_d_empty_regs = use_rs1 && dirty_regs[op_rs1] || use_rs2 && dirty_regs[op_rs2]; wire stage_d_pause = stage_d_empty || stage_d_empty_regs; 

Выполнение инструкции

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

// тип инструкции reg stage_e_is_op_load; ...  // аргументы инструкции reg [31:0] stage_e_immediate; reg [31:0] stage_e_rs1; reg [31:0] stage_e_rs2; reg [31:0] stage_e_pc; // адрес, с которого инструкция прочитана  // выходные данные инструкции reg [4:0] stage_e_rd_index; reg stage_e_is_write_rd;  if(!stage_e_wait) begin stage_e_is_op_load       <= is_op_load; ... stage_e_empty            <= stage_d_pause || stage_f_jump; end  wire stage_e_data_read = stage_e_is_op_load && !stage_e_pause; wire[31:0] stage_e_address = stage_e_rs1 + stage_e_immediate; ...  wire [31:0] stage_e_rd_value = stage_e_is_op_multiply ? rd_mul : ... 

Здесь же считаем адрес перехода. До этого этапа идут ещё 2, поэтому потеря времени при попадании на ветку тоже составляет 2 такта, и это сильно влияет на производительность за такт.

wire jump_activated = stage_e_is_op_branch && branch_fired || stage_e_is_op_jal || stage_e_is_op_jalr; assign stage_f_jump = !stage_e_pause && jump_activated; assign stage_e_pc_next = stage_e_not_ready ? stage_e_pc : (stage_e_is_op_branch && branch_fired) ? pc_branch : stage_e_is_op_jal ? pc_jal : stage_e_is_op_jalr ? pc_jalr : stage_e_pc + 4; 

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

wire stage_e_need_next = stage_e_is_write_rd || stage_e_is_op_load || stage_e_is_op_store; assign stage_e_jam_up = stage_m_wait && stage_e_need_next; 

Итог наших преобразований для многотактового умножения.

Частота: 70 МГц slow / 157 МГц fast
Коремарки: 1.9 (54 тика)
Полный размер SoC: 5069 LUT / 2318 reg
Ядро: 2927 LUT / 1138 reg

Можно, к примеру, посмотреть, как пузырёк распространяется по конвейеру.

Этапы decode и execute при переходе инвалидируются одновременно, поэтому получается такая ёлочка из 2 полос.
С одной стороны, вроде как некоторые инструкции занимают несколько тактов, с другой — они и раньше занимали несколько тактов, если за такт брать новую длительность. Зато все остальные стали быстрее. Суммарно переход с 3-х на 5-этапный конвейер дал прирост производительности в 1.5 раза, и это при условии, что кэш всего на 8 элементов.