開源處理器Rocket的分支預測機制與性能評估

雷思磊

(酒泉衛星發射中心，酒泉 735000)

開源處理器Rocket的分支預測機制與性能評估

雷思磊

(酒泉衛星發射中心，酒泉 735000)

Rocket是基于RISC-V指令集架構的開源處理器，具有分支預測功能，其實現了GShare分支預測機制，在分析Rocket處理器分支預測處理過程、分支預測實現原理的基礎上，利用模擬器進行了性能測試，并依據測試結果，對Rocket處理器分支預測參數配置給出建議。

Rocket; 分支預測; Chisel

引 言

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

1 Rocket處理器簡介

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

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

2 GShare分支預測機制

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

圖1 GShare分支預測機制

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

圖2 2位飽和計數器

3 Rocket處理器分支預測機制分析

3.1 分支預測機制設計分析

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

圖3 BTB Module與Rocket Core的連接關系

3.1.1 取指階段

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

① 查詢BTB是否有對應的指令地址，如果有，那么進行下一步驟。

② 如果是返回指令，那么將RAS堆棧頂部的數據返回，作為目標地址，反之，進行下一步驟。

③ 如果是jal、jalr這兩條絕對轉移指令，那么設置taken為true，表示轉移發生，目標地址是BTB查詢的結果，反之，進行下一步驟。

④ 按照圖1進行查詢，依據BHT的查詢結果，判斷是否發生轉移，如果轉移，那么設置taken為true，轉移目標地址為BTB查詢的結果，反之，設置taken為false。無論是否轉移，均更新BHT中的BHSR。

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

圖4 取指階段BTB Module的處理過程

3.1.2 訪存階段

當分支指令進入訪存階段后，Rocket Core可以判斷出前期的分支預測是否正確，從而更新BTB Module中相應的內容，更新消息是通過btb_update、bht_update、ras_update送入BTB Module的，分別代表更新BTB、BHT、RAS。假設分支指令是B，跳轉指令是J、返回指令是R，那么可以分為如下幾種情況：

① B在取指階段沒有在BTB查詢命中，并且實際分支結果是not taken。此時不更新BTB，僅僅更新BHT，即圖1中的BHSR，以及對應的模式歷史表中的表項，按照圖2的2位飽和計數器的狀態機進行更新。

② B在取指階段沒有在BTB查詢命中，并且實際分支結果是taken。此時更新BTB、BHT，其中BHT的更新內容同情況①，對于BTB而言，需要在其中新增一個表項，其中存儲指令B的地址與分支目標地址。

③ B在取指階段在BTB查詢命中，實際分支結果與預測結果不一致，此時更新BTB、BHT，其中BHT的更新內容同情況①，對于BTB而言，需要更新其中存儲的指令B對應的目標地址。

④ B在取指階段在BTB查詢命中，實際分支結果與預測結果一致，此時不更新BTB，僅僅更新BHT，更新內容同情況①。

⑤ J在取指階段沒有在BTB查詢命中。此時將更新BTB，在其中新增一個表項，將指令J的地址及跳轉的目標地址寫入該表項，同時將當前指令地址加4，結果存入RAS堆棧頂部。

⑥ J在取指階段在BTB查詢命中，并且目標地址預測正確。此時將當前指令地址加4，結果存入RAS堆棧頂部。

⑦ J在取指階段在BTB查詢命中，但是目標地址預測錯誤。此時將更新BTB，將其中存儲的指令J對應的目標地址更新為新的地址，同時，將當前指令地址加4，結果存入RAS堆棧頂部。

⑧ R在取指階段沒有在BTB查詢命中。此時將更新BTB，在其中新增一個表項，將指令R的地址及跳轉的目標地址寫入該表項。

⑨ R在取指階段在BTB查詢命中，并且目標地址預測正確。此時將RAS堆棧頂部的數據出棧。

⑩ R在取指階段在BTB查詢命中，但是目標地址預測錯誤。此時將更新BTB，將其中存儲的指令R對應的目標地址更新為新的地址。

3.2 BTB Module分析

在BTB Module中實現了BTB、BHT、RAS，其中RAS就是一個簡單的堆棧，本文不再單獨分析，重點分析BTB、BHT。

3.2.1 BHT分析

通過BHT類實現了BHT，其實現的就是圖1所示的GShare分支預測算法，其中重點的方法是get，通過get方法返回預測結果，通過以下片段可以理解GShare的基本過程。

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

