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

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:	fe0718e3		bnez	a4,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:	44f12a23		sw	a5,1108(sp)
2a24:	00054783	lbu	a5,0(a0)
2a28:	44410713	addi	a4,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 элементов.