BOOMの分岐予測機構について調べる (1. BOOMの分岐予測の構成)

BOOMの分岐予測について、boom-docs.orgを読みながら解き明かしていこうと思う。

BOOMの分岐予測器は大きく分けて2種類に分類される。

Next Line Predictor (NLP) : 1サイクルで予測できる高速分岐予測器
- 分岐ターゲットバッファ(BTB)、リターンアドレススタック(RAS)、Bi-Modalテーブル(BIM)の3種類で構成されている。
- 1サイクルの高速分岐だが、その分面積効率を重視していない。
Backing Predictor (BPD) : 数サイクル掛けて予測する分岐予測器
- Gshare分岐予測、TAGE分岐予測、その他の分岐予測、で構成される。
- 数サイクル掛けて分岐予測を行うため低速だが、その分精度は高い。

まずはNLPの方から読み解いていく。

NLPは、分岐予測に関する情報をBTB (Branch Target Buffer)によって管理している。 BTBのインデックスとして使用するPCアドレスは分岐命令自身ではなく、その分岐命令が含まれているフェッチブロックの先頭命令となる。まあこれはハードウェアの簡素化のための処置だと思われる。

以下の図には、いくつかのフィールドが用意されているようだ。

PC tagsはPC値が一致するかどうかを検証するためのタグ
val は validの意味だと思われる
ret は関数から戻る命令に関する情報だと思われる
jmp 無条件分岐？
bidx 分岐タグのことだろうか
target ジャンプ先のアドレス

BTBの更新タイミングはBPDに依存しているようだ。BTBが予測しても、後段のBPDによって分岐またはジャンプが成立すると予測された場合にのみ更新される。

RASの更新は、命令をフェッチしてデコードにより関数コールが識別された段階で更新される。

BOOMの実装

次に、Chiselのコードを読みながら少し読み進めていく。 BOOMの分岐予測器は以下でインスタンス化されている。

boom/src/main/scala/ifu/frontend.scala

class BoomFrontendModule(outer: BoomFrontend) extends LazyModuleImp(outer)
  with HasBoomCoreParameters
  with HasBoomFrontendParameters
{
  val io = IO(new BoomFrontendBundle(outer))
  val io_reset_vector = outer.resetVectorSinkNode.bundle
  implicit val edge = outer.masterNode.edges.out(0)
  require(fetchWidth*coreInstBytes == outer.icacheParams.fetchBytes)

  val bpd = Module(new BranchPredictor)
  bpd.io.f3_fire := false.B
  val ras = Module(new BoomRAS)
/* ... 以下略 ... */

BranchPredictorの中身を見てみる。BranchPredictorは、フェッチする命令の単位に応じてバンクが分けられている。

class BranchPredictor(implicit p: Parameters) extends BoomModule()(p)
 with HasBoomFrontendParameters
{
  val io = IO(new Bundle {
/* ... */
  val banked_predictors = (0 until nBanks) map ( b => {
    val m = Module(if (useBPD) new ComposedBranchPredictorBank else new NullBranchPredictorBank)
    for ((n, d, w) <- m.mems) {
      bpdStr.append(BoomCoreStringPrefix(f"bank$b $n: $d x $w = ${d * w / 8}"))
      total_memsize = total_memsize + d * w / 8
    }
    m
  })

このComposedBranchPredictorBankは以下のように定義されている。

boom/src/main/scala/ifu/bpd/composer.scala

class ComposedBranchPredictorBank(implicit p: Parameters) extends BranchPredictorBank()(p)
{

  val (components, resp) = getBPDComponents(io.resp_in(0), p)
  io.resp := resp

/* ... 以下省略 ... */

さらにgetBPDComponentsは以下のように定義されている。つまり、boomParamのbranchPredictor`によって制御されているということになる。

boom/src/main/scala/common/parameters.scala

  def getBPDComponents(resp_in: BranchPredictionBankResponse, p: Parameters) = {
    boomParams.branchPredictor(resp_in, p)
  }

これをさらに参照する。例えばMediumBoomConfigの場合だと、

boom/src/main/scala/common/config-mixins.scala

/**
 * 2-wide BOOM.
 */
class WithNMediumBooms(n: Int = 1, overrideIdOffset: Option[Int] = None) extends Config(
  new WithTAGELBPD ++ // Default to TAGE-L BPD
/* ... 以下省略 ... */

WithTAGELBPDということは、以下のclassがmixinしているということになる。

class WithTAGELBPD extends Config((site, here, up) => {
  case TilesLocated(InSubsystem) => up(TilesLocated(InSubsystem), site) map {
    case tp: BoomTileAttachParams => tp.copy(tileParams = tp.tileParams.copy(core = tp.tileParams.core.copy(
      bpdMaxMetaLength = 120,
      globalHistoryLength = 64,
      localHistoryLength = 1,
      localHistoryNSets = 0,
      branchPredictor = ((resp_in: BranchPredictionBankResponse, p: Parameters) => {
        val loop = Module(new LoopBranchPredictorBank()(p))
        val tage = Module(new TageBranchPredictorBank()(p))
        val btb = Module(new BTBBranchPredictorBank()(p))
        val bim = Module(new BIMBranchPredictorBank()(p))
        val ubtb = Module(new FAMicroBTBBranchPredictorBank()(p))
        val preds = Seq(loop, tage, btb, ubtb, bim)
        preds.map(_.io := DontCare)

        ubtb.io.resp_in(0)  := resp_in
        bim.io.resp_in(0)   := ubtb.io.resp
        btb.io.resp_in(0)   := bim.io.resp
        tage.io.resp_in(0)  := btb.io.resp
        loop.io.resp_in(0)  := tage.io.resp

        (preds, loop.io.resp)
      })
    )))
    case other => other
  }
})