雷思磊

(酒泉衛(wèi)星發(fā)射中心，酒泉 735000)

開源處理器Rocket的分支預(yù)測(cè)機(jī)制與性能評(píng)估

雷思磊

(酒泉衛(wèi)星發(fā)射中心，酒泉 735000)

Rocket是基于RISC-V指令集架構(gòu)的開源處理器，具有分支預(yù)測(cè)功能，其實(shí)現(xiàn)了GShare分支預(yù)測(cè)機(jī)制，在分析Rocket處理器分支預(yù)測(cè)處理過(guò)程、分支預(yù)測(cè)實(shí)現(xiàn)原理的基礎(chǔ)上，利用模擬器進(jìn)行了性能測(cè)試，并依據(jù)測(cè)試結(jié)果，對(duì)Rocket處理器分支預(yù)測(cè)參數(shù)配置給出建議。

Rocket; 分支預(yù)測(cè); Chisel

引 言

RISC-V是加州大學(xué)伯克利分校(University of California at Berkeley，UCB)設(shè)計(jì)并發(fā)布的一種開源精簡(jiǎn)指令集架構(gòu)，其目標(biāo)是成為指令集架構(gòu)領(lǐng)域的Linux，應(yīng)用覆蓋IoT(Internet of Things)設(shè)備、桌面計(jì)算機(jī)、高性能計(jì)算機(jī)等眾多領(lǐng)域[1]。RISC-V自2014年正式發(fā)布以來(lái)，受到了包括谷歌、IBM、Oracle等在內(nèi)的眾多企業(yè)，以及包括劍橋大學(xué)、蘇黎世聯(lián)邦理工大學(xué)、印度理工學(xué)院、中國(guó)科學(xué)院在內(nèi)的眾多知名學(xué)府與研究機(jī)構(gòu)的關(guān)注和參與，RISC-V的生態(tài)環(huán)境逐漸完善，眾多開源處理器及SoC均采用了RISC-V架構(gòu)。Rocket就是采用RISC-V指令集的開源處理器，本文研究分析了Rocket處理器中分支預(yù)測(cè)機(jī)制的實(shí)現(xiàn)原理，并對(duì)其性能進(jìn)行了測(cè)試評(píng)估。

1 Rocket處理器簡(jiǎn)介

Rocket是UCB設(shè)計(jì)的一款基于RISC-V指令集、5級(jí)流水線、單發(fā)射順序執(zhí)行64位處理器，主要特點(diǎn)有：支持MMU和支持分頁(yè)虛擬內(nèi)存，可以移植Linux操作系統(tǒng)；具有兼容IEEE 754-2008標(biāo)準(zhǔn)的FPU；具有分支預(yù)測(cè)功能，具有BTB(Branch Prediction Buffer)、BHT(Branch History Table)、RAS(Return Address Stack)。

Rocket是采用Chisel(Constructing Hardware in an Scala Embedded Language)編寫的，這也是UCB設(shè)計(jì)的一種開源的硬件編程語(yǔ)言，是Scala語(yǔ)言的領(lǐng)域特定應(yīng)用，可以充分利用Scala的優(yōu)勢(shì)，將面向?qū)ο?object orientation)、函數(shù)式編程(functional programming)、類型參數(shù)化(parameterized types)、類型推斷(type inference)等概念引入硬件編程語(yǔ)言，從而提供更加強(qiáng)大的硬件開發(fā)能力。Chisel除了開源之外，還有一個(gè)優(yōu)勢(shì)就是使用Chisel編寫的硬件電路，可以通過(guò)編譯得到對(duì)應(yīng)的Verilog設(shè)計(jì)，還可以得到對(duì)應(yīng)的C++模擬器。Rocket使用Chisel編寫，可以很容易得到對(duì)應(yīng)的軟件模擬器[2]。本文對(duì)于分支預(yù)測(cè)機(jī)制的性能評(píng)估就是使用編譯得到的軟件模擬器進(jìn)行實(shí)驗(yàn)的。

2 GShare分支預(yù)測(cè)機(jī)制

