付家為 王 旭 何 虎

(清華大學微電子學研究所 北京 100084)

一種支持Superscalar-VLIW混合架構處理器的混合分支預測設計

付家為 王 旭 何 虎

(清華大學微電子學研究所 北京 100084)

描述在一款支持超標量與超長指令字結構的混合架構數字信號處理器上設計的分支預測結構。為控制硬件復雜度并充分提高預測準確度，設計雙峰預測器與PAp預測器混合型預測結構，充分發(fā)揮兩種預測器的優(yōu)點。在設計完成的處理器上，運行標準DSPstone程序。實驗結果表明，添加分支預測結構使得處理器性能平均提升23%，并且混合型預測結構相比單一預測結構在準確度方面優(yōu)勢明顯。

數字信號處理器 超標量 超長指令字 分支預測 雙峰預測 PAp

0 引 言

數字信號處理器(DSP)已經越來越多地應用于通信及多媒體信號處理領域，隨著如視頻、音頻、圖像等多媒體應用越來越復雜多樣，對處理器性能的要求也越來越高[1]。提高指令并行度(ILP)是提高處理器性能的重要手段。超標量(Superscalar)與超長指令字(VLIW)技術作為挖掘指令并行度的重要手段，分別在硬件層面與軟件層面對指令并行進行調度。Superscalar技術由硬件決定指令并行性[2]，硬件復雜度較高，對于編譯器要求較低，軟件可移植性較強[3]；VLIW技術由軟件調度指令并行性，大大降低了硬件復雜度，但隨之而來的代價是軟件復雜度的增大以及寄存器和功能單元數目的增加[4]，而且VLIW處理器程序兼容性也較低。為充分利用兩種技術的優(yōu)勢，本設計處理器采用Superscalar與VLIW混合架構，對于運算密集重復性較高的程序，采用VLIW模式執(zhí)行，提高指令并行度以提高執(zhí)行效率，其他部分程序采用Superscalar模式執(zhí)行，確保程序可移植性。

現代高性能處理器中多數采用流水線技術，采用流水線技術隨之而來的問題就是跳轉指令所帶來的周期損失，尤其對于深度流水線結構處理器更是明顯。所以成熟精準的分支預測設計對于處理器性能的提升不言而喻?，F階段常用的分支預測技術主要分為靜態(tài)分支預測與動態(tài)分支預測。對于靜態(tài)分支預測，程序中每次遇到跳轉指令，都對其進行固定的預測，靜態(tài)分支預測準確率較低。動態(tài)分支預測在每次遇到跳轉指令時，通過關聯之前的跳轉信息，對不同的跳轉指令進行不同的預測，并實時更新跳轉信息[5]。

動態(tài)分支預測中，廣泛使用的方法主要有雙峰預測與兩級自適應預測，近年來各種改進型預測器如神經網絡型預測器也是相繼被提出。較成熟的雙峰預測與兩級自適應預測各有利弊[6]，其中兩級自適應預測中常被使用到的方法包括PAp、GAg、GAs、Gshare等。雙峰預測器的優(yōu)勢在于硬件結構簡單，預測穩(wěn)定性高，訓練時間短，但準確率較低；兩級自適應預測器的準確率較高，但是硬件邏輯較為復雜，增加了面積功耗的額外開銷。

現有技術中，動態(tài)分支預測已在Superscalar結構上充分利用，而VLIW結構的分支預測功能多采用靜態(tài)預測，由軟件調度。事實上，大多數VLIW結構使用延遲跳轉技術[7]，這大大增加了編譯器的負擔，尤其對于VLIW結構單周期多發(fā)射指令編譯，編譯器為填滿延遲槽大大增加了軟件負擔[8]。所以，為VLIW結構設計動態(tài)分支預測方法具有重要的意義。

本文提出支持Superscalar與VLIW雙模式架構處理器的動態(tài)分支預測方法，預測設計采用雙峰預測與PAp預測混合結構，對于不同跳轉指令使用不同的預測方法，充分發(fā)揮兩種預測器的優(yōu)勢。實驗結果表明，使用混合結構預測器比單獨結構預測器性能優(yōu)勢明顯，并使處理器整體性能得到很大提升。

