Rocket Core : BTB(Branch Target Buffer)

gs要加油呀

IP属地: 四川

0.0682020.02.17 15:27:22字数 1,512阅读 7,776

前言

关于Rocket Chip中的BTB模块，已经有前辈整理得很清楚了，可以参照开源处理器Rocket的分支预测机制研究与性能评估这一系列文章，本文仅仅稍微补充一点点代码上的实现细节，并配上一些图片供大家食用。

Rocket中分支预测模块概要

Rocket Core 中，BTB主要分为三个部分

1. BTB：Branch Target Buffer

2. BHT：Branch History Table

3. RAS：Return Address Stack

其中，
BTB与BHT都是针对branch指令进行分支预测(很多设计中将两者整合，作为一个模块)

• BTB主要记录分支指令跳转目标地址(即：往哪里跳? branch target)

• BHT则决定是否采用BTB的目标地址跳转(即：跳不跳?taken or not taken)

RAS相对独立，是针对与函数调用有关的JAL和JALR指令进行预测执行。

Rocket Core中将这三者整合成一个模块，模块名称就叫BTB，为了不引起歧义，下面所说的BTB都是指其中的子模块，而不是Rocket Core中整合成的大模块。

1. BTB

在课上讲解得BTB基本原理大概都如下图所示那样，与Cache设计思路类似，BTB取PC其中k位作为buffer的entry，读出Entry PC与当前PC比对，若相等则可取出目标地址来预测。

BTB基本原理

基本原理比较清晰易懂，但是存在一个较大的问题，Buffer太大，会浪费相当多的存储资源，体现在两个方面：

1. Buffer 每一项位宽太宽：Enrty PC和target PC位宽都是32。

2. Buffer中的PC高位存在冗余：对于branch指令，跳转范围有限，地址高位(页号部分)通常不会改变

为了解决这个问题，Rocket Chip中重新设计了下面这种方案：

BTB Register Model

与基本原理图最明显的区别在于：

1. idx不作为buffer的入口地址，而是与全相联的idxs逐一比对形成独热码idxHit

2. BTB 与页号(图中pages即页号)分离存储，BTB中通过指针指向对应页号(图中红色弧线：idxPages、tgtPages为指向pages的指针)

1.1 PC划分

在Rocket Core中，PC切分方式如下：

Rocket Core中PC划分方式

根据Rocket Generator配置不同，PC位宽为32或39，主要分为了三部分

1. coreInstBytes:指令字节，由于使用压缩指令(2字节), 对齐位1bit

2. idx(tgt)，idx不作为入口地址!!!(代码中tgt、target也对应此字段)

3. page，即页号

1.2 命中检测(hit or miss)

虽然页号(pages)与buffer独立管理维护，但是两者都采用全相联的命中检测方法：逐一比对，生成独热码。
BTB中定义了idxMatch 与 pageMatch两个方法，可以检查一个pc地址page字段与idx字段是否命中。

idxMatch 与 pageMatch

 private def page(addr: UInt) = addr >> matchBits  private def pageMatch(addr: UInt) = {    val p = page(addr)    pageValid & pages.map(_ === p).asUInt  }  private def idxMatch(addr: UInt) = {    val idx = addr(matchBits-1, log2Up(coreInstBytes))    idxs.map(_ === idx).asUInt & isValid  }  val pageHit = pageMatch(io.req.bits.addr)  val idxHit = idxMatch(io.req.bits.addr)

若命中，则直接读出BTB对应项target，返回给Frontend

 io.resp.valid := (pageHit << 1)(Mux1H(idxHit, idxPages))  io.resp.bits.target := Cat(pages(Mux1H(idxHit, tgtPages)), Mux1H(idxHit, tgts) << log2Up(coreInstBytes))  io.resp.bits.entry := OHToUInt(idxHit) // 若idxHit不命中，entry为0

1.3 替换策略

页号(pages)和BTB buffer也有不同的替换策略。

1.3.1 替换时机

首先介绍一下替换时机，BTB的更新与流水线两个阶段相关：