分支預(yù)測(cè)是處理器用來(lái)提高執(zhí)行速度的一種機(jī)制，其對(duì)程序的分支流程進(jìn)行預(yù)測(cè)，然后預(yù)先讀取其中一個(gè)分支的指令并解碼，從而避免了流水線的空閑等待，也就相應(yīng)提高了處理器的整體執(zhí)行速度。但是，一旦分支指令結(jié)果出來(lái)表明前期分支預(yù)測(cè)是錯(cuò)誤的，那么就必須將已經(jīng)進(jìn)入流水線執(zhí)行的指令和結(jié)果全部清除，然后再裝入正確的指令重新處理，這樣會(huì)消耗處理器額外的時(shí)鐘周期，所以提高分支預(yù)測(cè)準(zhǔn)確率是一項(xiàng)十分重要的工作。分支預(yù)測(cè)可以分為靜態(tài)分支預(yù)測(cè)、動(dòng)態(tài)分支預(yù)測(cè)。GShare[3]是Scott Mcfarling于1993年提出的一種動(dòng)態(tài)分支預(yù)測(cè)機(jī)制，也是Rocket處理器采用的分支預(yù)測(cè)機(jī)制，包括BTB、BHT兩部分。對(duì)于一條指令，首先查詢BTB，如果命中，表示是分支指令，那么再查詢BHT，預(yù)測(cè)分支是否發(fā)生，BHT的內(nèi)容及預(yù)測(cè)機(jī)制如圖1所示。

圖1 GShare分支預(yù)測(cè)機(jī)制

將分支指令的地址取出n位，與分支歷史移位寄存器(BHSR：Branch History Shift Register)的n位進(jìn)行異或運(yùn)算，運(yùn)算結(jié)果作為索引，查詢模式歷史表(PHT：Pattern History Table)，PHT中使用的是2位飽和計(jì)數(shù)器，其狀態(tài)變化如圖2所示。如果查詢的結(jié)果是00或者01，那么預(yù)測(cè)分支不發(fā)生；如果查詢的結(jié)果是10或者11，那么預(yù)測(cè)分支發(fā)生。根據(jù)分支指令實(shí)際運(yùn)行結(jié)果更新BHSR、PHT的相關(guān)內(nèi)容。

圖2 2位飽和計(jì)數(shù)器

3 Rocket處理器分支預(yù)測(cè)機(jī)制分析

3.1 分支預(yù)測(cè)機(jī)制設(shè)計(jì)分析

Rocket處理器除了實(shí)現(xiàn)BTB、BHT，還實(shí)現(xiàn)了RAS，都在BTB Module中實(shí)現(xiàn)，BTB Module的接口以及與Rocket Core的連接如圖3所示。Rocket處理器主要在流水線的取指、訪存兩個(gè)階段使用到BTB Module。

圖3 BTB Module與Rocket Core的連接關(guān)系

3.1.1 取指階段

將取指階段的指令地址通過(guò)Req送到BTB Module，后者進(jìn)行如下判斷(如圖4所示)：

① 查詢BTB是否有對(duì)應(yīng)的指令地址，如果有，那么進(jìn)行下一步驟。

② 如果是返回指令，那么將RAS堆棧頂部的數(shù)據(jù)返回，作為目標(biāo)地址，反之，進(jìn)行下一步驟。

③ 如果是jal、jalr這兩條絕對(duì)轉(zhuǎn)移指令，那么設(shè)置taken為true，表示轉(zhuǎn)移發(fā)生，目標(biāo)地址是BTB查詢的結(jié)果，反之，進(jìn)行下一步驟。

④ 按照?qǐng)D1進(jìn)行查詢，依據(jù)BHT的查詢結(jié)果，判斷是否發(fā)生轉(zhuǎn)移，如果轉(zhuǎn)移，那么設(shè)置taken為true，轉(zhuǎn)移目標(biāo)地址為BTB查詢的結(jié)果，反之，設(shè)置taken為false。無(wú)論是否轉(zhuǎn)移，均更新BHT中的BHSR。

⑤ 將上述判斷結(jié)果通過(guò)resp返回給Rocket Core，后者據(jù)此決定下一條指令的地址。

圖4 取指階段BTB Module的處理過(guò)程

3.1.2 訪存階段

當(dāng)分支指令進(jìn)入訪存階段后，Rocket Core可以判斷出前期的分支預(yù)測(cè)是否正確，從而更新BTB Module中相應(yīng)的內(nèi)容，更新消息是通過(guò)btb_update、bht_update、ras_update送入BTB Module的，分別代表更新BTB、BHT、RAS。假設(shè)分支指令是B，跳轉(zhuǎn)指令是J、返回指令是R，那么可以分為如下幾種情況：