1 Orchid結構

1.1 Orchid硬件結構

本設計在清華大學DSP實驗室自主開發(fā)的Orchid處理器上完成，Orchid是一款兼容ARM指令集的通用處理器，采用Superscalar-VLIW混合結構，整體分為程序存儲器、數據存儲器、指令獲取模塊、指令分發(fā)模塊、執(zhí)行模塊以及寄存器堆模塊，如圖1所示，是Orchid處理器的整體硬件結構。

圖1 Orchid整體結構圖

指令獲取模塊每次從程序存儲器中獲取256位的指令包，包含16位與32位混編指令。分發(fā)單元可以工作在兩種分發(fā)模式下，Superscalar模式和VLIW模式，由軟件實現模式切換，Superscalar模式支持最多2發(fā)射，VLIW模式支持最多6發(fā)射。經過將指令包中的指令擴展、分發(fā)后，分配到相應的執(zhí)行單元進行指令執(zhí)行。為更好地兼容ARM指令集，Orchid的寄存器堆采用與ARM架構相應的15個通用寄存器。

Orchid功能單元分為兩個A單元，兩個M單元，兩個D單元，最多支持六條指令并行執(zhí)行。其中A單元用于算術邏輯運算以及移位運算，M單元用于乘法運算，D單元用于存儲器的存取以及實現程序的跳轉。

1.2 Orchid流水線結構

Orchid流水線設計為十級流水線結構，主要分為Fetch_PG、Fetch_PS、Fetch_WT、Fetch_IR、Fetch_EXP、Dispatch、Decode、Exe1、Exe2、Exe3，如圖2所示。流水線各級功能如下：

Fetch_PG：分支預測以及產生PC地址。

Fetch_PS：將產生的PC地址傳遞給指令cache控制單元。

Fetch_WT：等待指令cache控制單元讀取指令。

Fetch_IR：從指令cache控制單元讀取指令。

Fetch_EXP：將16位于32位指令統一擴展成32位指令，每6條指令形成一個擴展包。

Dispatch：執(zhí)行指令并行分發(fā)策略，將具有并行性的指令同時分發(fā)到各個功能單元。對于Superscalar模式，最多并行發(fā)射2條指令，并行分發(fā)原則是判斷兩條指令是否有依賴關系以及執(zhí)行單元是否沖突；對于VLIW模式，最多并行發(fā)射6條執(zhí)行，并行分發(fā)原則是按照指令執(zhí)行單元順序。

Decode：指令解碼。

Exe1～Exe3：執(zhí)行級，完成指令執(zhí)行其中Exe1完成單周期執(zhí)行指令，Exe2與Exe3完成多周期執(zhí)行指令。

圖2 Orchid流水線結構圖

2 Orchid雙模式分支預測設計

2.1 Orchid 雙峰-PAp混合預測器結構

本設計采用了雙峰預測器與PAp預測器結合的混合預測結構，對于不同的跳轉指令采用不同的預測機制，充分發(fā)揮兩種預測器的優(yōu)勢。

分支預測的原理是在Fetch_PG級，通過PC地址索引BTB表查找跳轉信息，如果查到了跳轉指令的信息，則按照跳轉信息進行跳轉操作。在執(zhí)行級判斷預測是否正確，如果預測正確，則按照預測結果繼續(xù)執(zhí)行，如果預測錯誤，則清空流水線，從正確位置重新執(zhí)行并對BTB表中存儲的跳轉信息進行修改。分支預測原理如圖3所示。

圖3 分支預測原理圖

雙峰預測器的核心技術是分支目標緩存表(BTB)，BTB表是一塊SRAM，里面存儲著各條跳轉指令的跳轉信息，由PC進行索引。雙峰預測BTB表的每個表項存儲四部分信息：跳轉指令地址BIA(Branch Instruction Address)、跳轉目標地址BTA(Branch Target Address)、跳轉指令下一個執(zhí)行包地址NDA(Next Dispatch_packet Addrees)以及分支歷史信息BHI(Branch History Information)，如圖4所示。其中BIA用于索引BTB表項，BTA是跳轉目標地址，BHI存儲是否跳轉，NDA是預測錯誤后重新執(zhí)行的地址。跳轉指令第一次執(zhí)行時，將其相應信息存入BTB表中，當此跳轉指令再次執(zhí)行時，通過PC索引BTB表讀取跳轉信息進行預測，按照預測信息執(zhí)行，在執(zhí)行級判斷預測是否準確，如果預測錯誤，則用正確的跳轉信息改寫B(tài)TB表。

