Rocket Core : BTB(Branch Target Buffer)
Rocket Core : BTB(Branch Target Buffer)
gs要加油呀
IP屬地: 四川
0.0682020.02.17 15:27:22字?jǐn)?shù) 1,512閱讀 7,776
前言
關(guān)于Rocket Chip中的BTB模塊，已經(jīng)有前輩整理得很清楚了，可以參照開源處理器Rocket的分支預(yù)測機(jī)制研究與性能評估這一系列文章，本文僅僅稍微補(bǔ)充一點(diǎn)點(diǎn)代碼上的實(shí)現(xiàn)細(xì)節(jié)，并配上一些圖片供大家食用。
Rocket中分支預(yù)測模塊概要
Rocket Core 中，BTB主要分為三個(gè)部分
BTB：Branch Target Buffer
BHT：Branch History Table
RAS：Return Address Stack
其中，
BTB與BHT都是針對branch指令進(jìn)行分支預(yù)測(很多設(shè)計(jì)中將兩者整合，作為一個(gè)模塊)
BTB主要記錄分支指令跳轉(zhuǎn)目標(biāo)地址(即：往哪里跳? branch target)
BHT則決定是否采用BTB的目標(biāo)地址跳轉(zhuǎn)(即：跳不跳?taken or not taken)
RAS相對獨(dú)立，是針對與函數(shù)調(diào)用有關(guān)的JAL和JALR指令進(jìn)行預(yù)測執(zhí)行。
Rocket Core中將這三者整合成一個(gè)模塊，模塊名稱就叫BTB，為了不引起歧義，下面所說的BTB都是指其中的子模塊，而不是Rocket Core中整合成的大模塊。
1. BTB
在課上講解得BTB基本原理大概都如下圖所示那樣，與Cache設(shè)計(jì)思路類似，BTB取PC其中k位作為buffer的entry，讀出Entry PC與當(dāng)前PC比對，若相等則可取出目標(biāo)地址來預(yù)測。
BTB基本原理
基本原理比較清晰易懂，但是存在一個(gè)較大的問題，Buffer太大，會浪費(fèi)相當(dāng)多的存儲資源，體現(xiàn)在兩個(gè)方面：
Buffer 每一項(xiàng)位寬太寬：Enrty PC和target PC位寬都是32。
Buffer中的PC高位存在冗余：對于branch指令，跳轉(zhuǎn)范圍有限，地址高位(頁號部分)通常不會改變
為了解決這個(gè)問題，Rocket Chip中重新設(shè)計(jì)了下面這種方案：
BTB Register Model
與基本原理圖最明顯的區(qū)別在于：
idx不作為buffer的入口地址，而是與全相聯(lián)的idxs逐一比對形成獨(dú)熱碼idxHit
BTB 與頁號(圖中pages即頁號)分離存儲，BTB中通過指針指向?qū)?yīng)頁號(圖中紅色弧線：idxPages、tgtPages為指向pages的指針)
1.1 PC劃分
在Rocket Core中，PC切分方式如下：
Rocket Core中PC劃分方式
根據(jù)Rocket Generator配置不同，PC位寬為32或39，主要分為了三部分
coreInstBytes:指令字節(jié)，由于使用壓縮指令(2字節(jié)), 對齊位1bit
idx(tgt)，idx不作為入口地址!!!(代碼中tgt、target也對應(yīng)此字段)
page，即頁號
1.2 命中檢測(hit or miss)
雖然頁號(pages)與buffer獨(dú)立管理維護(hù)，但是兩者都采用全相聯(lián)的命中檢測方法：逐一比對，生成獨(dú)熱碼。
BTB中定義了idxMatch 與 pageMatch兩個(gè)方法，可以檢查一個(gè)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對應(yīng)項(xiàng)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 替換時(shí)機(jī)
首先介紹一下替換時(shí)機(jī)，BTB的更新與流水線兩個(gè)階段相關(guān)：
IF Stage：Predication
WB Stage ：BTB Updating
取指令階段只讀不寫，若BTB不命中，不會改變BTB。
寫回階段才會更新BTB和獨(dú)立管理的頁號(pages)。
讀源碼小技巧：IF Stage 與WB Stage信號名區(qū)別，主要看有沒有update
IF Stage相關(guān)信號名：
pc相關(guān)：io.req.bits.addr(update_target)
pages相關(guān)：pageHit、usePageHit
idx相關(guān)： idxHit
WB Stage相關(guān)信號名：
pc相關(guān)：r_btb_update.bits.pc
pages相關(guān)：updatePageHit、useUpdatePageHit
idx相關(guān)：updateHitAddr
entry相關(guān)：waddr
1.3.2 BTB buffer替換策略：PseudoLRU
Rocket Chip中采用一個(gè)偽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替換策略分為兩部分：
當(dāng)idxMatch 不命中時(shí)，使用一個(gè)nextPageRepl指針
當(dāng)idxMatch 命中時(shí)，采用Rotation Method
nextPageRepl是一個(gè)寄存器，指向下一次替換的位置，由于idx和target都有指向pages的指針，可能都需要更新：
若兩者只更新一個(gè)，指針加1
若兩者都更新，指針加2
相關(guān)代碼：
?// 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)
?}
另外還有一個(gè)這部分我也沒完全理解透orz，大體上類似下圖這個(gè)
Replacement Policy: Rotation Method
比較迷惑的是中間的一個(gè)Rotator循環(huán)移位，參考論文：An Optimal CAM-based Separated BTB for a Superscalar Processor
對應(yīng)代碼
?// 這里采用了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中封裝成一個(gè)class，定義了接口。BHT大致結(jié)構(gòu)如下：
BHT示意圖
history是歷史預(yù)測結(jié)果的pattern，采用比特串表示，如history為b'1110,則歷史預(yù)測結(jié)果為taken、taken、taken、not taken
counter table是一組counter ,用計(jì)數(shù)器表示本次分支是否預(yù)測跳轉(zhuǎn)
2.1 BHT大致原理
BHT基于歷史預(yù)測結(jié)果(history)和當(dāng)前pc值，讀取counter table預(yù)測當(dāng)前分支是否采用BTB的預(yù)測結(jié)果。
為了使history和addr都對預(yù)測結(jié)果有影響，Rocket Chip中index方法采用hash函數(shù)，是兩者起作用。
index函數(shù)得到入口地址后，再用get函數(shù)打包成BHTResp處理
2.2 counter table 更新策略
Rocket Chip中BHT內(nèi)置了兩種counter (1-bit 和 2-bit)，可通過參數(shù)params.counterLength配置，參考代碼：
?// 根據(jù)分支預(yù)測的結(jié)果更新表
?def updateTable(addr: UInt, d: BHTResp, taken: Bool): Unit = {
? ?// 通過match case模式匹配來選擇使用預(yù)測器
? ?table(index(addr, d.history)) := (params.counterLength match {
? ? ?// 1-bit:Last-Time Prediction
? ? ?case 1 => taken
? ? ?// 2-bit counter (這里不是飽和計(jì)算)
? ? ?case 2 => Cat(taken ^ d.value(0), d.value === 1 || d.value(1) && taken)
? ?})
?}
2.3 history 更新策略
由于分支指令需要到EX Stage才能真正resolve，history 更新策略采用speculative的方式
當(dāng)分支指令流入指令Buffer時(shí)，就提前更新history(advanceHistory),同時(shí)將舊的history隨流水線傳遞下去
若預(yù)測結(jié)果正確，則采用更新后的history(即不變化)
若預(yù)測失敗，則用隨流水線傳遞的舊history恢復(fù)原樣
RAS
前面已經(jīng)寫了相關(guān)文章，參考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
A 900?MHz 2.25?MByte Cache with On Chip CPU (PDF, 119?KB) J. Michael Hill and Jonathan Lachman (2000: ISSCC)
PA-RISC 2.0 Architecture (.pdf) Hewlett-Packard Company (1995)
HP taps new foundry for PA-RISC processors, EE Times, August 2001