① B在取指階段沒(méi)有在BTB查詢命中，并且實(shí)際分支結(jié)果是not taken。此時(shí)不更新BTB，僅僅更新BHT，即圖1中的BHSR，以及對(duì)應(yīng)的模式歷史表中的表項(xiàng)，按照?qǐng)D2的2位飽和計(jì)數(shù)器的狀態(tài)機(jī)進(jìn)行更新。

② B在取指階段沒(méi)有在BTB查詢命中，并且實(shí)際分支結(jié)果是taken。此時(shí)更新BTB、BHT，其中BHT的更新內(nèi)容同情況①，對(duì)于BTB而言，需要在其中新增一個(gè)表項(xiàng)，其中存儲(chǔ)指令B的地址與分支目標(biāo)地址。

③ B在取指階段在BTB查詢命中，實(shí)際分支結(jié)果與預(yù)測(cè)結(jié)果不一致，此時(shí)更新BTB、BHT，其中BHT的更新內(nèi)容同情況①，對(duì)于BTB而言，需要更新其中存儲(chǔ)的指令B對(duì)應(yīng)的目標(biāo)地址。

④ B在取指階段在BTB查詢命中，實(shí)際分支結(jié)果與預(yù)測(cè)結(jié)果一致，此時(shí)不更新BTB，僅僅更新BHT，更新內(nèi)容同情況①。

⑤ J在取指階段沒(méi)有在BTB查詢命中。此時(shí)將更新BTB，在其中新增一個(gè)表項(xiàng)，將指令J的地址及跳轉(zhuǎn)的目標(biāo)地址寫入該表項(xiàng)，同時(shí)將當(dāng)前指令地址加4，結(jié)果存入RAS堆棧頂部。

⑥ J在取指階段在BTB查詢命中，并且目標(biāo)地址預(yù)測(cè)正確。此時(shí)將當(dāng)前指令地址加4，結(jié)果存入RAS堆棧頂部。

⑦ J在取指階段在BTB查詢命中，但是目標(biāo)地址預(yù)測(cè)錯(cuò)誤。此時(shí)將更新BTB，將其中存儲(chǔ)的指令J對(duì)應(yīng)的目標(biāo)地址更新為新的地址，同時(shí)，將當(dāng)前指令地址加4，結(jié)果存入RAS堆棧頂部。

⑧ R在取指階段沒(méi)有在BTB查詢命中。此時(shí)將更新BTB，在其中新增一個(gè)表項(xiàng)，將指令R的地址及跳轉(zhuǎn)的目標(biāo)地址寫入該表項(xiàng)。

⑨ R在取指階段在BTB查詢命中，并且目標(biāo)地址預(yù)測(cè)正確。此時(shí)將RAS堆棧頂部的數(shù)據(jù)出棧。

⑩ R在取指階段在BTB查詢命中，但是目標(biāo)地址預(yù)測(cè)錯(cuò)誤。此時(shí)將更新BTB，將其中存儲(chǔ)的指令R對(duì)應(yīng)的目標(biāo)地址更新為新的地址。

3.2 BTB Module分析

在BTB Module中實(shí)現(xiàn)了BTB、BHT、RAS，其中RAS就是一個(gè)簡(jiǎn)單的堆棧，本文不再單獨(dú)分析，重點(diǎn)分析BTB、BHT。

3.2.1 BHT分析

通過(guò)BHT類實(shí)現(xiàn)了BHT，其實(shí)現(xiàn)的就是圖1所示的GShare分支預(yù)測(cè)算法，其中重點(diǎn)的方法是get，通過(guò)get方法返回預(yù)測(cè)結(jié)果，通過(guò)以下片段可以理解GShare的基本過(guò)程。

def get(addr: UInt, update: Bool): BHTResp = {

val res = Wire(new BHTResp)

val index = addr(nbhtbits+1, log2Up(coreInstBytes)) ^ history //指令地址的低位與BHSR進(jìn)行異或

res.value := table(index)

//異或的結(jié)果作為查詢模式歷史表的索引

res.history := history

val taken = res.value(0)

//依據(jù)查詢結(jié)果，判斷分支是否taken

when (update) { history :=Cat(taken, history(nbhtbits-1,1)) }

res

}

3.2.2 BTB分析

