プロセッサアーキテクチャについて再度復習その7。分岐予測の基本について学んだので、実際の実装を見てみたいと思う。

RISC-VのアウトオブオーダBOOMの実装を眺めてみることにした。こちらはChiselをベースにしているので読み解くのは少し厄介だが、できない事は無い。

今回見てみる実装はGshareである。これはriscv-boom/src/main/scala/bpu/bpd/gshare/gshare.scalaに格納されている。

gshare分岐予測器

ベースとなるクラス。br-predictor.scalaが基底クラスとなっている。GShareBrPredictorはBoomBrPredictorから派生している。

boom/src/main/scala/bpu/bpd/br-predictor.scala

abstract class BoomBrPredictor(
   val historyLength: Int)(implicit p: Parameters) extends BoomModule
{
...

boom/src/main/scala/bpu/bpd/tage/gshare.scala

class GShareBrPredictor(
   historyLength: Int = 12
   )(implicit p: Parameters)
   extends BoomBrPredictor(historyLength)
   with HasGShareParameters
{

GShareのパラメータ

GShareを構成するにあたり、必要なのは以下のパラメータだ。

historyLength : Global History Registerのサイズ。デフォルトでは12ビット。
numSets : GShareのPattern History Tableのサイズ。デフォルトでは4096エントリ。

GShareのRAMはTAGEと異なり1つだけである。分岐予測に対してインデックスの計算方法が異なる。

boom-template/boom/src/main/scala/bpu/bpd/gshare/gshare.scala

  //------------------------------------------------------------
  // Predictor state.

  val counter_table = SyncReadMem(nSets, UInt(rowSz.W))

RAMの横幅はfetchWidthの2倍である。

/**
 * Trait to inherit parameters from the configuration
 */
trait HasGShareParameters extends HasBoomCoreParameters
{
  val gsParams = boomParams.gshare.get
  // prevent us from building something too big (and taking millions of cycles to initialize!)
  val nSets = gsParams.numSets

  val idxSz = log2Ceil(nSets)
  val rowSz = fetchWidth*2
}

予測前の初期化。ステートマシンによりテーブルの初期化を行う。

  val s_reset :: s_wait :: s_clear :: s_idle :: Nil = Enum(4)
  val fsm_state = RegInit(s_reset)
  val nResetLagCycles = 64
  val nBanks = 1
  val (lag_counter, lag_done) = Counter(fsm_state === s_wait, nResetLagCycles)
  val (clear_row_addr, clear_done) = Counter(fsm_state === s_clear, numEntries/nBanks)

  switch (fsm_state) {
    is (s_reset) { fsm_state := s_wait }
    is (s_wait)  { when (lag_done) { fsm_state := s_clear } }
    is (s_clear) { when (clear_done) { fsm_state := s_idle } }
    is (s_idle)  { when (io.do_reset) { fsm_state := s_clear } }
  }

リセット後にステートマシンがs_waitに代わり、64サイクル待つ(リセットの非同期対応？)。次にs_clearステートに移り、テーブルのエントリを1つずつ初期化する。すべてが完了すると、s_idle状態に遷移し、定常状態に移る。

予測の手順

分岐予測のリクエストに対して、現在のフェッチしたPCとグローバルヒストリレジスタの値をハッシュし、RAMアクセスのインデックスを決める。

  private def Hash (addr: UInt, hist: UInt) = {
    // fold history if too big for our table
    val folded_history = Fold (hist, idxSz, historyLength)
    ((addr >> (log2Ceil(fetchWidth*coreInstBytes).U)) ^ folded_history)(idxSz-1,0)
  }
...
  val s1_ridx = Hash(this.r_f1_fetchpc, this.r_f1_history)

リクエストが来ると、まずはRAMをReadして予測値を引っ張ってくる。これには1サイクルが消費される。

  // return data to superclass (via f2_resp bundle).
  val s2_out = counter_table.read(s1_ridx, this.f1_valid)

これをElasticRegという2エントリのQueueのようなものに挿入し、この値をそのまま返して予測値とする。

予測のアップデート

予測のアップデートは、TAGEと同様にコミット時に行う。コミット時の予測更新信号に応じて、カウンタをアップデートする。もとのカウンタの値はパイプラインの外に出て行って戻ってきたものをそのまま使用し、これにアップデートの論理をかけてRAMに再度格納する。

  val com_info = (io.commit.bits.info).asTypeOf(new GShareResp(fetchWidth, idxSz))
  val com_idx = Hash(io.commit.bits.fetch_pc, io.commit.bits.history)(idxSz-1,0)

  val wen = io.commit.valid || (fsm_state === s_clear)
  when (wen) {
    val new_row = updateEntireCounterRow(
      com_info.rowdata,
      io.commit.bits.mispredict,
      io.commit.bits.miss_cfi_idx,
      io.commit.bits.taken)

    val waddr = Mux(fsm_state === s_clear, clear_row_addr, com_idx)
    val wdata = Mux(fsm_state === s_clear, initRowValue(), new_row)

    counter_table.write(waddr, wdata)
  }

  // Pick out the old counter value from a full row and increment it.
  // Return the new row.
  private def updateCounterInRow(old_row: UInt, cfi_idx: UInt, taken: Bool): UInt = {
    val row = Wire(UInt(rowSz.W))
    val shamt = cfi_idx << 1.U
    val mask = Wire(UInt(rowSz.W))
    mask := ~(0x3.U << shamt)
    val old_cntr = (old_row >> shamt) & 0x3.U
    val new_cntr = updateCounter(old_cntr, taken)
    row := (old_row & mask) | (new_cntr << shamt)
    row
  }