パイプライン##
以下、パイプラインステージを<>で表すことにする。
分岐予測器を読み始めようと思ったが、やはり基本のパイプラインの構造理解が必要だと感じたので、パイプラインの頭から読み始めようと思う。クロックの両エッジを使っていることに注意。<IF>の立ち上がりエッジからの前半がPC確定であり、立下りエッジからの後半が(1)IMEMを引くIfetch、(2)分岐先を引くBTB、(3)予測テーブルを引くPred、(4)シーケンシャル側PCの計算の4つを並行に行い、(3)に従い(2)または(4)を選択し、Next PCを決定する。
<IF>##
ということで、<IF>から。ソースはsrc/fpga/pipeline_if.v。Next PC選択器についてソースを読む。RTL読書会ではあるが、理解のため回路図を見てみよう。上部はこれから説明するnext PC論理、その下にbtb、sellog, gshのサブモジュールの他、PCをハッシュするためのXORが見えている。
Next PC###
assign npc = (hit && predict_cond) ? pred_pc :
invalid2 ? pc + 4 : pc + 8;
回路図の上部に表れている。verilogはCと同様に3項演算子が使用可能である。前述のように、hitかつ分岐予測器が分岐側と判定したら分岐予測PCを、そうでなければシーケンシャル側PCを選択する。シーケンシャル側PCはワードクロスの場合はinst1(1word)しか取れていないので、Next PCを1ワード先(PC+4)の2ワード目にする。そうでなければ2word取れているので、Next PCを2ワード先(PC+8)の3ワード目とする。
ちなみに、上位のパイプライン構造(pipeline.v)で記述されているが、ストール時にPCの値を変えない選択論理がある。上位パイプライン部の論理は以下のとおり。
assign stall_IF = stall_ID | stall_DP;
assign kill_IF = prmiss;
always @ (posedge clk) begin
if (reset) begin
pc <= `ENTRY_POINT;
end else if (prmiss) begin
pc <= jmpaddr;
end else if (stall_IF) begin
pc <= pc;
end else begin
pc <= npc;
end
end
説明するまでもないような論理だが、リセット時にはエントリアドレスをPCに入れ、prmiss(分岐予測ミス=非予測分岐時)の場合には非予測分岐先アドレスをPCに入れる。次が前述のパイプラインストールの場合であり、個々のパイプラインステージ内の論理には依らず、ステージ間の依存関係によるウエイト(ストール)の状況により、ステージの進行を止めている。最後に<IF>で決定されたNext PCの値をPCに入れている。
余談であるが、昔会社でパイプラインウェイトの論理を下流ステージから上流ステージへ向かってORを取って伝える、別の言い方をすれば、前(先行)の命令が後続の命令を止める、という話をしたら、後の命令が前の命令を止めても良いのではないかと同僚に言われたことがあった。これはNGで先行命令は止めずに流さなければならない。
Select Logic###
次にセレクトロジックのインスタンスがある。回路図では右まんなかあたり。
select_logic sellog(
.sel(pc[3:2]),
.idata(idata),
.inst1(inst1),
.inst2(inst2),
.invalid(invalid2)
);
実体は同じファイル中の以下の部分。何の選択かというと、4word並列の命令バッファ(inmem)からPCアドレスを索引として4wordをフェッチし、そのうちの2wordをPCの[3:2]を用いて選択する命令選択である。
module select_logic
(
input wire [1:0] sel,
input wire [4*`INSN_LEN-1:0] idata,
output reg [`INSN_LEN-1:0] inst1,
output reg [`INSN_LEN-1:0] inst2,
output wire invalid
);
assign invalid = (sel[0] == 1'b1);
always @ (*) begin
inst1 = `INSN_LEN'h0;
inst2 = `INSN_LEN'h0;
case(sel)
2'b00 : begin
inst1 = idata[31:0];
inst2 = idata[63:32];
end
2'b01 : begin
inst1 = idata[63:32];
inst2 = idata[95:64];
end
2'b10 : begin
inst1 = idata[95:64];
inst2 = idata[127:96];
end
2'b11 : begin
inst1 = idata[127:96];
inst2 = idata[31:0];
end
endcase // case (sel)
end
endmodule // select_logic
PCのミスアラインに応じて、4命令のうち取り出し位置を変えinst1, inst2の2命令を選択している。ソース中の
assign invalid = (sel[0] == 1'b1);
これは、以下の波形にも表れているように、ダブルワードミスアラインした場合(+4番地、+C番地)に、2ワード目を無効にするもの。+4番地の場合は2ワード目はvalidであるため、4ワード(ロングワードとする)ミスアラインした場合(+C番地)のみ2ワード目を無効とするものかと思ったが、+4番地で取れても次はロングワードミスアラインするため、このようになっているのかな？分岐先が常に+4番地の分岐が頻発した際に性能劣化にならないか、やや気になる。
次がBTBと分岐予測器である2つの加速器のインスタンスである。
btb brtbl(
.clk(clk),
.reset(reset),
.pc(pc),
.hit(hit),
.jmpaddr(pred_pc),
.we(btbpht_we),
.jmpsrc(btbpht_pc),
.jmpdst(btb_jmpdst),
.invalid2(invalid2)
);
gshare_predictor gsh
(
.clk(clk),
.reset(reset),
.pc(pc),
.hit_bht(hit),
.predict_cond(predict_cond),
.we(btbpht_we),
.wcond(pht_wcond),
.went(btbpht_pc[2+:`GSH_BHR_LEN] ^ pht_bhr),
.mpft_valid(mpft_valid),
.prmiss(prmiss),
.prsuccess(prsuccess),
.prtag(prtag),
.bhr_master(bhr),
.spectagnow(spectagnow)
);
お気づきになったかもしれない。冒頭で<IF>後半の立下りエッジでBTBもGshareも検索すると述べたが、このように立ち上がりエッジで動作するような、分岐予測のサブモジュールが実装されている。PCが立ち上がりで確定して、命令バッファや加速器が立ち上がりエッジでそれを使用すると、1サイクル無駄になるが実際はそうではなく、後述するサブモジュール内部で立下りエッジでメモリを検索しているため、冒頭の説明のようになる。
ようやくソースコード読書会になってきたものの、分岐予測の中身までほとんどたどり着かなかったが、ゆっくりとしたペースで進めて行きたい。
追記：
今日はkrste Asanovic教授の講演が聞けて大変良かった。色々なプロジェクトが進行中のようである。RISC-V祭りをやりたい。Matsuriといえばこんなのがイメージ。http://2017.scalamatsuri.org/