Rocket通過(guò)一系列數(shù)組實(shí)現(xiàn)了BTB，為了便于分析，假設(shè)BTB的表項(xiàng)是64，此時(shí)會(huì)有如圖5所示的一系列數(shù)組。以idx開始的數(shù)組表示是與分支指令有關(guān)，以tgt開始的數(shù)組表示是與分支目標(biāo)地址有關(guān)，其含義如下。

idxs：64項(xiàng)，存儲(chǔ)的是分支指令地址的第2～11位，實(shí)際應(yīng)該是低12位，但是指令是4字節(jié)的，所以最低2位可以忽略。

idxPages：64項(xiàng)，與idxs一一對(duì)應(yīng)，每一項(xiàng)是3位，是一個(gè)索引，指向pages數(shù)組，后者存儲(chǔ)的是分支指令地址的高27位。

idxPagesOH：64項(xiàng)，與idxPages一一對(duì)應(yīng)，每一項(xiàng)是6位，實(shí)際就是idxPages中對(duì)應(yīng)數(shù)據(jù)的one-hot編碼，是為了加快查詢pages數(shù)組的速度而設(shè)計(jì)的。

idxValid：64項(xiàng)，與idxs一一對(duì)應(yīng)，每一項(xiàng)是1位，表示對(duì)應(yīng)的idxs是否有效。

tgts：64項(xiàng)，存儲(chǔ)的是分支目標(biāo)地址的第2～11位，實(shí)際應(yīng)該是低12位，但是指令是4字節(jié)的，所以最低2位可以忽略。

tgtPages：64項(xiàng)，與tgts一一對(duì)應(yīng)，每一項(xiàng)是3位，是一個(gè)索引，指向pages數(shù)組，其中存儲(chǔ)的是分支目標(biāo)地址的高27位。

tgtPagesOH：64項(xiàng)，與tgtPages一一對(duì)應(yīng)，每一項(xiàng)是6位，實(shí)際就是tgtPages中對(duì)應(yīng)數(shù)據(jù)的one-hot編碼，是為了加快查詢pages數(shù)組的速度而設(shè)計(jì)的。

pages：6項(xiàng)，存儲(chǔ)的是分支指令地址或者分支目標(biāo)地址的高27位，RISC-V中定義虛擬地址是39位，在idxs中已有低位的10位，此外最低2bit忽略，所以就是27位。

pagesValid：6項(xiàng)，與pages一一對(duì)應(yīng)，表示對(duì)應(yīng)的pages是否有效。

圖5 實(shí)現(xiàn)BTB的一系列數(shù)組

從圖5中可以發(fā)現(xiàn)，Rocket將地址分為低位、高位兩部分，其中高位存儲(chǔ)在pages中，并且pages的表項(xiàng)顯著小于idxs、tgts，從而減少BTB占用的芯片資源。每次進(jìn)行BTB查詢的時(shí)候，首先將分支指令地址的低位與idxs中的表項(xiàng)一一比較，如果有相等項(xiàng)，再通過(guò)對(duì)應(yīng)的idxPages表項(xiàng)檢索pages數(shù)組，進(jìn)行地址高位的比較，如果也相等，那么表示BTB查詢命中，反之，BTB查詢沒(méi)有命中。當(dāng)BTB查詢命中的時(shí)候，就可以通過(guò)tgts數(shù)組得到分支目標(biāo)地址。

4 Rocket處理器分支預(yù)測(cè)機(jī)制性能評(píng)估

4.1 評(píng)估環(huán)境

Rocket使用Chisel編寫，所以可以很容易得到對(duì)應(yīng)的C++模擬器，本文使用得到的C++模擬器，運(yùn)行RISC-V提供的benchmark，以測(cè)試分支預(yù)測(cè)性能。默認(rèn)的Rocket編譯后并不會(huì)輸出分支預(yù)測(cè)有關(guān)的信息，需要在rocket.scala添加如下代碼：

val counter0 = WideCounter(64, mem_reg_valid && !take_pc_wb && mem_ctrl.branch)

val counter1 = WideCounter(64, mem_reg_valid && !take_pc_wb && mem_ctrl.branch && mem_wrong_npc)

printf("branch inst number[%x] ", counter0)

printf("misprediction branch inst number[%x] ", counter1)