圖4 雙峰預測器BTB表示意圖

PAp預測器的BTB表在雙峰預測器的基礎上增加了跳轉歷史寄存器BHR(Branch History Register)，通過PC索引BTB表項，由BHR索引模式表(Pattern Table)，對應模式表中設計一個計數器，每個計數值記錄一次跳轉指令的跳轉方向。這樣對于條件執(zhí)行的跳轉指令，可以準確預測出每次的跳轉方向，即準確預測出哪一次跳轉，哪一次不跳轉。PAp預測器BTB表如圖5所示。

圖5 PAp預測器BTB表示意圖

雙峰預測器的優(yōu)勢在于邏輯結構簡單，面積、功耗較小，并且正確預測之前所需的訓練次數少，訓練完成后預測穩(wěn)定性高，但是對于條件執(zhí)行的跳轉指令，只能預測出一種跳轉方向，預測命中率較低；PAp預測器的優(yōu)勢在于可以準確預測出跳轉指令的不同跳轉方向，預測命中率較高，但是邏輯結構較復雜，隨之帶來了面積、功耗的增加，同時，需要為每次不同跳轉方向建立對應的模式表表項，即建立完整跳轉指令信息的BTB表項時間較長，且BTB表較大增加額外存儲資源負擔。將建立完整跳轉指令信息BTB表項的時間稱為預測訓練時間，PAp預測器的訓練時間是雙峰預測器的數倍甚至數十倍，后文將介紹縮短訓練時間的方法。為更好地利用兩種預測器的優(yōu)勢，本設計采用一種混合的分支預測機制：對于非條件執(zhí)行的跳轉指令，其只有一種跳轉方向，所以采用雙峰預測器，降低面積、功耗與訓練時間，減少存儲資源負擔；對于條件執(zhí)行的跳轉指令，其存在兩種跳轉方向，采用PAp預測器進行預測，提高預測命中率。

2.2 Superscalar-VLIW雙模式下分支預測技術

本設計中，包的概念十分重要，在整個流水線設計過程中，指令是以包的形式存在的，即取指包、擴展包、分發(fā)包。取指包是指令獲取單元從程序存儲器中讀取的256位數據包，包含16位與32位指令；擴展包在Fetch_EXP級生成，將16位指令與32位指令統一擴展成32位，每6條指令形成一個擴展包，即192位；分發(fā)包在Dispatch級生成，根據分發(fā)策略，將并行執(zhí)行的指令裝載在一個分發(fā)包中。

分支預測是在Fetch_PG級進行的，從BTB表中讀出BIA、BTA、NDA、BHI、PT等預測信息，在Exe1級要對預測信息進行判斷是否正確，所以預測信息需要隨著跳轉指令一起沿流水線逐級傳遞下去，因為跳轉指令是以包的形式逐級傳遞的，所以預測信息也要與相應的包一起逐級傳遞。確定預測信息與某個包中的跳轉指令對應的原則是判斷預測信息中的BIA是否與包中的跳轉指令PC對應。對于Superscalar模式，最多2發(fā)射，即BIA與2條指令作比較；但對于VLIW模式，最多6發(fā)射，BIA需要與6條指令分別對照，所需邏輯復雜，所以存入VLIW模式存入BTB表項中的BIA并不是跳轉指令的PC，而是跳轉指令所在分發(fā)包的首地址，這樣只需要將BIA與分發(fā)包首地址做比較即可，邏輯較為簡單。