1. IF Stage：Predication

2. WB Stage ：BTB Updating

取指令阶段只读不写，若BTB不命中，不会改变BTB。
写回阶段才会更新BTB和独立管理的页号(pages)。

读源码小技巧：IF Stage 与WB Stage信号名区别，主要看有没有update
IF Stage相关信号名：

• pc相关：io.req.bits.addr(update_target)

• pages相关：pageHit、usePageHit

• idx相关： idxHit

WB Stage相关信号名：

• pc相关：r_btb_update.bits.pc

• pages相关：updatePageHit、useUpdatePageHit

• idx相关：updateHitAddr

• entry相关：waddr

1.3.2 BTB buffer替换策略：PseudoLRU

Rocket Chip中采用一个伪LRU的算法，不展开。

 val repl = new PseudoLRU(entries)  val waddr = Mux(updateHit, updateHitAddr, repl.replace)  val r_resp = Pipe(io.resp)  when (r_resp.valid && r_resp.bits.taken || r_btb_update.valid) {    repl.access(Mux(r_btb_update.valid, waddr, r_resp.bits.entry))  }

1.3.2 pages替换策略：nextPageRepl + Rotation Method

pages替换策略分为两部分：

1. 当idxMatch 不命中时，使用一个nextPageRepl指针

2. 当idxMatch 命中时，采用Rotation Method

nextPageRepl是一个寄存器，指向下一次替换的位置，由于idx和target都有指向pages的指针，可能都需要更新：

1. 若两者只更新一个，指针加1

2. 若两者都更新，指针加2

相关代码：

 // pages指针nextPageRepl更新策略  when (r_btb_update.valid && (doIdxPageRepl || doTgtPageRepl)) {    val both = doIdxPageRepl && doTgtPageRepl    val next = nextPageRepl + Mux[UInt](both, 2, 1)    nextPageRepl := Mux(next >= nPages, next(0), next)  }

另外还有一个这部分我也没完全理解透orz，大体上类似下图这个

Replacement Policy: Rotation Method

比较迷惑的是中间的一个Rotator循环移位，参考论文：An Optimal CAM-based Separated BTB for a Superscalar Processor
对应代码

 // 这里采用了Rotation Method  val idxPageRepl = Cat(pageHit(nPages-2,0), pageHit(nPages-1)) | Mux(usePageHit, UInt(0), UIntToOH(nextPageRepl))  val idxPageUpdateOH = Mux(useUpdatePageHit, updatePageHit, idxPageRepl)  val idxPageUpdate = OHToUInt(idxPageUpdateOH)  val idxPageReplEn = Mux(doIdxPageRepl, idxPageRepl, UInt(0))  val samePage = page(r_btb_update.bits.pc) === page(update_target)  val doTgtPageRepl = !samePage && !usePageHit  val tgtPageRepl = Mux(samePage, idxPageUpdateOH, Cat(idxPageUpdateOH(nPages-2,0), idxPageUpdateOH(nPages-1)))  val tgtPageUpdate = OHToUInt(pageHit | Mux(usePageHit, UInt(0), tgtPageRepl))  val tgtPageReplEn = Mux(doTgtPageRepl, tgtPageRepl, UInt(0))

2. BHT

BHT模块比较简单，Rocket Chip中封装成一个class，定义了接口。BHT大致结构如下：

BHT示意图

• history是历史预测结果的pattern，采用比特串表示，如history为b'1110,则历史预测结果为taken、taken、taken、not taken

• counter table是一组counter ,用计数器表示本次分支是否预测跳转

2.1 BHT大致原理

BHT基于历史预测结果(history)和当前pc值，读取counter table预测当前分支是否采用BTB的预测结果。

1. 为了使history和addr都对预测结果有影响，Rocket Chip中index方法采用hash函数，是两者起作用。

2. index函数得到入口地址后，再用get函数打包成BHTResp处理

2.2 counter table 更新策略

