RISC-V OoO CPUを実装する (14. IQ age matrix: 古い命令を絶対に追い越させない)

前回のtop moduleでpipelineが一通り繋がったが、smoke testの結果2命令retireで止まって「deadlock」していた。 原因はIQのpriorityが「physical entry indexのLSB」で決まっていて、free slotに埋まった若い命令が古い命令を追い越して発行され、in-order retireのROBで古い命令の完了待ちのまま止まる、というOoOの初歩的な設計不備。 今回はage matrixを入れてこれを解消し、ついでに絡み合った別のbugも一つ潰した話。

Age matrixの実装

古典的なOoO schedulerの1テクニックで、BOOMやXiangShanが使っているのと同じ形。

• logic [IQ_ENTRIES-1: 0][IQ_ENTRIES-1: 0] r_age_matrix;
• age[i][j] = 1 = entry iはjより古い、というbit matrix
• Dispatchで新規に埋まるentryのrowをall-clear、逆に既存valid entryのcolumn (新規entryを表す) は1
• Issueは「row iがall (ready & cat-matching) entryに対して1」ならoldest → 1個だけ1になるone-hot

update logicの構造:

generate for (genvar i_idx = 0; i_idx < IQ_ENTRY_NUM; i_idx++) begin
  for (genvar j_idx = 0; j_idx < IQ_ENTRY_NUM; j_idx++) begin
    always_ff @(posedge clk, negedge rst_n) begin
      if (!rst_n | flush_all) begin
        r_age_matrix[i_idx][j_idx] <= 1'b0;
      end else if (w_being_dispatched[i_idx] & w_being_dispatched[j_idx]) begin
        // 両方同時dispatch: 若いlane indexが古い命令
        r_age_matrix[i_idx][j_idx] <= (w_dispatch_lane[i_idx] < w_dispatch_lane[j_idx]);
      end else if (w_being_dispatched[i_idx]) begin
        r_age_matrix[i_idx][j_idx] <= 1'b0;   // i is new; not older than anyone
      end else if (w_being_dispatched[j_idx]) begin
        r_age_matrix[i_idx][j_idx] <= r_iq[i_idx].valid;   // existing i older than new j
      end
    end
  end
end endgenerate

Multi-lane dispatchでlane順序を「若い方が古い」に決める

最初lane 0 vs lane 1の比較をhardcodeで書いていたが、これだとDISP_SIZE=2前提で6-way構成 (最終形態) にscaleしない。 「entryごとにどのlaneがdispatchしたか」をsignal化して、そのlane indexの順序で古さを決める形にした:

logic [$clog2(DISP_SIZE)-1: 0] w_dispatch_lane [IQ_ENTRY_NUM];

always_comb begin
  for (int e = 0; e < IQ_ENTRY_NUM; e++) begin
    w_dispatch_lane[e] = '0;
    for (int d = 0; d < DISP_SIZE; d++) begin
      if (i_dis_valid[d] & w_iq_free_slot_oh[d][e]) begin
        w_dispatch_lane[e] = d[$clog2(DISP_SIZE)-1: 0];
      end
    end
  end
end

これでage matrix更新はlane index比較1本にまとまり、DISP_SIZEを大きくしても同じcodeが使える。

「lane 0がlane 1より古い」のinvariantはfront-endの構造から自動的に保たれる:

• Fetch F3 output: lane 0のPCがlane 1のPCより4小さい (program order)
• Rename: all-or-nothing dispatchなのでpartial dispatchが発生しない
• ROB: 若いlane 0のrob_idがlane 1より1小さい

なのでdispatch時点で「lane indexが若い = 古い命令」が常に成立。

Issue selectorの書き換え

bit_extract_lsbのLSB priorityは削除して、age matrixでoldest-among-readyを選ぶ形に:

generate for (genvar p = 0; p < PRF_WRITE_PORTS; p++) begin
  logic [IQ_ENTRY_NUM-1: 0] w_oldest_ready;
  for (genvar i = 0; i < IQ_ENTRY_NUM; i++) begin
    logic w_older_than_all;
    always_comb begin
      w_older_than_all = 1'b1;
      for (int j = 0; j < IQ_ENTRY_NUM; j++) begin
        if (i != j) begin
          if (w_issue_ready[p][j] & ~r_age_matrix[i][j]) begin
            w_older_than_all = 1'b0;
          end
        end
      end
    end
    assign w_oldest_ready[i] = w_issue_ready[p][i] & w_older_than_all;
  end
  // w_oldest_ready is one-hot (unique oldest)
  assign w_iss_slot_oh[p] = w_oldest_ready;
  ...
end endgenerate

「entry iのage matrix rowが『同portの候補でreadyなentry全部』をdominateする」ならiは該当portのoldest ready。1個だけ1が立つone-hotになるので、そのままselectorとして使える。

埋め込まれていたBRU wb typo

age matrixを入れてrunしたら... 2命令retireから増えない。deadlock状況は同じ。

debug printsを追加して、issueはrob 2 (ADDI x3) がoldestとして選ばれて発火しているのに、ROBのr_rob[0][1].doneが1に立たない、という現象を突き止めた。

原因はage matrixとは無関係で、top moduleのBRU writeback構築のtypo:

always_comb begin
  w_wb_result[1] = 'h0;
  w_wb_result[1].valid  = w_iss_valid[0];   // ← [0] はtypo、[1] が正
  w_wb_result[1].rob_id = w_iss_uop[1].rob_id;
  ...
end

BRUのwb portはindex 1なのに、validだけport 0の値を追随していた。結果、BRUが全くissueしていないcycleでもwb.valid[1]=1が立ち、rob_idはw_iss_uop[1] (IQ port 1の出力 = stale値) から取られて、bank 0 / row 2のような「たまたま」ヒットするROB entryをwb扱いする形になっていた。

ROBはper-bankのwb collectorで「該当bankにwbしているport」の情報を集めるが、複数portが同じbankを触った場合は最後にヒットしたportがw_wr_ports_entry_idxを上書きする:

for (int w = 0; w < PRF_WRITE_PORTS; w++) begin
  if (w_rob_wr_valid[w] & (w_rob_wr_bank_idx[w] == b_idx[BW-1:0])) begin
    w_wr_ports_valid = 1'b1;
    w_wr_ports_entry_idx = w_rob_wr_entry_idx[w];   // 上書き
  end
end

port 0 (ALU) がrob 2 (bank 0 row 1) をwbしていても、port 1 (BRU) がspuriousにwb.valid=1かつbank_idx=0 (別のrow) を報告すると、w_wr_ports_entry_idxがその別rowで上書きされて、rob 2のdoneがsetされない。

Typo 1文字 ([0] → [1]) 直しただけで、pipelineが4命令完走した。

Age matrixのdebugに時間を取られてBRU wb typoに気付くのに時間がかかったが、教訓としては:

• 統合debugでは「一番怪しい所」以外にも複数bugが同居している可能性を常に念頭に
• wb busのように複数producerで共有するpathは、片方のspurious出力が他方のkeyに影響を及ぼす形になりがち。valid gatingを厳密にする

検証結果

Top module smoke testでADDI × 4が全部retire:

[75000] commit lane[0]: rd=x1 ...
[85000] commit lane[0]: rd=x2 ...
[95000] commit lane[0]: rd=x3 ...
[105000] commit lane[0]: rd=x4 ...
=== tb_scariv_top : 1 tests, 0 fail, 4 retired ===
PASS

Regression全16 TB pass、累計196k+ tests / 0 fail。