Superscalar與VLIW模式下分支預測另一個不同點是，Superscalar模式下，跳轉指令后面一條指令不能與跳轉指令并行發(fā)射，而VLIW模式下，跳轉指令后面指令如果沒有執(zhí)行單元沖突，則可與跳轉指令并行發(fā)射。NDA表示預測錯誤后正確的執(zhí)行地址，對于Superscalar模式，NDA為跳轉指令后面一條指令的地址，而對于VLIW模式，NDA為跳轉指令所在分發(fā)包的下一個分發(fā)包的首地址。如圖6所示，是取指包中Superscalar與VLIW模式下BIA與NDA位置示意圖，其中Dp_package1與Dp_package2是兩個分發(fā)包，即Dp_package1中指令并行發(fā)射，Dp_package2中指令并行發(fā)射。

圖6 取指包中Superscalar與VLIW模式下BIA與NDA位置示意圖

2.3 分支預測的技術改進

對于PAp預測器，雖然其預測命中率較高，但是存在訓練時間較長的缺點，所以降低訓練時間對于提高分支預測器性能至關重要。動態(tài)的基于歷史信息的跳轉方向預測方法可使用有限狀態(tài)機來描述，圖7(a)表示預測方向狀態(tài)機示意圖。狀態(tài)機由四個狀態(tài)組成，每個狀態(tài)有2 bit信息組成，代表最近兩次跳轉方向。狀態(tài)機中狀態(tài)存在BTB表的BHI中，代表跳轉方向，00、01表示不跳，10、11表示跳。BHI的初始狀態(tài)為00。對于訓練一條方向為跳轉的跳轉指令，需要兩次訓練，第三次才能正確預測，對于PAp預測器，每個PT模式狀態(tài)都需要兩次訓練，如果循環(huán)為for(i=0,i<10,i++)這種10次的循環(huán)，訓練次數至少為20次，這將付出相當大的代價。本設計對有限狀態(tài)機做改進，改進的狀態(tài)機如圖7(b)所示，00表示不跳，10、11表示跳，從不跳到跳只需1次訓練，將原有訓練時間減半。

圖7 有限狀態(tài)機

改進后的PAp訓練時間減半，但是對于循環(huán)次數較多的跳轉指令，需要對每個PT模式狀態(tài)都進行訓練，如果循環(huán)為for(i=0,i<10,i++)這種10次的循環(huán)，訓練次數至少為10次，訓練代價依然很大，所以對PT模式表中對應的BHI值訓練方法進行改進。第一次訓練時，不僅僅對PT模式計數器中計數為000項的BHI值進行更改，對所有計數項的BHI都做000項的更改，也就是將所有項都置成跳轉方向，這樣只需要對不跳轉的一項即最后一項進行訓練即可，通過此改進方法，訓練項僅為第一項與最后一項，大大縮短了訓練次數。

Fetch_PG級還未對指令進行解碼，通過PC索引BTB表的方法是對取指包中的每條指令進行遍歷，看BTB表中是否有與之對應的表項，如果查到對應的表項，說明該指令是跳轉指令，并取出跳轉信息進行預測，每個包遍歷一次得到一組跳轉信息。存在一種情況是一個取指包中包含兩條跳轉指令，第一條跳轉指令方向為不跳，第二條跳轉指令要執(zhí)行。 但是這個取指包中只能取出第一條跳轉指令的跳轉信息，而得不到第二條跳轉指令的跳轉信息，因此需要多加入一套跳轉信息。即在遍歷到一條方向為不跳的跳轉指令后在取值包中繼續(xù)遍歷，如果又遍歷到跳轉指令則取出第二套跳轉信息，與第一套跳轉信息共同完成預測并一起沿流水線逐級傳遞并在Exe1級進行分支預測正確性的判斷。

