３２位ＲＩＳＣ微處理器中分支預(yù)測(cè)器的硬件實(shí)現(xiàn)
2009-01-01 00:00:00汪永威樊曉椏黃小平
計(jì)算機(jī)應(yīng)用研究 2009年2期
(西北工業(yè)大學(xué) 航空微電子中心， 西安 710072)
摘 要：提出了一種基于Bimode和分支路徑歷史的動(dòng)態(tài)分支預(yù)測(cè)器，并在西北工業(yè)大學(xué)自主設(shè)計(jì)的“龍騰R2”微處理器中得以FPGA硬件實(shí)現(xiàn)，提出的分支預(yù)測(cè)器對(duì)條件分支可以進(jìn)行準(zhǔn)確地預(yù)測(cè)，具有延遲小、功耗低的特點(diǎn)。
關(guān)鍵詞：分支預(yù)測(cè)；超標(biāo)量；分支歷史
中圖分類號(hào)：TP303 文獻(xiàn)標(biāo)志碼：A
文章編號(hào)：10013695(2009)02041903
Hardware implementation of branch predictor in 32 bit RISC microprocessor
WANG Yongwei，F(xiàn)AN Xiaoya，HUANG Xiaoping
(Aviation Microelectronics Center， Northwestern Polytechnical University， Xi’an 710072， China)
Abstract:This paper proposed a new dynamic branch predictor based on BiMode predictor and branch path history， and then implemented it by FPGA based on Longtium R2，a RISC microprocessor designed by NWPU AMEC. The proposed predictorgives good prediction accuracy for conditional branches， with small latency and low power consumption.
Key words:branch prediction; superscalar; branch history
在條件分支執(zhí)行前，處理器對(duì)分支方向進(jìn)行預(yù)測(cè)，并按照預(yù)測(cè)方向進(jìn)行取指執(zhí)行。當(dāng)預(yù)測(cè)錯(cuò)誤時(shí)必須將流水線沖刷，然后從正確的地址取指，誤預(yù)測(cè)會(huì)產(chǎn)生很大的代價(jià)，并且這種代價(jià)隨著指令發(fā)射寬度和流水線深度的增加而快速增長(zhǎng)。因此，分支預(yù)測(cè)的準(zhǔn)確性成為微處理器設(shè)計(jì)的關(guān)鍵問(wèn)題。
為了提高分支預(yù)測(cè)的準(zhǔn)確率，已經(jīng)提出許多分支預(yù)測(cè)器結(jié)構(gòu)，從利用分支信息的狀態(tài)將這些分支預(yù)測(cè)器分為靜態(tài)和動(dòng)態(tài)的。靜態(tài)分支預(yù)測(cè)器利用靜態(tài)分支的信息或編譯器提供的信息對(duì)分支方向進(jìn)行預(yù)測(cè)；動(dòng)態(tài)分支預(yù)測(cè)器在不改變指令集的前提下，在程序執(zhí)行中動(dòng)態(tài)地收集分支相關(guān)信息并利用這些歷史信息對(duì)分支方向進(jìn)行預(yù)測(cè)。文獻(xiàn)[1]已經(jīng)表明動(dòng)態(tài)分支預(yù)測(cè)器在預(yù)測(cè)準(zhǔn)確率和實(shí)用性等方面勝過(guò)靜態(tài)分支預(yù)測(cè)器，因此過(guò)去的研究主要集中在對(duì)動(dòng)態(tài)分支預(yù)測(cè)策略的研究上。
本文引入了一種分支預(yù)測(cè)器并在32位RISC微處理器上得以硬件實(shí)現(xiàn)，這種預(yù)測(cè)器將路徑歷史信息組合進(jìn)Bimode預(yù)測(cè)器并將方向PHT進(jìn)行分頁(yè)處理，這種預(yù)測(cè)器結(jié)構(gòu)具有許多優(yōu)越的性質(zhì)。
1 相關(guān)研究
2 bit飽和計(jì)數(shù)器預(yù)測(cè)器在1981年由J. E. Smith引入[1]，其預(yù)測(cè)器是一個(gè)簡(jiǎn)單的2 bit飽和計(jì)數(shù)器的狀態(tài)機(jī)，預(yù)測(cè)器維持一些計(jì)數(shù)器項(xiàng)，當(dāng)有分支需要預(yù)測(cè)時(shí)，由一個(gè)哈希函數(shù)來(lái)選擇其中一個(gè)計(jì)數(shù)器來(lái)預(yù)測(cè)當(dāng)前分支“taken”或“nottaken”。當(dāng)執(zhí)行結(jié)果出來(lái)后，被選擇的計(jì)數(shù)器按照簡(jiǎn)單的狀態(tài)機(jī)進(jìn)行變化。這些計(jì)數(shù)器的狀態(tài)機(jī)有許多形式，但最有效的形式如圖1所示[2]。
兩級(jí)預(yù)測(cè)器是早期非常有效的預(yù)測(cè)器，由T.Yeh等人[3]于1992年提出。如圖2所示，它有兩級(jí)預(yù)測(cè)表，第一級(jí)是分支歷史寄存器表（BHRT），其中包含多個(gè)分支歷史移位寄存器（BHSR）；第二級(jí)是模式歷史表（PHT）。當(dāng)有分支需要預(yù)測(cè)時(shí)，由分支地址（branch address）選擇一個(gè)分支歷史寄存器(BHR)，然后由這個(gè)BHR索引PHT選擇一個(gè)2 bit 的預(yù)測(cè)器對(duì)分支方向進(jìn)行預(yù)測(cè)，如果被選擇的計(jì)數(shù)器的值為2′b11或2′b10，則預(yù)測(cè)taken；如果為2′b10或2′b00，則預(yù)測(cè)nottaken。
為了減小不同分支在PHT中的沖突，提高預(yù)測(cè)準(zhǔn)確率，基于兩級(jí)預(yù)測(cè)器提出了許多改進(jìn)的方案。Gshare預(yù)測(cè)器用分支地址（branch address）和全局分支歷史寄存器的異或（XOR）來(lái)索引分支模式表（PHT），充分利用分支執(zhí)行的歷史信息對(duì)當(dāng)前分支進(jìn)行預(yù)測(cè)[4]。這種Gshare預(yù)測(cè)器因其準(zhǔn)確率高和硬件開(kāi)銷小而廣泛應(yīng)用。
1.1 Bimode 預(yù)測(cè)器
為了消除不同分支在PHT的沖突現(xiàn)象而帶來(lái)的誤預(yù)測(cè)，Bimode預(yù)測(cè)器被提出[5]，它將分支模式表分為兩部分，然后由另外一個(gè)選擇預(yù)測(cè)器表來(lái)動(dòng)態(tài)選擇應(yīng)用哪個(gè)表來(lái)對(duì)當(dāng)前分支進(jìn)行預(yù)測(cè)。這種方法被證明能夠很好地消除沖突，具有較高的準(zhǔn)確性，并在上下文轉(zhuǎn)換環(huán)境下表現(xiàn)良好。其索引方法如圖3 所示。
1.2 路徑歷史信息
為了充分利用分支歷史信息對(duì)分支方向進(jìn)行預(yù)測(cè)，S.Reches 等人[6]提出基于分支路徑的歷史信息。圖4所示是利用路徑歷史信息的Gshare預(yù)測(cè)器。仿真結(jié)果顯示分支路徑歷史是可以用來(lái)提高預(yù)測(cè)器準(zhǔn)確性能的又一重要信息。
1.3 基于感知機(jī)的分支預(yù)測(cè)器
前面的分支預(yù)測(cè)機(jī)制都建立在2 bit飽和計(jì)數(shù)器的基礎(chǔ)上，為了進(jìn)一步提高預(yù)測(cè)器的準(zhǔn)確率，D.A.Jiménez 等人[7]提出了基于感知機(jī)的動(dòng)態(tài)分支預(yù)測(cè)器，這種預(yù)測(cè)器采用一種完全不同的機(jī)制，將2 bit飽和計(jì)數(shù)器換成一種簡(jiǎn)單的神經(jīng)網(wǎng)絡(luò)——感知機(jī)（perceptron）。如圖5所示，一個(gè)感知機(jī)為每一位分支歷史賦予一個(gè)權(quán)值，通過(guò)計(jì)算權(quán)值總和預(yù)測(cè)分支方向，如果權(quán)值總和符號(hào)為正，則預(yù)測(cè)taken；如果為負(fù)，則預(yù)測(cè)nottaken。而分支歷史信息的更新通過(guò)更新感知機(jī)的各個(gè)權(quán)值來(lái)實(shí)現(xiàn)。基于感知機(jī)的全局分支歷史方案如圖6所示。
基于感知機(jī)的預(yù)測(cè)器在某些情況下確實(shí)能提高預(yù)測(cè)準(zhǔn)確率，但是在預(yù)測(cè)時(shí)，感知機(jī)需要作一個(gè)乘加運(yùn)算，更新時(shí)也需要對(duì)感知機(jī)的各個(gè)權(quán)值作運(yùn)算，因此預(yù)測(cè)延遲比較大。雖然后來(lái)的研究提出了減小延遲的方法，但仍然未達(dá)到實(shí)際應(yīng)用的要求。
2 基于Bimode和路徑歷史信息的預(yù)測(cè)器方案的提出和實(shí)現(xiàn)
2.1 適用于超標(biāo)量微處理器的預(yù)測(cè)器
分支預(yù)測(cè)基于這樣的假設(shè)，即分支行為是重復(fù)的，由一種模式指定的分支再次發(fā)生時(shí)會(huì)產(chǎn)生上次這種模式發(fā)生時(shí)同樣的動(dòng)作，而這種分支執(zhí)行模式是由各種分支相關(guān)信息組成。在執(zhí)行中，預(yù)測(cè)器動(dòng)態(tài)收集分支指令執(zhí)行的歷史信息，利用這些歷史信息對(duì)分支方向進(jìn)行預(yù)測(cè)。對(duì)超標(biāo)量指令流及相關(guān)研究可以得出一些啟示：
a)分支預(yù)測(cè)可以利用的相關(guān)信息包括分支地址、全局分支執(zhí)行歷史、局部分支執(zhí)行歷史、分支路徑歷史，而局部分支執(zhí)行歷史與各個(gè)分支相關(guān)，要實(shí)現(xiàn)需要大量的分支歷史寄存器表。
b)基于感知機(jī)的預(yù)測(cè)器預(yù)測(cè)準(zhǔn)確率較高，但是預(yù)測(cè)延遲大，并不適用于超標(biāo)量RISC微處理器。
c)從Bimode分支預(yù)測(cè)器的高性能來(lái)看，將PHT分成兩個(gè)部分，然后動(dòng)態(tài)地選擇其中一個(gè)用來(lái)預(yù)測(cè)。這種方法是有效的，不但提高了預(yù)測(cè)器的性能，并且在上下文轉(zhuǎn)換環(huán)境中表現(xiàn)良好。
d)傳統(tǒng)的基于計(jì)數(shù)器的分支預(yù)測(cè)器研究主要集中在提高預(yù)測(cè)準(zhǔn)確率上，對(duì)預(yù)測(cè)延遲和功耗關(guān)注不夠。
基于以上研究，本文提出一種基于Bimode和路徑歷史信息的預(yù)測(cè)器，其方案如圖7所示。它在Bimode預(yù)測(cè)器的基礎(chǔ)上增加了last branch，由此利用全局分支歷史、路徑歷史、分支地址三種相關(guān)信息；預(yù)測(cè)器仍然采用2 bit 飽和計(jì)數(shù)器機(jī)制，對(duì)Bimode預(yù)測(cè)器的兩個(gè)方向預(yù)測(cè)器表進(jìn)行了改造，并將每個(gè)方向預(yù)測(cè)器表分為兩頁(yè)。
在遇到條件分支指令需要預(yù)測(cè)時(shí)，首先分支指令的分支地址（branch address）、分支全局歷史移位寄存器（BHSR）和分支路徑上最后一條分支指令地址（last branch）三部分進(jìn)行異或運(yùn)算得到一個(gè)索引（index），用這個(gè)索引去選擇一個(gè)2 bit的選擇預(yù)測(cè)器（choice predictor）；同時(shí)，用分支地址索引兩個(gè)方向預(yù)測(cè)器表以選擇兩個(gè)方向預(yù)測(cè)器（direction predictor），而每個(gè)方向預(yù)測(cè)器表分為兩頁(yè)，兩頁(yè)的索引結(jié)果用另外1 bit分支地址去選擇。
在choice predictor 和兩個(gè)direction predictor都選出來(lái)后，再用choice predictor選擇用哪一個(gè)direction predictor作為當(dāng)前分支的預(yù)測(cè)輸出。在預(yù)測(cè)分支的分支結(jié)果出來(lái)后，分支預(yù)測(cè)器要根據(jù)結(jié)果對(duì)計(jì)數(shù)器狀態(tài)進(jìn)行更新。更新?tīng)顟B(tài)機(jī)如圖1所示。被索引到的choice predictor總是要根據(jù)分支結(jié)果進(jìn)行更新，而只有被選中的direction predictor才會(huì)更新，未被選中的direction predictor狀態(tài)不改變。
2.2 “龍騰R2”微處理器中預(yù)測(cè)器的實(shí)現(xiàn)
“龍騰R2”微處理器中選擇全局歷史移位寄存器的長(zhǎng)度為9 bit，選擇分支路徑上最近一條分支的低9 bit作為路徑歷史last branch，在索引choice predictor時(shí)，選擇分支指令地址的低9 bit作為branch address進(jìn)行異或操作。而在對(duì)每一個(gè)direction predictor表的兩頁(yè)進(jìn)行選擇時(shí)采用的是分支指令地址的第9bit。
Choice predictor表和兩個(gè)兩頁(yè)的direction predictor表共五個(gè)表，硬件實(shí)現(xiàn)中，對(duì)這五個(gè)512×2 bit的表均使用RAM塊實(shí)現(xiàn)。預(yù)測(cè)器電路結(jié)構(gòu)如圖8所示。
24譯碼器用于選擇更新哪個(gè)計(jì)數(shù)器，譯碼器的輸入是選擇計(jì)數(shù)器的輸出和分支指令地址的第9 bit的連接，這剛好實(shí)現(xiàn)只有被選擇的預(yù)測(cè)器計(jì)數(shù)器才會(huì)更新的原則。對(duì)四個(gè)方向預(yù)測(cè)器的選擇也可以直接用一個(gè)41多選器，但是這樣預(yù)測(cè)器的關(guān)鍵路徑就是一個(gè)異或門的延遲加上訪RAM的延遲再加上一個(gè)41多選器的延遲。如果采用圖8的結(jié)構(gòu)關(guān)鍵路徑就大致為一個(gè)異或門的延遲加上訪RAM的延遲再加上一個(gè)21多選器的延遲，很明顯延遲減小，可以實(shí)現(xiàn)更高的時(shí)鐘頻率。
因?yàn)榇鎯?chǔ)規(guī)模越小，功耗越低[10]，為了減小整個(gè)預(yù)測(cè)結(jié)構(gòu)的功耗，將Bimode預(yù)測(cè)器的方向PHT分為兩頁(yè)，這樣未被選定的預(yù)測(cè)器的功耗就很小，整體預(yù)測(cè)功耗就可以有效降低。另外，為了減小取指延遲，在“龍騰R2”微處理器分支處理單元（BPU）的實(shí)現(xiàn)中，還使用了一個(gè)64端口、4組相連的分支目標(biāo)指令cache（BTIC），用于存儲(chǔ)新近執(zhí)行的分支目標(biāo)指令?！褒堯vR2”微處理器分支預(yù)測(cè)單元的實(shí)現(xiàn)結(jié)構(gòu)如圖9所示。
3 仿真結(jié)果和性能分析
基于Bimode和路徑歷史信息的預(yù)測(cè)器同時(shí)使用了分支地址、全局分支執(zhí)行歷史、分支路徑歷史三種分支相關(guān)信息，并采用了Bimode預(yù)測(cè)器的思想，將模式歷史表PHT分為兩部分以減小不同分支的沖突。由于對(duì)每個(gè)PHT采用了分頁(yè)技術(shù)，在同樣的歷史長(zhǎng)度和硬件開(kāi)銷下利用1 bit分支地址對(duì)分頁(yè)進(jìn)行選擇，增加了1 bit分支地址的相關(guān)信息，對(duì)條件分支可以準(zhǔn)確地預(yù)測(cè)。
分別使用Bimode預(yù)測(cè)器和本文提出的預(yù)測(cè)器進(jìn)行仿真，使用的仿真程序是VxWorks操作系統(tǒng)的啟動(dòng)程序，相信這個(gè)程序可以對(duì)預(yù)測(cè)器的性能有代表性的反應(yīng)。在操作系統(tǒng)啟動(dòng)出現(xiàn)命令提示符 “>”時(shí)，對(duì)預(yù)測(cè)器的預(yù)測(cè)準(zhǔn)確率進(jìn)行統(tǒng)計(jì)，統(tǒng)計(jì)數(shù)據(jù)如表1所示（其中用bimodepath代表本文提出的預(yù)測(cè)器）。在同樣采用9 bit的歷史長(zhǎng)度下，純粹的Bimode預(yù)測(cè)器可以達(dá)到85.45%的預(yù)測(cè)準(zhǔn)確率，而本文提出的預(yù)測(cè)器可以到達(dá)87.18%的預(yù)測(cè)準(zhǔn)確率，可見(jiàn)本文提出的預(yù)測(cè)器可以對(duì)條件分支可以進(jìn)行更準(zhǔn)確的預(yù)測(cè)。
表1 兩種預(yù)測(cè)器預(yù)測(cè)啟動(dòng)VxWorks的預(yù)測(cè)準(zhǔn)確率
預(yù)測(cè)方法預(yù)測(cè)分支總次數(shù)預(yù)測(cè)成功數(shù)預(yù)測(cè)失敗數(shù)預(yù)測(cè)成功率執(zhí)行周期
Bimode621 434529 33792 09785.18%5 128萬(wàn)
Bimodepath621 021543 08377 93887.45%5 125萬(wàn)
本文提出的預(yù)測(cè)器在實(shí)現(xiàn)中將兩個(gè)方向預(yù)測(cè)器分別分為兩頁(yè)，在同樣歷史長(zhǎng)度下，每個(gè)RAM塊減小一半，減小了訪問(wèn)RAM的延遲。雖然多出一個(gè)21多選器的延遲，但是這個(gè)延遲可以淹沒(méi)在XOR門的延遲中，因此并不會(huì)使延遲增加。同時(shí)，將兩個(gè)方向預(yù)測(cè)器分別分為兩頁(yè)，在更新預(yù)測(cè)器對(duì)PHT表寫的時(shí)候，采用一個(gè)24譯碼器決定對(duì)哪一塊RAM操作，未選中的頁(yè)的功耗就會(huì)很小。這種分頁(yè)技術(shù)用訪問(wèn)小規(guī)模的頁(yè)代替訪問(wèn)大規(guī)模的頁(yè)減小了預(yù)測(cè)器的功耗。
4 結(jié)束語(yǔ)
筆者設(shè)計(jì)的基于Bimode和路徑歷史信息的預(yù)測(cè)器已基本完成，并在Vera驗(yàn)證語(yǔ)言搭建的VCS仿真平臺(tái)下通過(guò)了仿真驗(yàn)證。最后，筆者用Design Compiler對(duì)分支處理單元進(jìn)行了綜合，并用Primetime進(jìn)行了靜態(tài)時(shí)序分析。時(shí)序報(bào)告表明，該設(shè)計(jì)滿足PowerPC 750微處理器時(shí)鐘266 MHz的要求。目前，集成了分支處理單元的“龍騰R2”微處理器已在FPGA板上初步通過(guò)驗(yàn)證，更深層的系統(tǒng)級(jí)驗(yàn)證正在進(jìn)行。
實(shí)驗(yàn)證明這種基于Bimode和路徑歷史信息的預(yù)測(cè)器可以對(duì)條件分支進(jìn)行準(zhǔn)確的預(yù)測(cè)，并具有較小的延遲，能夠適應(yīng)于更高的主頻，并具有繼續(xù)減小功耗的空間，可以滿足32位RISC微處理的應(yīng)用。
參考文獻(xiàn)：
［1］
SMITH J E.A study of branch prediction strategies[C]//Proc of the 8th Annual International Symposium on Computer Architecture. Los Alamitos:IEEE Computer Society Press，1981:135148.
[2]PAN S T，SO K，RAHMEH J T.Correlationbased branch prediction[C]//Proc of the 26th Asilomar Conference on Signals，Systems and Computers.1992:5155.
[3]YEH T Y，PATT Y N.Twolevel adaptive training branch prediction[C]//Proc of the 24th Annual ACM/IEEE International Symposium on Microarchitecture.New York:ACM Press，1991:5161.
[4]McFARLING S.Combining branch predictors， TN36 [R]. Palo Alto:Digital Western Research Laboratory，1993.
[5]LEE C C，CHEN C K，MUDGE T N.The Bimode branch predictor[C]//Proc of the 30th AnnualIEEE/ACM International Symposium on Microarchitecture.Washington DC:IEEE Computer Society，1997:413.
[6]NAIR R.Dynamic pathbased branch correlation[C]//Proc of the 28th Annual IEEE/ACM International Symposium on Microarchitecture.Los Alamitos:IEEE Computer Society Press，1995:1523.
[7]JIMNEZ D A，LIN C.Dynamic branch prediction with perceptrons[C]//Proc of the 7th International Symposium on HighPerformance Computer Architecture.Washington DC:IEEE Computer Society，2001:197206.
[8]HO C Y，CHONG K F，YAU C H，et al.A study of dynamic branch predictors:counter versus perceptron[C]//Proc of International Conference on Information Technology.Washington DC:IEEE Computer Society ，2007:528536.
[9]AASARAAI K，BANIASADI A，ATOOFIAN E.Computational and storage power optimizations for the OGEHL branch predictor[C]//Proc of the 4th International Conference on Computing Frontiers.New York:ACM Press，2007:105112.
[10]武萌，沈海斌.一種Gshare分支預(yù)測(cè)器的低功耗設(shè)計(jì)方法[J].微電子學(xué)與計(jì)算機(jī)，2007，24(3):200202.