val res = Wire(new BHTResp)

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

res.value := table(index)

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

res.history := history

val taken = res.value(0)

//依據查詢結果，判斷分支是否taken

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

res

}

3.2.2 BTB分析

Rocket通過一系列數組實現了BTB，為了便于分析，假設BTB的表項是64，此時會有如圖5所示的一系列數組。以idx開始的數組表示是與分支指令有關，以tgt開始的數組表示是與分支目標地址有關，其含義如下。

idxs：64項，存儲的是分支指令地址的第2～11位，實際應該是低12位，但是指令是4字節的，所以最低2位可以忽略。

idxPages：64項，與idxs一一對應，每一項是3位，是一個索引，指向pages數組，后者存儲的是分支指令地址的高27位。

idxPagesOH：64項，與idxPages一一對應，每一項是6位，實際就是idxPages中對應數據的one-hot編碼，是為了加快查詢pages數組的速度而設計的。

idxValid：64項，與idxs一一對應，每一項是1位，表示對應的idxs是否有效。

tgts：64項，存儲的是分支目標地址的第2～11位，實際應該是低12位，但是指令是4字節的，所以最低2位可以忽略。

tgtPages：64項，與tgts一一對應，每一項是3位，是一個索引，指向pages數組，其中存儲的是分支目標地址的高27位。

tgtPagesOH：64項，與tgtPages一一對應，每一項是6位，實際就是tgtPages中對應數據的one-hot編碼，是為了加快查詢pages數組的速度而設計的。

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

pagesValid：6項，與pages一一對應，表示對應的pages是否有效。

圖5 實現BTB的一系列數組

從圖5中可以發現，Rocket將地址分為低位、高位兩部分，其中高位存儲在pages中，并且pages的表項顯著小于idxs、tgts，從而減少BTB占用的芯片資源。每次進行BTB查詢的時候，首先將分支指令地址的低位與idxs中的表項一一比較，如果有相等項，再通過對應的idxPages表項檢索pages數組，進行地址高位的比較，如果也相等，那么表示BTB查詢命中，反之，BTB查詢沒有命中。當BTB查詢命中的時候，就可以通過tgts數組得到分支目標地址。

4 Rocket處理器分支預測機制性能評估

4.1 評估環境

Rocket使用Chisel編寫，所以可以很容易得到對應的C++模擬器，本文使用得到的C++模擬器，運行RISC-V提供的benchmark，以測試分支預測性能。默認的Rocket編譯后并不會輸出分支預測有關的信息，需要在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)

上述代碼定義了兩個計數器，第一個計數器counter0，當訪存階段是分支指令的時候加1，第二個計數器counter1，當訪存階段是分支指令，且分支預測錯誤的時候加1，所以，上述兩個計數器可以分別輸出分支指令數、分支預測錯誤指令數。

4.2 分支預測機制性能評估

BTB的表項數量不同，會影響分支預測的準確率，分別取BTB的表項為40、60、120，其分支預測效果如圖6所示。當BTB的表項為默認的40的時候，最差情況為0.815，最好情況為0.991；當BTB的表項為60的時候，最差情況為0.813，最好情況為0.991；當BTB的表項為120的時候，最差情況為0.819，最好情況為0.992。并且，從圖6中可以發現對于一個特定的測試程序，當BTB表項增加的時候，其分支預測準確率相對有所提高。

在實驗過程中發現如果BTB表項數目是2的冪，那么分支預測準確率會急劇下降，如圖7所示，分別取BTB表項為32、64、128，與BTB表項為40時的分支預測效果對比。原因是由于BTB Module中如下一段代碼引起的。

val nextRepl =

if (!isPow2(entries)) {

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

} else {

val plru = new PseudoLRU(entries)

//BTB表項是2的冪時的替換算法

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

plru.replace

}

其中計算nextRepl的值，如果當前更新的分支指令在BTB中沒有查詢到，那么就從BTB中找出一個表項，用來存儲這個新的分支指令，nextRepl計算的就是這個新的表項的序號。如果BTB的表項是2的冪，那么替換算法是偽最近最少使用算法(PseudoLRU)；反之，替換算法就是簡單地累加。算法的不同，導致最終效果的差異，建議使用的時候可以避免設置BTB表項的值為2的冪。

圖6 當BTB表項是40、60、120的時候的分支預測效果

圖7 當BTB表項是40、32、64、128的時候的分支預測效果

結 語

[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)