PT模式表計數器的計數規(guī)則為每次遇到跳轉指令，對BTB表中對應表項的PT模式表計數器加1，遇到跳轉指令方向為不跳或預測錯誤需要清空流水線時，BTB表對應項PT模式表計數器歸零。由于預測是在Fetch_PG級進行的，PT模式表計數也要發(fā)生在Fetch_PG級，計數原則是在取指包中遍歷指令，如果發(fā)現跳轉指令，則對其相應的PT模式表計數器加1。在預測錯誤需要清空流水線的情況下，對預測錯誤的跳轉指令PT表計數器歸零，但是存在一種情況，即在Fetch_PG級，按照預測信息執(zhí)行的指令中有其他跳轉指令，它們的PT表計數器也發(fā)生了改變，而預測錯誤的跳轉指令后面執(zhí)行的跳轉指令本不該執(zhí)行，它們的PT表計數器也不應該發(fā)生變化。如圖8所示的一段程序，指令B1預測方向為不跳轉，但實際方向為跳轉，固B2、B3兩條跳轉指令本不該執(zhí)行，但根據預測信息，這兩條指令在B1到達Exe1級之前執(zhí)行，B2、B3的PT表計數器發(fā)生了不該有的變化。本設計考慮到了預測錯誤的跳轉指令，讓它們的PT表計數器恢復到正確的計數值，即對于圖8所示的程序，當B1后流水線清空后，B2與B3的PT表計數器恢復到了正確的計數值。

圖8 跳轉示例程序

PT模式表的計數器位數同樣決定了PAp預測器預測的準確率。當計數器為3位時，計數范圍是0～7，對于循環(huán)次數大于8的跳轉指令，則無法記錄每次跳轉方向，所以增加計數器位數可有效提高預測的命中率。但是增加計數器位數又會增大面積與功耗，所以計數器位數的選擇應為命中率與面積功耗折中的結果。

3 性能評測

3.1 對2.3節(jié)分支預測技術改進性能指標評測

本實驗采用DSPstone基準程序對處理器及分支預測部分性能進行評估。表1對2.3節(jié)分支預測技術改進前后預測準確率進行對比，由表中可以看出，改進后分支預測命中率較改進前均有明顯提升，即對于混合預測器，預測訓練時間較改進前大大減少，命中率最高可以提升32%，命中率平均提升23%。

表1 改進分支預測器預測命中率比較

3.2 混合預測器與單一預測器以及不采用分支預測器性能比較

表2是在Superscalar模式與Superscalar-VLIW混合模式下混合預測器與單一預測器及無分支預測器性能預測命中率的比較。由表中可以看出，對于單獨Superscalar模式與Superscalar-VLIW混合模式，分支預測均適用，并且兩種模式下分支預測準確率相近。混合模式分支預測器命中率相比無分支預測器和單一雙峰預測器都有非常明顯提升，命中率最高可達到近99%，并且對于類似fir2dim、matrix2、matrix1這樣較大的程序，混合預測器命中率提升更為明顯并且準確率更高，原因在于，對于小程序，跳轉指令數目較少并且訓練時間所占比例較大，所以準確率和優(yōu)化空間有限。

表2 混合預測器與單一預測器及 無分支預測器性能預測命中率比較 %

表3是混合預測器與雙峰預測器相比無分支預測器運行時間提升的比較，可以看出，混合預測器與雙峰預測器對于程序運行時間提升明顯，并且混合預測器相比單一雙峰預測器運行時間也都有明顯提升，最高提升達38%。

表3 混合預測器與雙峰預測器相比 無分支預測器運行時間提升比較 %

3.3 綜合報告

表4是使用xilinx vivado綜合工具，選擇XC7K-325T FPGA綜合得到的結果，處理器內核的存儲資源沒有進行綜合，目的在于更直觀地對比分支預測部分的存儲資源占用量。由表中可以看出，雙峰與PAp混合預測器邏輯資源與寄存器數量占整個處理器的比例較小?；旌项A測器比單一的雙峰預測器邏輯資源增加了48%左右，寄存器數量增加近40%，存儲資源幾乎沒有增加；相比選用單一的PAp預測器，邏輯資源減小了一半，寄存器數目大大減少。由此可以看出，相比單一雙峰預測器，混合預測器只增加了少量硬件開銷，但占處理器內核比例依舊很??；相比單一的PAp預測器，混合預測器大大降低了硬件復雜度。由此可見，混合預測器以較小的硬件代價換取了處理器性能的很大提升，混合型預測器是處理器性能和硬件開銷折中考慮的最優(yōu)選擇。

表4 綜合報告

4 結 語

