##分岐予測器##
いよいよ本題の分岐予測器に入ってきた。分岐予測器はこの読書会で言うところの加速器の一種で、分岐予測器の出力結果により、BTB(分岐先バッファ)で検索された分岐先を使うか使わないかを決定することになる。ソースコードはgshare.v。分岐予測やGshareについてはWikipediaに書かれている。
https://ja.wikipedia.org/wiki/%E5%88%86%E5%B2%90%E4%BA%88%E6%B8%AC

###sel_bhrfix###
サブモジュールを2個説明する。まずbhrfixは、分岐履歴レジスタの内容を選択するロジック。選択する理由は、分岐予測ミスした場合に分岐履歴レジスタを元に戻すためとのこと。

module sel_bhrfix(
		  input wire [4:0] 		sel,
		  input wire [`GSH_BHR_LEN-1:0] bhr0,
		  input wire [`GSH_BHR_LEN-1:0] bhr1,
		  input wire [`GSH_BHR_LEN-1:0] bhr2,
		  input wire [`GSH_BHR_LEN-1:0] bhr3,
		  input wire [`GSH_BHR_LEN-1:0] bhr4,
		  output reg [`GSH_BHR_LEN-1:0] out
		  );
   always @ (*) begin
      out = 0;
      case (sel)
	5'b00001 : out = bhr0;
	5'b00010 : out = bhr1;
	5'b00100 : out = bhr2;
	5'b01000 : out = bhr3;
	5'b10000 : out = bhr4;
	default : out = 0;
      endcase // case (sel)
   end
   
endmodule // sel_bhr

上記のように分岐履歴レジスタ(BHR)が5個あり、sel信号によりそのうちのいずれかを選択する組み合わせロジック。この5個は投機タグの個数と対応しているようだが、まだ読んでいないため後で分かってくると思われる。

###pht###
phtはパターン履歴テーブル。パターン履歴とは、2bit飽和型カウンタの配列であり、2bit飽和型カウンタの理由は、分岐側を予測して非分岐で外れても一度だけならまだ分岐側を予測する。2度連続して外れると、今度は非分岐側が確率が高いと判断し、非分岐と予測するためのステートマシンを構成するためのものである。

(前記論文から引用)

