一種支持Superscalar-VLIW混合架構(gòu)處理器的混合分支預(yù)測(cè)設(shè)計(jì)

付家為 王 旭 何 虎

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

一種支持Superscalar-VLIW混合架構(gòu)處理器的混合分支預(yù)測(cè)設(shè)計(jì)

付家為 王 旭 何 虎

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

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

數(shù)字信號(hào)處理器 超標(biāo)量 超長(zhǎng)指令字 分支預(yù)測(cè) 雙峰預(yù)測(cè) PAp

0 引 言

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

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

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

現(xiàn)有技術(shù)中，動(dòng)態(tài)分支預(yù)測(cè)已在Superscalar結(jié)構(gòu)上充分利用，而VLIW結(jié)構(gòu)的分支預(yù)測(cè)功能多采用靜態(tài)預(yù)測(cè)，由軟件調(diào)度。事實(shí)上，大多數(shù)VLIW結(jié)構(gòu)使用延遲跳轉(zhuǎn)技術(shù)[7]，這大大增加了編譯器的負(fù)擔(dān)，尤其對(duì)于VLIW結(jié)構(gòu)單周期多發(fā)射指令編譯，編譯器為填滿(mǎn)延遲槽大大增加了軟件負(fù)擔(dān)[8]。所以，為VLIW結(jié)構(gòu)設(shè)計(jì)動(dòng)態(tài)分支預(yù)測(cè)方法具有重要的意義。

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

1 Orchid結(jié)構(gòu)

1.1 Orchid硬件結(jié)構(gòu)

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

圖1 Orchid整體結(jié)構(gòu)圖

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

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

1.2 Orchid流水線結(jié)構(gòu)

Orchid流水線設(shè)計(jì)為十級(jí)流水線結(jié)構(gòu)，主要分為Fetch_PG、Fetch_PS、Fetch_WT、Fetch_IR、Fetch_EXP、Dispatch、Decode、Exe1、Exe2、Exe3，如圖2所示。流水線各級(jí)功能如下：

Fetch_PG：分支預(yù)測(cè)以及產(chǎn)生PC地址。

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

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

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

Fetch_EXP：將16位于32位指令統(tǒng)一擴(kuò)展成32位指令，每6條指令形成一個(gè)擴(kuò)展包。

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

Decode：指令解碼。

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

圖2 Orchid流水線結(jié)構(gòu)圖

2 Orchid雙模式分支預(yù)測(cè)設(shè)計(jì)

2.1 Orchid 雙峰-PAp混合預(yù)測(cè)器結(jié)構(gòu)

本設(shè)計(jì)采用了雙峰預(yù)測(cè)器與PAp預(yù)測(cè)器結(jié)合的混合預(yù)測(cè)結(jié)構(gòu)，對(duì)于不同的跳轉(zhuǎn)指令采用不同的預(yù)測(cè)機(jī)制，充分發(fā)揮兩種預(yù)測(cè)器的優(yōu)勢(shì)。

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

圖3 分支預(yù)測(cè)原理圖

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

圖4 雙峰預(yù)測(cè)器BTB表示意圖

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

圖5 PAp預(yù)測(cè)器BTB表示意圖

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

2.2 Superscalar-VLIW雙模式下分支預(yù)測(cè)技術(shù)

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

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

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

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

2.3 分支預(yù)測(cè)的技術(shù)改進(jìn)

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

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

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

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

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

圖8 跳轉(zhuǎn)示例程序

PT模式表的計(jì)數(shù)器位數(shù)同樣決定了PAp預(yù)測(cè)器預(yù)測(cè)的準(zhǔn)確率。當(dāng)計(jì)數(shù)器為3位時(shí)，計(jì)數(shù)范圍是0～7，對(duì)于循環(huán)次數(shù)大于8的跳轉(zhuǎn)指令，則無(wú)法記錄每次跳轉(zhuǎn)方向，所以增加計(jì)數(shù)器位數(shù)可有效提高預(yù)測(cè)的命中率。但是增加計(jì)數(shù)器位數(shù)又會(huì)增大面積與功耗，所以計(jì)數(shù)器位數(shù)的選擇應(yīng)為命中率與面積功耗折中的結(jié)果。

3 性能評(píng)測(cè)

3.1 對(duì)2.3節(jié)分支預(yù)測(cè)技術(shù)改進(jìn)性能指標(biāo)評(píng)測(cè)

本實(shí)驗(yàn)采用DSPstone基準(zhǔn)程序?qū)μ幚砥骷胺种ьA(yù)測(cè)部分性能進(jìn)行評(píng)估。表1對(duì)2.3節(jié)分支預(yù)測(cè)技術(shù)改進(jìn)前后預(yù)測(cè)準(zhǔn)確率進(jìn)行對(duì)比，由表中可以看出，改進(jìn)后分支預(yù)測(cè)命中率較改進(jìn)前均有明顯提升，即對(duì)于混合預(yù)測(cè)器，預(yù)測(cè)訓(xùn)練時(shí)間較改進(jìn)前大大減少，命中率最高可以提升32%，命中率平均提升23%。

表1 改進(jìn)分支預(yù)測(cè)器預(yù)測(cè)命中率比較

3.2 混合預(yù)測(cè)器與單一預(yù)測(cè)器以及不采用分支預(yù)測(cè)器性能比較

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

表2 混合預(yù)測(cè)器與單一預(yù)測(cè)器及 無(wú)分支預(yù)測(cè)器性能預(yù)測(cè)命中率比較 %

表3是混合預(yù)測(cè)器與雙峰預(yù)測(cè)器相比無(wú)分支預(yù)測(cè)器運(yùn)行時(shí)間提升的比較，可以看出，混合預(yù)測(cè)器與雙峰預(yù)測(cè)器對(duì)于程序運(yùn)行時(shí)間提升明顯，并且混合預(yù)測(cè)器相比單一雙峰預(yù)測(cè)器運(yùn)行時(shí)間也都有明顯提升，最高提升達(dá)38%。

表3 混合預(yù)測(cè)器與雙峰預(yù)測(cè)器相比 無(wú)分支預(yù)測(cè)器運(yùn)行時(shí)間提升比較 %

3.3 綜合報(bào)告

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

表4 綜合報(bào)告

4 結(jié) 語(yǔ)

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

[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] 肖澤強(qiáng).動(dòng)態(tài)分支預(yù)測(cè)技術(shù)分析與量化研究[J].信息技術(shù),2011(3):80-82.

[14] 張?bào)?史戰(zhàn)果,吳迪.基于SimpleScalar的動(dòng)態(tài)分支預(yù)測(cè)器研究[J].微型電腦應(yīng)用,2011,27(11):19-21.

[15] 顧慧,龔育昌,趙振西.超長(zhǎng)指令字技術(shù)[J].小型微型計(jì)算機(jī)系統(tǒng),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。核高基重大專(zhuān)項(xiàng)基金項(xiàng)目(2012ZX01034001-002)。付家為，碩士生，主研領(lǐng)域：微處理器架構(gòu)設(shè)計(jì)。王旭，碩士生。何虎，副教授。

TP303

A

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