上述代碼定義了兩個(gè)計(jì)數(shù)器，第一個(gè)計(jì)數(shù)器counter0，當(dāng)訪存階段是分支指令的時(shí)候加1，第二個(gè)計(jì)數(shù)器counter1，當(dāng)訪存階段是分支指令，且分支預(yù)測(cè)錯(cuò)誤的時(shí)候加1，所以，上述兩個(gè)計(jì)數(shù)器可以分別輸出分支指令數(shù)、分支預(yù)測(cè)錯(cuò)誤指令數(shù)。

4.2 分支預(yù)測(cè)機(jī)制性能評(píng)估

BTB的表項(xiàng)數(shù)量不同，會(huì)影響分支預(yù)測(cè)的準(zhǔn)確率，分別取BTB的表項(xiàng)為40、60、120，其分支預(yù)測(cè)效果如圖6所示。當(dāng)BTB的表項(xiàng)為默認(rèn)的40的時(shí)候，最差情況為0.815，最好情況為0.991；當(dāng)BTB的表項(xiàng)為60的時(shí)候，最差情況為0.813，最好情況為0.991；當(dāng)BTB的表項(xiàng)為120的時(shí)候，最差情況為0.819，最好情況為0.992。并且，從圖6中可以發(fā)現(xiàn)對(duì)于一個(gè)特定的測(cè)試程序，當(dāng)BTB表項(xiàng)增加的時(shí)候，其分支預(yù)測(cè)準(zhǔn)確率相對(duì)有所提高。

在實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn)如果BTB表項(xiàng)數(shù)目是2的冪，那么分支預(yù)測(cè)準(zhǔn)確率會(huì)急劇下降，如圖7所示，分別取BTB表項(xiàng)為32、64、128，與BTB表項(xiàng)為40時(shí)的分支預(yù)測(cè)效果對(duì)比。原因是由于BTB Module中如下一段代碼引起的。

val nextRepl =

if (!isPow2(entries)) {

Counter(r_btb_update.valid && !updateHit, entries)._1 //BTB表項(xiàng)不是2的冪的時(shí)候的替換算法

} else {

val plru = new PseudoLRU(entries)

//BTB表項(xiàng)是2的冪時(shí)的替換算法

when (hits.orR) { plru.access(OHToUInt(hits)) }

plru.replace

}

其中計(jì)算nextRepl的值，如果當(dāng)前更新的分支指令在BTB中沒(méi)有查詢到，那么就從BTB中找出一個(gè)表項(xiàng)，用來(lái)存儲(chǔ)這個(gè)新的分支指令，nextRepl計(jì)算的就是這個(gè)新的表項(xiàng)的序號(hào)。如果BTB的表項(xiàng)是2的冪，那么替換算法是偽最近最少使用算法(PseudoLRU)；反之，替換算法就是簡(jiǎn)單地累加。算法的不同，導(dǎo)致最終效果的差異，建議使用的時(shí)候可以避免設(shè)置BTB表項(xiàng)的值為2的冪。

圖6 當(dāng)BTB表項(xiàng)是40、60、120的時(shí)候的分支預(yù)測(cè)效果

圖7 當(dāng)BTB表項(xiàng)是40、32、64、128的時(shí)候的分支預(yù)測(cè)效果

結(jié) 語(yǔ)

[1] VIBU Isa，A Waterman，Y Lee， et al.The RISC-V Instruction Set Manual, Volume I: User-Level ISA, Version 2.1[EB/OL].[2016-12].http://www.atmel.com/Images/doc0856.pdf.

[2] Chisel 2.2 Tutorial[EB/OL].[2016-12].https://chisel.eecs.berkeley.edu/2.2.0/chisel-tutorial. 2016-10.

[3] S McFarling. Combining Branch Predictors, Technical Report TN-36[J].Compaq Western Research Laboratory, 1993, 26(4):176-188.

Performance Evaluation of Branch Prediction Mechanism for Open-source Processor Rocket

Lei Silei

(Jiuquan Satellite Launch Center,Jiuquan 735000,China)

The Rocket is an open-source processor based on RISC-V instruction set architecture,it has branch prediction function,it implements the GShare branch prediction mechanism.In the analysis of the Rocket processor branch prediction process,branch prediction based on the principle of performance,the tests are carried out by the simulator,.According to the test results,the suggestions on the configuration of Rocket processor branch prediction parameters are given.

Rocket;branch prediction;Chisel

TP368.1

A

?迪娜

2016-12-28)