module pht(
	   input wire 			 clk,
	   input wire [`GSH_PHT_SEL-1:0] raddr_if,
	   input wire [`GSH_PHT_SEL-1:0] raddr_ex,
	   input wire [`GSH_PHT_SEL-1:0] waddr_ex,
	   output wire [1:0] 		 rdata_if,
	   output wire [1:0] 		 rdata_ex,
	   input wire [1:0] 		 wdata_ex,
	   input wire 			 we_ex
	   );
   
   true_dualport_ram #(`GSH_PHT_SEL, 2, `GSH_PHT_NUM) pht0
     (
      .clka(~clk),
      .addra(raddr_if),
      .rdataa(rdata_if),
      .wdataa(),
      .wea(1'b0),
      .clkb(clk),
      .addrb(waddr_ex),
      .rdatab(),
      .wdatab(wdata_ex),
      .web(we_ex)
      );
   
   true_dualport_ram #(`GSH_PHT_SEL, 2, `GSH_PHT_NUM) pht1
     (
      .clka(~clk),
      .addra(raddr_ex),
      .rdataa(rdata_ex),
      .wdataa(),
      .wea(1'b0),
      .clkb(clk),
      .addrb(waddr_ex),
      .rdatab(),
      .wdatab(wdata_ex),
      .web(we_ex)
      );
   
endmodule // pht

デュアルポートRAMを2個インスタンスしており、ひとつずつはA系とB系のアドレスとクロックを持つ、1R1WのRAMを2個使いし、同じデータ(<EX>のライト)をそれぞれに同時にライトし、それぞれから別のデータ(<EX>と<IF>のリード)を同時に読み出す、2R1WデュアルポートRAMとしている。

クロックの立下りでA系が動作していることが良くわかる。

###gshare_predictor###
ここから、Gshare分岐予測器本体。BHRを戻すための組み合わせ論理のサブモジュールと、PHTのサブモジュール及びBHRで構成されている。

//PRTAG is tag of prmiss/success branch instruction's
module gshare_predictor
  (
   input wire 			 clk,
   input wire 			 reset,
   input wire [`ADDR_LEN-1:0] 	 pc,
   input wire 			 hit_bht,
   output wire 			 predict_cond,
   input wire 			 we,
   input wire 			 wcond,
   input wire [`GSH_PHT_SEL-1:0] went,
   input wire [`SPECTAG_LEN-1:0] mpft_valid,
   input wire 			 prmiss,
   input wire 			 prsuccess,
   input wire [`SPECTAG_LEN-1:0] prtag,
   output reg [`GSH_BHR_LEN-1:0] bhr_master,
   input wire [`SPECTAG_LEN-1:0] spectagnow
   );

   reg [`GSH_BHR_LEN-1:0] 	 bhr0;
   reg [`GSH_BHR_LEN-1:0] 	 bhr1;
   reg [`GSH_BHR_LEN-1:0] 	 bhr2;
   reg [`GSH_BHR_LEN-1:0] 	 bhr3;
   reg [`GSH_BHR_LEN-1:0] 	 bhr4;
   wire [`GSH_BHR_LEN-1:0] 	 bhr_fix;
   wire [1:0] 			 rif;
   wire [1:0] 			 rex;
   wire [1:0] 			 wex;
   wire [2:0] 			 wex_calc;
   
   sel_bhrfix sb(
		 .sel(prtag),
		 .bhr0(bhr0),
		 .bhr1(bhr1),
		 .bhr2(bhr2),
		 .bhr3(bhr3),
		 .bhr4(bhr4),
		 .out(bhr_fix)
		 );
   
   always @ (posedge clk) begin
      if (reset) begin
	 bhr0 <= 0;
	 bhr1 <= 0;
	 bhr2 <= 0;
	 bhr3 <= 0;
	 bhr4 <= 0;
	 bhr_master <= 0;
      end else if (prmiss) begin
	 bhr0 <= bhr_fix;
	 bhr1 <= bhr_fix;
	 bhr2 <= bhr_fix;
	 bhr3 <= bhr_fix;
	 bhr4 <= bhr_fix;
	 bhr_master <= bhr_fix;
      end else if (prsuccess) begin
	 bhr0 <= (prtag == 5'b00001) ? {bhr_master[`GSH_BHR_LEN-2:0], predict_cond} : bhr0; 
	 bhr1 <= (prtag == 5'b00010) ? {bhr_master[`GSH_BHR_LEN-2:0], predict_cond} : bhr1;
	 bhr2 <= (prtag == 5'b00100) ? {bhr_master[`GSH_BHR_LEN-2:0], predict_cond} : bhr2;
	 bhr3 <= (prtag == 5'b01000) ? {bhr_master[`GSH_BHR_LEN-2:0], predict_cond} : bhr3;
	 bhr4 <= (prtag == 5'b10000) ? {bhr_master[`GSH_BHR_LEN-2:0], predict_cond} : bhr4;
      end else if (hit_bht) begin
	 if (we & mpft_valid[0]) begin
	    bhr0 <= {bhr0[`GSH_BHR_LEN-2:0], predict_cond};
	 end
	 if (we & mpft_valid[1]) begin
	    bhr1 <= {bhr1[`GSH_BHR_LEN-2:0], predict_cond};
	 end
	 if (we & mpft_valid[2]) begin
	    bhr2 <= {bhr2[`GSH_BHR_LEN-2:0], predict_cond};
	 end
	 if (we & mpft_valid[3]) begin
	    bhr3 <= {bhr3[`GSH_BHR_LEN-2:0], predict_cond};
	 end
	 if (we & mpft_valid[4]) begin
	    bhr4 <= {bhr4[`GSH_BHR_LEN-2:0], predict_cond};
	 end
	 if (we) begin
	    bhr_master <= {bhr_master[`GSH_BHR_LEN-2:0], predict_cond};
	 end
      end
   end

分岐履歴レジスタの記述。基本的には分岐履歴を格納しておく10bitのシフトレジスタを構成している。ここは他モジュールからの信号をシフト条件に使用しているため、理解が進んでから追記したい。例えばprmissやprsuccessは<EX>の分岐命令の結果としての信号であるため、<EX>の解読が必要となる。mpftは、miss prediction fix table(予測失敗回復表)の省略のようである。

   assign predict_cond = (hit_bht && (rif > 2'b01)) ? 1'b1 : 1'b0;

rifは<if>での2bit飽和型カウンタ読み出し値であり、それが2または3である場合は図1で示すように、分岐側と予測する。predict_condは分岐側と予測した場合に1となる。

   assign wex_calc = {1'b0, rex} + (wcond ? 3'b001 : 3'b111);
   assign wex = ((rex == 2'b00) && ~wcond) ? 2'b00 :
		((rex == 2'b11) && wcond) ? 2'b11 : wex_calc[1:0];

分岐履歴レジスタの書き込み値wexの計算。読み出し値rexに応じて、2bit飽和加減算させた値を計算し、<EX>で書き込む。なぜ3bitに拡張しているのだろうか。単に2bit飽和演算をすれば良いだけと思うが。

加算したMSBは使用していないため、合成時に最適化されて除去されているのがわかる。

   pht prhisttbl
     (
      .clk(clk),
      .raddr_if(pc[2+:`GSH_BHR_LEN] ^ bhr_master),
      .raddr_ex(went),
      .waddr_ex(went),
      .rdata_if(rif),
      .rdata_ex(rex),
      .wdata_ex(wex),
      .we_ex(we)
      );
   

endmodule // gshare_predictor

前述のとおり、2bit飽和型カウンタのインスタンス(サブモジュール)。実態は1R1Wメモリを2個使い、2bitの2R1Wメモリを構成している。値の検索にPCと分岐履歴レジスタのXORを取り入力している。

(前記論文より再掲)
最後にGshare分岐予測器の全体像を示す。

###BOOMの2bitカウンタ###
おっと、見逃すところだった。BOOMの2bitカウンタは状態遷移がWikipediaや上図と違っているし、誤記がある。誤記は修正するとして、状態遷移は間違っていないとすれば、どちらが性能が良いのだろう?パッと見ではわからないから、取り換えて性能を見るしかないかな?

ソースコード読書会らしく、ソースコードを見てみよう。といってもChisel(Scala)で書かれているんだけど。

 def update(index: UInt, value: UInt, taken: Bool): Unit =
   {
      // LSB gives the taken/not-taken prediction (p-bit).
      // MSB gives "how strongly" biased the counter is.
      table(index(idx_sz-1, 0)) := Cat(taken, (value(1) & value(0)) | ((value(1) | value(0)) & taken))
   }

やはり、状態遷移図のとおり実装されていたことが判明した。これは飽和カウンタではなく、taken, not takenの強度が飽和カウンタよりも強い。

###追記###
RIDECOREの参考文献となっていた"Modern Processor Design"が届いたので、早速当該箇所をみてみたら、2ビットのヒストリーFSMを持つ分岐予測器の構成として2^20個もある構成のうち、5248個がまずまず有用なものだったようだ。6個のSPECベンチマークを実行してみると、ベンチマークによって最大性能を出したFSM構成は異なるが、6個のうち3個で同じ構成が最大性能となり、それは2bit飽和型カウンタであった。つまり、RIDECOREのそれと同じ構成であり、BOOMの構成は残念ながら6個のうちのどれにも該当しない。平均的に良いのかもしれないが。いずれにしろ参考文献では2bit飽和型カウンタが良いと書かれている。

##今後の予定##

RIDECOREのソースコード読書
Chizelの勉強
FPGAボードの動作確認
Vivadoに慣れる
Rocket Coreのソースコード読書
BOOMのソースコード読書
何らかの題材のソースコード読書
自作チップの実装、デバッグ、Linuxのブート
機能安全、自動運転向け車載マイコンの設計

読書会(4)はこちら
https://qiita.com/mocapapa/items/e8580e03d5f176b2baf7