Rocket Chip中BHT内置了两种counter (1-bit 和 2-bit)，可通过参数params.counterLength配置，参考代码：

 // 根据分支预测的结果更新表  def updateTable(addr: UInt, d: BHTResp, taken: Bool): Unit = {    // 通过match case模式匹配来选择使用预测器    table(index(addr, d.history)) := (params.counterLength match {      // 1-bit:Last-Time Prediction      case 1 => taken      // 2-bit counter (这里不是饱和计算)      case 2 => Cat(taken ^ d.value(0), d.value === 1 || d.value(1) && taken)    })  }

2.3 history 更新策略

由于分支指令需要到EX Stage才能真正resolve，history 更新策略采用speculative的方式

1. 当分支指令流入指令Buffer时，就提前更新history(advanceHistory),同时将旧的history随流水线传递下去

2. 若预测结果正确，则采用更新后的history(即不变化)

3. 若预测失败，则用随流水线传递的旧history恢复原样

RAS

前面已经写了相关文章，参考Rocket Core : RAS(Return Address Stack)

最后编辑于 ：2020.02.17 15:28:50

PA-RISC Processors

• Overview

• Early PA-RISC

• PA-7000

• PA-7100

• PA-7100LC

• PA-7200

• PA-7300LC

• PA-8000

• PA-8200

• PA-8500

• PA-8600

• PA-8700

• PA‑8800

• PA-8900

• Third Party

PA-8700 (PCX-W2) processor

Overview

The PA-8700 processor is an 64-bit HP PA-RISC processor from HP, released in 2001 building on an enhanced PA-8500 core with several modifications. As with other PA-8x00 processors, the logic core is close to the original PA-8000 from 1997. The PA-8700 used significant larger on-chip L1 caches and TLB while switching to a new manufacturing process at IBM helped increase the clock speed. At its time it was one of the largest available commercial processors and one of the first manufactured in Silicon on Insulator (SoI). It is superscalar (4-way) and multi-processor (SMP) capable.

Details

• PA-RISC version 2.0, 64-bit architecture, multi-processor capable, 4-way superscalar

• Ten functional units: 2 integer ALUs, 2 shift/merge units, 2 complete load/store pipelines, 2 Floating Point multiply/accumulate units, 2 Floating Point divide/square root units

• IRB: 56-entry instruction queue/reorder buffer

• TLB: 240-entry fully-associative dual-ported

• BTAC: 32-entry Branch Target Address Cache; BHT: 2048-entry Branch History Table

• Cache 0.75 MB instruction and 1.5 MB data L1 on-chip, 4-way set associative, in independent 0.75 MB banks.

• Memory up to 16 TB supported with 44-bit physical addresses

• Memory and I/O controllers are external

• Bi-endian support

• MAX-2 multimedia extensions subword arithmetic for multimedia applications

• Runway+ system bus, 125 MHz, 64-bit, DDR, about 2.0 GB/s peak bandwidth

• Up to 750 MHz, 875 MHz on the PA-8700+ clock speed with 1.5 V core voltage

• 16.0×19.0 mm2 die, 186,000,000 FETs, 0.18µ, 7-layer Silicon-on-Insulator CMOS packaged in a 544-pin LGA package

Used in

• HP 9000 A400-6X (rp2430), A500-6X, A500-7X (rp2470), rp2405 servers

• HP 9000 C3650, C3700, C3750 workstations

• HP 9000 J6700 workstations

• HP 9000 L1500-6X, L1500-7X, L1500-8X (rp5430), L3000-6X, L3000-7X, L3000-8X (rp5470) servers

• HP 9000 N4000-6X, N4000-7X (rp7400) servers

• HP 9000 N4000-6X, N4000-7X, N4000-8X (rp7405, rp7410) servers

• HP 9000 Superdome mainframes (SD16000, SD32000, SD64000)

References

1. A 900 MHz 2.25 MByte Cache with On Chip CPU (PDF, 119 KB) J. Michael Hill and Jonathan Lachman (2000: ISSCC)

2. PA-RISC 2.0 Architecture (.pdf) Hewlett-Packard Company (1995)

3. HP taps new foundry for PA-RISC processors, EE Times, August 2001