本文提出一種支持Superscalar-VLIW混合架構處理器的分支預測方法，在兩種模式下均可以進行分支預測，預測機制采用雙峰預測與PAp預測相結合，充分利用二者在預測穩(wěn)定性、硬件結構以及預測準確率方面的優(yōu)勢。實驗結果表明，該分支預測方法在Superscalar與VLIW兩種模式下進行分支預測的效果相同，并且得到了較高的預測準確率，占用硬件資源較少，處理器性能得到了較大的提升。

[1] Lee J,Youn J M,Cho D,et al.Reducing instruction bit-width for low-power VLIW architectures[J].Acm Transactions on Design Automation of Electronic Systems,2013,18(2):99-109.

[2] Moon S M,Ebcioglu K.An Efficient Resource-constrained Global Scheduling Technique For Superscalar And Vliw Processors[J].Acm Sigmicro Newsletter,1993,23(23):55-71.

[3] Steven G,Christianson B,Collins R,et al.A superscalar architecture to exploit instruction level parallelism[J].Microprocessors & Microsystems,1997,20(96):391-400.

[4] 沈鉦,何虎,楊旭,等.Architecture Design of a Variable Length Instruction Set VLIW DSP[J].Tsinghua Science & Technology,2009,14(5):561-569.

[5] Palermo G,Sam M,Silvan C,et al.Branch prediction techniques for low-power VLIW processors[C]//Proceedings of the 13th ACM Great Lakes symposium on VLSI.ACM,2003:225-228.

[6] Yeh T Y,Patt Y N.Two-Level Adaptive Training Branch Prediction[C]//24th ACM/IEEE International Symposium on Micro architecture.1991:1028-1073.

[7] Patterson D A,Hennessy J L.Computer Architecture:A Quantitative Approach[M].2nd ed.Morgan Kaufmann,San Mateo,CA,1996.

[8] Hoogerbrugge J.Dynamic branch prediction for a VLIW processor[C]//International Conference on Parallel Architectures & Compilation Techniques,2000:207-214.

[9] Faravelon A,Fournel N,Pétrot F.Fast and accurate branch predictor simulation[C]//Design,Automation & Test in Europe Conference & Exhibition (DATE),2015.IEEE,2015:317-320.

[10] Zhou P,Nder S,Carr S.Fast branch misprediction recovery in out-of-order superscalar processors[C]//Proceedings of the 19th annual international conference on Supercomputing.ACM,2005:41-50.

[11] Eden A N,Mudge T.The YAGS branch prediction scheme[C]//Microarchitecture,1998.MICRO-31.Proceedings.31st Annual ACM/IEEE International Symposium on.IEEE,1998:69-77.

[12] 謝子超,佟冬,黃明凱.A General Low-Cost Indirect Branch Prediction Using Target Address Pointers[J].Journal of Computer Science & Technology,2014,29(6):929-946.

[13] 肖澤強.動態(tài)分支預測技術分析與量化研究[J].信息技術,2011(3):80-82.

[14] 張筱,史戰(zhàn)果,吳迪.基于SimpleScalar的動態(tài)分支預測器研究[J].微型電腦應用,2011,27(11):19-21.

[15] 顧慧,龔育昌,趙振西.超長指令字技術[J].小型微型計算機系統,2000,21(2):174-177.

A DESIGN OF HYBRID BRANCH PREDICTOR SUPPORTING SUPERSCALAR-VLIW HYBRID MICROPROCESSOR

Fu Jiawei Wang Xu He Hu

(InstituteofMicroelectronics,TsinghuaUniversity,Beijing100084,China)

A design of hybrid branch predictor on a digital signal processor which supports Superscalar-VLIW hybrid architecture is described. To control hardware complexity and improve the accuracy of prediction, a hybrid branch predictor of bimodal and PAp is selected for the branch prediction scheme. The standard DSPstone programs have been run on the processor. The experimental results show that the processor with hybrid branch predictor has an improvement of 23% on average compared with processor without branch predictor, and processor with hybrid branch predictor predicts more accurately than processor with only bimodal predictor.

Digital signal processor Superscalar VLIW Branch prediction Bimodal prediction PAp

2016-01-12。核高基重大專項基金項目(2012ZX01034001-002)。付家為，碩士生，主研領域：微處理器架構設計。王旭，碩士生。何虎，副教授。

TP303

A

10.3969/j.issn.1000-386x.2017.02.018