摘 要：現(xiàn)有的分支預測模型無法完全準確預測處理器中各種指令的行為，導致處理效率受限。為此提出了兩種混合預測解決方案，旨在結合多種分支預測模型，以提高預測的準確性和處理器的執(zhí)行效率。將TAGE（tagged geometric history length）分支預測模型與BATAGE（Bayesian tagged geometric history length）分支預測模型的預測結果轉交Hybrid模型。在預測階段中，Hybrid模型會根據(jù)TAGE和BATAGE的歷史表現(xiàn)去選擇表現(xiàn)最佳分支預測模型的預測結果。而在更新階段中，Hybrid模型會根據(jù)設計的混合預測策略對需要更新條目的飽和計數(shù)器進行更新。在CBP（championship branch prediction）軟件仿真平臺提供的440個測試程序上進行實驗，實驗結果表明：與多種最新主流分支預測模型相比，兩種混合預測解決方案的預測錯誤率均低于它們。該研究為預測所有指令模式行為問題提供了有效解決方案。在實際CPU的分支指令預測，該研究提供了一些實用價值。

關鍵詞：TAGE；BATAGE；分支預測；混合預測

中圖分類號：TP332 文獻標志碼：A 文章編號：1001-3695（2024）09-028-2766-07

doi：10.19734/j.issn.1001-3695.2023.12.0641

Design of efficient hybrid predicting strategies

Fang Xinyu1，Zhou Rigui1，Gong Mingqing2

（1.College of Information Engineering，Shanghai Maritime University，Shanghai 201306，China;2.Hangzhou Today’s Headlines Technology Co.，Ltd.，Hangzhou 311100，China）

Abstract：The existing branch prediction models can’t predict the behaviors of various instructions in the processor accurately，which leads to the limitation of processing efficiency.Therefore，this paper proposd two hybrid prediction solutions，which aimed to combine multiple branch prediction models to improve prediction accuracy and processor execution efficiency.This paper transferred the prediction results of TAGE branch prediction model and BATAGE branch prediction model to the Hybrid model.In the prediction phase，the Hybrid model selected the prediction results of the best-performing branch prediction model based on the historical performance of TAGE and BATAGE.In the update phase，the Hybrid model updated the saturation counter of the entries that needed to be updated according to the designed hybrid prediction strategy.Experiments on 440 test programs provided by the CBP software simulation platform show that the prediction error rates of both hybrid prediction solutions are lower than those of many of the latest mainstream branch prediction models.This study provides an effective solution to the problem of predicting all command mode behaviors.In the branch instruction prediction of real CPU，this research provides some practical value.

Key words：TAGE;BATAGE;branch prediction;hybrid prediction

0 引言

分支預測是計算機體系結構領域中的一個重要研究主題，尤其是在高性能處理器設計方面?，F(xiàn)代中央處理器［1］都廣泛采用分支預測技術［2］，其主要目的是預測程序中的控制流路徑，以減少由于分支指令引起的處理器流水線中的延遲和中斷。在分支預測的研究中，最常見的挑戰(zhàn)包括減少條件分支指令的錯誤預測來提高預測準確性。然而，目前的分支預測模型都無法精準預測所有類型的條件分支指令。針對這個問題，國內外研究人員在過去十幾年作出諸多貢獻：在處理器設計的早期階段，簡單的靜態(tài)預測策略得到了廣泛應用。隨著計算需求加深，動態(tài)預測技術［3］逐漸成為主流，如二級自適應訓練分支預測模型（Bimodal［4］，Gshare［5］）、高精度條件分支預測模型TAGE［6］及其優(yōu)化模型［7～9］、以及結合多個分支預測模型的混合預測模型［10］。此外，還有嘗試利用神經(jīng)網(wǎng)絡模型［11］來捕捉更復雜的分支行為。在實際應用上，學術界［12，13］在Sonic Boom開源IP核中應用了分支預測模型，工業(yè)界［14，15］在具體產(chǎn)品也中也應用了分支預測技術。

為了盡可能預測大多數(shù)條件分支指令，主要方案包括基于傳統(tǒng)TAGE分支預測模型的優(yōu)化；引入具有強大學習能力的網(wǎng)絡模型［16，17］；組合不同預測模型的混合預測［18］，能夠利用各個預測模型特點，提升預測精度并適應各種分支指令行為。本文旨在結合兩種分支預測模型并且設計混合預測策略，以提高預測準確性，適應更多應用測試場景。最新提出的混合預測模型采用BATAGE與無偏差神經(jīng)網(wǎng)絡預測模型相結合［19］，雖然提高了預測準確度，但是需要較長時間訓練模型才能達到理想效果。

本文將TAGE與BATAGE［20］分支預測模型相結合，并且設計混合預測策略來提高預測準確性。如何得到最終預測結果是需要考慮的問題。所以，本文設計適應性增減策略和權重策略兩種混合預測策略方案。通過利用兩種分支預測模型的預測結果和混合預測策略，得出最終預測結果?；旌项A測策略采用單獨載體接受TAGE和BATAGE的預測結果，這里稱為Hybrid預測模型，其本身為標記預測表。在混合預測策略中，適應性增減策略考慮全部歷史信息模式行為對當前決策的影響；而權重策略更加注重考慮近期歷史信息模式行為對當前決策的影響，削弱早期歷史信息模式行為的影響。在預測方面上，兩種混合預測策略都是選擇歷史表現(xiàn)最好預測模型的預測結果。在更新方面上，適應性增減策略是在需要更新的條目上自增或自減；權重策略是在需要更新的條目上采用指數(shù)平滑法。

1 預測模型及預測模型架構介紹

1.1 TAGE分支預測模型

TAGE分支預測模型結構如圖1所示，由一張基礎預測表和四張標記預測表組成，分別用T0，T1，T2，T3，T4表示。基礎預測表由多項條目組成，每項條目是用于預測的飽和計數(shù)器，標記預測表的每項條目由標簽（tag）、預測位（pred）和評估置信度（u）三部分組成。基礎預測表和標記預測表的條目組成如圖2和3所示。

在TAGE分支預測模型中，每張標記預測表需要不同長度的分支歷史信息來匹配條目的標簽，其所需長度遵循

L（i）=（int）（αi-1×L（i）+0.5）（1）

其中：1≤i≤M，M表示標記預測表的數(shù)量。基礎預測表用PC（program counter）來索引和匹配條目，匹配到條目所對應的飽和計數(shù)器負責提供預測結果。另外，標記預測表將PC與不同長度的歷史信息進行哈希運算來完成標簽匹配。若標簽匹配成功，表明某張標記預測表命中，最終預測結果源自于成功匹配到所需最長歷史信息的標記預測表。若所有標記預測表的標簽都未能命中，則采用基礎預測表的預測結果作為最終預測結果。

TAGE分支預測模型的更新策略主要針對更新條目的pred和u字段進行調整。這里引入provider和altpred的概念，分別表示匹配最長和次長歷史信息預測表。u字段會根據(jù)是否準確預測進行調整：當provider和altpred不同時，它會遞減，否則會遞增。在文獻［6］中，每256K分支指令都會定期重置u。對于provider，若TAGE分支預測模型預測準確，則更新provider的pred字段。相反，如果TAGE分支預測模型預測不正確并且provider不是所需最長歷史信息的預測表，則不僅更新provider的pred字段，而且在比provider所需歷史信息更長的預測表中分配新條目。新分配條目需要初始化：u字段初始化為0，pred字段初始化為weak correct。

1.2 BATAGE分支預測模型

BATAGE與TAGE分支預測模型結構相同，同樣也是由基礎預測表和標記預測表組成。BATAGE與TAGE分支預測模型結構不同主要在于引入貝葉斯置信度評估機制和條目分配受控分配機制替代原有TAGE的預測和更新機制，下面詳細介紹BATAGE與TAGE分支預測模型結構的不同之處。

BATAGE條目組成：基礎預測表T0條目組成如圖2所示，由飽和計數(shù)器位所組成；標記預測表從T1到T4條目組成如圖4所示，tag表示標簽用于匹配，n1與n0記錄條件分支指令的跳轉和未跳轉次數(shù)。BATAGE分支預測模型會通過n1與n0字段計算當前條目的錯誤預測率并且選擇最終預測結果。

貝葉斯置信度評估機制應用在分支預測階段，在BATAGE分支預測模型的預測階段：

a）在基礎預測表中，預測結果直接通過分支指令的PC值索引基礎預測表中的條目獲得。

b）在標記預測表中，通過條件分支指令的PC值與分支歷史信息進行哈希運算，其結果去匹配標記預測表的標簽，其中不同的標記預測表所需歷史信息長度也是不同的。另外，BATAGE［20］分支預測模型所描述的貝葉斯置信度評估機制利用n0和n1字段來計算當前錯誤預測率qi。若錯誤預測率越低，則置信度越高。

c）若標記預測表都沒有匹配成功，則采用基礎預測表結果。反之，根據(jù)每張預測表得到的錯誤預測率qi，選取結果qi最小對應標記預測表的預測結果；若qi存在相等的情況，此時根據(jù)匹配成功的標記預測表所對應歷史信息長度情況，選擇歷史信息長度最長對應標記預測表的預測結果。

條目分配受控分配機制應用在分支預測錯誤階段，為每個錯誤預測的預測表都分配新條目不是最佳策略，過度分配會導致許多預測表的條目通過貝葉斯置信度評估機制，導致預測不夠準確，進而導致分支預測模型缺乏足夠多歷史信息來提供準確預測。

其中心思想是比較NHC（中置信度/低置信度）的條目數(shù)量和MHC（適度高置信度）的條目數(shù)量，其中MHC介于特定范圍內（文獻［20］中為0.17～1/3）。監(jiān)控MHC與NHC條目比例來調整分配概率，若其比例大于設定閾值，則增加分配概率，反之，減少分配概率。

1.3 分支預測模型缺陷

TAGE分支預測模型廣泛應用于現(xiàn)代微處理器，以提高指令流水線處理效率。該模型采用非標記預測表加標記預測表的多表架構，每張標記預測表的哈希運算需要不同長度的歷史信息，這能夠捕獲廣泛的程序行為模式。通過在表中利用不同長度的歷史信息，TAGE分支預測模型可以與分支指令行為最佳地保持一致。除基礎預測表外，每個預測表條目都帶有標簽，這有助于區(qū)分所需不同長度的分支歷史信息，以減少預測沖突和不準確。TAGE分支預測模型歷史長度的幾何級數(shù)確保了從短期到長期分支歷史信息的覆蓋，增強了預測的靈活性和準確性。

TAGE分支預測模型的流程如圖5所示。盡管TAGE分支模型因高精度和適應性而受到青睞，但是存在一個稱為冷計數(shù)器的問題：其中弱偏差分支指令需要大量訓練，飽和計數(shù)器才能實現(xiàn)最佳預測能力。若跳轉概率越大，那么計算錯誤概率趨于穩(wěn)定的次數(shù)越多。

BATAGE分支預測模型以TAGE分支預測模型為基礎，在不改變核心結構的情況下引入了多項關鍵修改。這些修改包括：a）標記預測表的條目新穎組合，用跳轉發(fā)生次數(shù)（n1）和非跳躍發(fā)生次數(shù)（n0）的計數(shù)器替換原始預測（pred）和評估置信度（u）位；b）采用貝葉斯置信估計機制進行預測，而不是TAGE分支預測模型選擇最長匹配歷史信息對應預測表的預測結果；c）針對錯誤分配情況，創(chuàng)新受控條目分配機制，用于評估條目分配的必要性?；谝陨先c，這些修改使BATAGE模型能夠有效緩解冷計數(shù)器問題。

雖然引入貝葉斯置信度估計和受控條目分配機制緩解了冷計數(shù)器問題，但它還是存在某些限制：雖然這些機制賦予BATAGE分支預測模型對復雜分支指令行為的卓越預測能力，但比TAGE分支預測模型更加復雜。BATAGE分支預測模型具體流程如圖6所示。從圖6可知，預測階段不再是選取成功匹配到最長歷史信息標記預測表的預測結果，而是先選取錯誤預測率最小條目標記預測表的預測結果。若存在相等的情況，再從中選取成功匹配到最長歷史信息標記預測表的預測結果；更新階段不再是直接分配新條目，而需要判斷是否再分配新條目的可能性。雖然增強了弱偏差指令的預測準確性，但是在某些應用測試場景其預測準確性可能并不總是優(yōu)于TAGE，這一發(fā)現(xiàn)將在3.3節(jié)BATAGE與TAGE分支預測模型對比實驗中得到進一步驗證。

1.4 現(xiàn)有的預測模型結構

本文指令主要分成條件分支指令和其他類型指令。對于其他類型指令，它們只需要目標預測地址。然而對于條件分支指令，不僅需要提供預測目標地址，而且還需要提供條件分支指令的預測方向。如圖7所示，BATAGE分支預測模型負責提供條件分支指令預測方向，BTB（branch target buffer）模塊則提供所有指令的目標預測地址，RAS（return address stack）模塊專門處理返回指令的目標預測地址。

從圖7可知，如果指令是條件分支指令，此時BTB模塊與BATAGE分支預測模型會負責提供目標預測地址和目標預測方向。BATAGE分支預測模型將不同長度的分支歷史信息與獲取的PC值進行哈希運算。然后，在BATAGE分支預測模型的預測機制下，確定條件分支指令的預測方向。另外，獲取的PC需要掃描BTB模塊的tag表以查找匹配項。若tag表存在匹配項，那么對應targ表的條目提供目標預測地址。如果指令是其他類型指令，那么目標預測地址由BTB和RAS模塊提供。對其他類型指令進一步細分，當指令為無條件跳轉指令，那么jmp表會提供目標預測地址；當指令為返回指令，那么ret表提供RAS模塊的訪問地址，RAS模塊提供返回指令的目標預測地址。由于現(xiàn)代處理器為超標量處理器，所以獲取的PC為一組連續(xù)指令，bidx表用于標識一系列連續(xù)指令中，哪一條指令負責引發(fā)控制流的預測。

BATAGE單一分支預測模型無法完全準確預測各種指令行為，為實現(xiàn)分支預測模型能夠在更多的應用測試場景中展現(xiàn)良好的預測效果，一般流行的方案是采用混合預測技術：將兩種或者多種分支預測模型結合進行預測，多項預測結果根據(jù)某種策略選擇最終預測結果。具體解決方案主要分兩種：將網(wǎng)絡相關預測模型與傳統(tǒng)分支預測模型集成［21］，其中網(wǎng)絡模型的算法需要大量的訓練才能實現(xiàn)最佳性能，這是采用網(wǎng)絡模型的弱勢之處；將傳統(tǒng)主流的分支預測模型進行結合預測，目的在于減少訓練時間。本文采用后者方案，鑒于TAGE分支預測模型的高效簡單性特點，以及BATAGE分支預測模型能夠緩解冷計數(shù)器問題的優(yōu)勢，本文提出了一種結合TAGE和BATAGE分支預測模型兩者優(yōu)勢的混合預測方法，并且設計相應的混合預測策略來提升分支預測模型在不同應用場景的預測效果。

2 優(yōu)化的預測模型結構及混合預測策略

2.1 改進的預測模型結構

為解決BATAGE分支預測模型在適應多樣化應用測試場景的局限性，本文在現(xiàn)有預測模型結構基礎上進行優(yōu)化，具體如圖8所示。與現(xiàn)有預測模型結構相比，不同之處在于增加了TAGE分支預測模型和名為Hybrid的預測模型，Hybrid預測模型本身為一張標記預測表，其條目組成如圖9所示，其中tag負責索引匹配，count_tage和count_batage字段分別表示TAGE與BATAGE分支預測模型預測條件分支指令的效用評分。

在優(yōu)化的預測模型結構中，對于條件分支指令，TAGE和BATAGE分支預測模型會將不同長度分支歷史信息和PC進行哈希運算，所得結果在這兩種分支預測模型同時進行索引匹配，它們的預測結果轉交Hybrid預測模型，Hybrid預測模型會根據(jù)混合預測策略選擇對應分支預測模型的預測結果。其余方面與原有預測模型結構做法一致。對于其他類型分支指令，與原有的預測模型結構采取相同措施。

在下面的程序段中，一個名為function的函數(shù)接收四個整型參數(shù)a、b、c、d。該函數(shù)主要執(zhí)行一個條件循環(huán)，循環(huán)中的加法操作是否執(zhí)行取決于變量d的狀態(tài)，這直接影響到程序執(zhí)行效率。這是因為加法操作的執(zhí)行依賴于if語句前變量d的值，而循環(huán)的持續(xù)性則依賴于變量a逐步遞減至零。如果這類具有指令依賴性的程序較為少見，可以采用簡單的混合預測策略進行處理。相反，如果這類程序較為常見，則需要采取考慮指令依賴性影響的相應混合預測策略。針對指令依賴性問題，已有一些解決方法［22～24］。鑒于此，本文設計了適應性增減策略和權重策略兩種混合預測策略，這兩種策略將基于TAGE和BATAGE的歷史表現(xiàn)來評估并選擇最準確的預測結果。具體的指令依賴性示例程序如下：

int function（int a，int b，int c，int d）{

c=a;

a=0;

do{

d=d & 1;

if（d ！=0）{

a=a+c;

}

a=a/2;

c=c * 2;

}while（a ！=0）

}

2.2 適應性增減策略

適應性增減策略以其簡單性和直觀性為特點，有利于實施和理解，比較適合處理指令依賴性的程序較為少見的情況。在TAGE和BATAGE固有的分支預測模型中，保持簡單而有效地選擇機制來提高預測準確性，同時降低實施的復雜性。該策略整合了所有的歷史信息來評估TAGE和BATAGE分支預測模型的預測能力。

在優(yōu)化的預測模型結構中，Hybrid預測模型接收來自BATAGE和TAGE分支預測模型的預測結果。Hybrid預測模型需要當前指令PC去匹配預測表的標簽。如果沒有成功匹配，Hybrid預測模型默認選擇TAGE分支預測模型的預測結果。如果匹配成功并且count_tage值比count_batage值大，則TAGE分支預測模型的預測結果具有更加可靠性；否則，采用BATAGE分支預測模型的預測結果。適應性增減策略預測算法的偽代碼如算法1所示。

算法1 適應性增減策略預測算法

輸入：程序計數(shù)器PC和分支歷史信息history。

輸出：最終預測結果Rfinal。

a）初始化 由PC和history獲取TAGE預測結果RTAGE和BATAGE預測結果RBATAGE。

b）將PC和history進行哈希運算得出索引index

c）while t<NUMSIZE do //NUMSIZE為預測表最大條目數(shù)

由index找到Hybrid預測模型對應條目hybridEntry;

t←t+1;

end while

d）if hybridEntry.tag≠（PC & 0x3F）then /*若不能成功匹配，PC取低位與標簽作匹配*/

Rfinal←RTAGE;

返回Rfinal;

end if

e）if hybridEntry.count_tage<hybridEntry.count_batage then

Rfinal←RBATAGE;

返回Rfinal;

else

Rfinal←RTAGE;

返回Rfinal;

end if

指令執(zhí)行后需要更新預測模型的條目。TAGE和BATAGE分支預測模型根據(jù)各自的算法進行更新。Hybrid預測模型也會更新其預測表的條目：如果最終預測結果與實際執(zhí)行結果相同，此時會根據(jù)預測階段所選分支預測模型，條目中對應的飽和計數(shù)器（count_batage或者count_tage字段）自增。相反，則會發(fā)生類似的自減過程。適應性增減策略的更新算法如算法2所示。

算法2 適應性增減策略更新算法

輸入：實際執(zhí)行結果resolveDir，最終預測結果preDir和實際選擇分支預測模型tageOrBatage。

輸出：更新條目hybridEntry。

a）初始化 根據(jù)PC和分支歷史信息history使用哈希運算得出索引index

b）while t<NUMSIZE do //NUMSIZE為預測表最大條目數(shù)

由index找到Hybrid預測模型對應條目hybridEntry;

t←t+1;

end while

c）if resolveDir=preDir then //若實際結果與預測結果相同

if tageOrBatage=0 then //若此時選擇TAGE分支模型

hybridEntry.count_tage自增;

else //若此時選擇BATAGE分支模型

hybridEntry.count_batage自增;

end if

else //若實際結果與預測結果不相同

if tageOrBatage=0 then //若此時選擇TAGE分支模型

hybridEntry.count_tage自減;

else //若此時選擇BATAGE分支模型

hybridEntry.count_batage自減;

end if

end if

返回hybridEntry;

在適應性增減策略中，主要分為預測算法和更新算法。假設Hybrid預測模型的標記預測表最大條目數(shù)為N。在預測算法中，步驟a）初始化的時間復雜度為O（1），步驟b）根據(jù)哈希運算得到的索引時間復雜度為O（1），步驟c）根據(jù)索引查找對應條目的時間復雜度為O（N），步驟d）和e）判斷成功或者失敗匹配情況的時間復雜度為O（1），經(jīng)過分析可得到適應性增減策略預測算法的時間復雜度為O（N）；在更新算法中，步驟a）初始化計算的索引時間復雜度為O（1），步驟b）根據(jù)索引查找對應條目的時間復雜度為O（N），步驟c）更新條目的時間復雜度為O（1），經(jīng)過分析可得適應性增減策略更新算法的時間復雜度為O（N）。

2.3 權重策略

權重策略選擇最終預測結果基于的前提：最近預測結果比早期預測結果更有價值。對于指令依賴性程序，該策略有助于快速適應最近指令模式行為，并減少早期指令模式行為的影響。適應性增減策略整合了全部歷史信息，而權重策略則強調即時性。這種方法特別是在指令模式行為突然轉變的情況下，能夠提供良好預測能力。

值得注意的是，權重策略采用一次指數(shù)平滑法更新Hybrid預測模型的條目。一次指數(shù)平滑法是時間序列分析和預測所使用的方法。其核心公式為

St=（1-α）×Yt+α×St-1（2）

其中：St為當前時間的預測值;St-1為上次時間的預測值;Yt是當前時間的實際觀測值;α為平滑因子，取值為在0～1。這里采用一次指數(shù)平滑法的原因是其計算簡單的特點，并且能夠減少對硬件資源需求，更加適應中央處理器的高頻操作，所以二次和三次指數(shù)平滑法不適合用于權重混合預測策略。

指數(shù)平滑在時間序列分析中的有效性使得它可以用于分支預測，作為指令模式行為的加權評價方法。在這種情況下，各個變量的含義與原來不同：St表示Hybrid預測模型中標記預測表的飽和計數(shù)器更新值；Yt表示Hybrid的預測結果和實際結果的一致性，若Hybrid的預測結果和實際結果一致，則Yt為1，反之為-1；St-1表示Hybrid預測模型中條目的飽和計數(shù)器最近一次更新值；α作為衰減因子，調節(jié)最近與早期歷史信息的影響，衰減因子采用0.01、0.50和0.99，由式（2）可知系數(shù)越小越側重最近指令模式行為。

權重策略預測算法與適應性增減策略是相同的，具體如算法1所示。在權重策略更新算法中，如算法3所示，Hybrid預測模型也會更新其預測表的條目：如果最終預測結果與實際執(zhí)行結果相同，此時會根據(jù)預測階段所選分支預測模型，條目中對應的飽和計數(shù)器（count_batage或者count_tage字段）會基于式（2）進行更新。相反，則會發(fā)生類似的更新過程。

算法3 權重策略更新算法

輸入：實際執(zhí)行結果resolveDir，最終預測結果preDir和實際選擇分支預測模型tageOrBatage。

輸出：更新條目hybridEntry。

a）初始化 根據(jù)PC和分支歷史信息history使用哈希運算得出索引index

b）while t<NUMSIZE do //NUMSIZE為預測表最大條目數(shù)

由index找到Hybrid預測模型對應條目hybridEntry;

t←t+1;

end while

c）if resolveDir=preDir then //若實際結果與預測結果相同

if tageOrBatage=0 then //若此時選擇TAGE分支模型

hybridEntry.Count_tage基于式（2）進行更新;

else //若此時選擇BATAGE分支模型

hybridEntry.Count_batage基于式（2）進行更新;

end if

else //若實際結果與預測結果不相同

if tageOrBatage=0 then //若此時選擇TAGE分支模型

hybridEntry.count_tage基于式（2）進行更新;

else //若此時選擇BATAGE分支模型

hybridEntry.count_batage基于式（2）進行更新;

end if

end if

返回hybridEntry;

在權重策略中，主要分為預測算法和更新算法。假設Hybrid預測模型的標記預測表最大條目數(shù)為N。在預測算法中，它與適應性增減策略的預測算法相同，所以權重策略預測算法的時間復雜度為O（N）；在更新算法中，步驟a）初始化計算索引的時間復雜度為O（1），步驟b）根據(jù)索引查找對應條目的時間復雜度為O（N），步驟c）更新條目的時間復雜度為O（1），經(jīng)過分析可得權重策略更新算法的時間復雜度為O（N）。

3 仿真實驗及結果分析

3.1 分支預測模型參數(shù)設置

本文測試對象為TAGE、TAGE-SC-L、BATAGE、multi-perceptron［25］和混合預測模型。預測模型的預測準確性與其配置參數(shù)緊密相關。總大小8 Kb量限制并且上下浮動在0.5 Kb以內，確保各種預測模型能夠在指定的大小范圍進行預測，從而提供更均衡和穩(wěn)定的預測表現(xiàn)。這種參數(shù)配置旨在保持測試的相對公平性。各種預測模型的大小如表1所示。

在TAGE分支預測模型中，基礎預測表項數(shù)16，每項為2 bit飽和計數(shù)器，大小0.003 9 Kb；標記預測表為4張表（每張表項數(shù)4 096），其中每項由2 bit置信度、3 bit飽和計數(shù)器和11 bit標簽組成，大小8 Kb。

在TAGE-SC-L分支預測模型中，TAGE基礎預測表項數(shù)為128，每項為3 bit飽和計數(shù)器，大小為0.046 9 Kb。標記預測表為4張表（每張表項數(shù)1 024），每項由2 bit置信度、3 bit飽和計數(shù)器和10 bit標簽組成，大小7.500 0 Kb。循環(huán)預測表（LOOP）項數(shù)為8，每項占38 bit，其中記錄迭代次數(shù)占10 bit，評估置信度占4 bit，記錄當前迭代次數(shù)占10 bit，標簽占10 bit，當前條目的年齡占4 bit，總共大小為0.037 1 Kb。校正器（SC）由存儲偏置值的偏置表，記錄迭代次數(shù)的表，基于分支寬度預測表，基于全局歷史表和基于局部歷史表組成，每張表項數(shù)為128，其中每項為3 bit飽和計數(shù)器，大小為0.234 4 Kb。

在multi-perceptron分支預測模型中，其中特征權重大小為1.270 6 Kb，特征權重表以外表所占大小為6.698 7 Kb。

在BATAGE分支預測模型中，基礎預測表項數(shù)8，每項為3 bit飽和計數(shù)器，總計0.002 9 KBit。標記預測表為4張表（每張表項數(shù)1 024），其中每項由2個3 bit飽和計數(shù)器和10位標簽組成，大小8 KBit。

在混合預測模型中，TAGE基礎預測表項數(shù)為1 024，每項為2 bit飽和計數(shù)器，大小0.25 Kb。標記預測表為4張表（每張表項數(shù)2 048），每項由2 bit置信度、3 bit飽和計數(shù)器和10 bit標簽組成，大小3.75 Kb。BATAGE基礎預測表項數(shù)128，每項為3 bit飽和計數(shù)器組成，大小0.046 8 Kb。標記預測表為4張表（每張表項數(shù)256），每項由6 bit飽和計數(shù)器和10 bit標簽組成，大小2 Kb。Hybrid預測模型由1張標記預測表組成，項數(shù)1 024，每項由10 bit標簽和2個3 bit飽和計數(shù)器組成，大小2 Kb。

3.2 仿真平臺及數(shù)據(jù)集

本文采用CBP軟件仿真平臺進行實驗，該平臺是分支預測競賽中使用的分支預測模型性能評估框架，可以測得理想情況下的錯誤預測率。設計的分支預測模型性能評估框架主要調用預測算法函數(shù)和更新算法函數(shù)兩個不同的函數(shù)接口。為了測試分支預測模型的精準度，該過程將每個測試程序轉換為指令并且調用預測算法函數(shù)進行預測。預測完成之后，調用性能評估框架的更新函數(shù)，利用實際執(zhí)行結果與預測結果是否一致對分支預測模型預測表進行更新。此時一條分支指令已經(jīng)預測完成，需要預測下一條分支指令，重復此過程。

本文采用的性能指標為MPKI，它表示平均每一千條指令中錯誤預測分支指令方向的條數(shù)。所以，該性能指標越低越好?；旌夏Ｐ驮诜种ьA測方面相對于其他主流分支預測模型的性能增強通過式（3）定量表達。

P=MPKI預測模型-MPKI混合模型MPKI預測模型（3）

本文使用CBP軟件仿真平臺所提供的440個測試程序進行實驗，仿真實驗數(shù)據(jù)結果為MPKI。應用場景主要分為LONG_SERVER、LONG_MOBILE、SHORT_SERVER、SHORT_MOBILE四個種類。其中LONG_SERVER測試應用場景有8個測試程序，LONG_MOBILE測試應用場景有32個測試程序，SHORT_SERVER測試應用場景有293個測試程序，SHORT_MOBILE測試應用場景有107個測試程序。在每種測試應用場景中，測試程序最大和最小條件分支指令數(shù)情況如表2所示。

本文進行兩部分實驗：

第一組實驗為BATAGE與TAGE驗證對比：按照上述440個測試程序劃分測試應用場景進行測試，驗證BATAGE的MPKI力是否都比TAGE的MPKI值要低。

第二組實驗為混合預測模型與最新主流分支預測模型進行橫向比較：TAGE、TAGE-SC-L、BATAGE、multi-perceptron與混合模型進行對比實驗，將混合分支預測模型得到的總體MPKI和各種測試應用場景的總體MPKI與這些主流分支預測模型進行比較。

3.3 BATAGE與TAGE驗證對比

在驗證對比實驗中，在總體MPKI方面上，BATAGE比TAGE性能優(yōu)于7.833%，BATAGE與TAGE分支預測模型的總體MPKI如表3所示。

圖10可知，在四類測試應用場景中：LONG_MOBILE與SHORT_MOBILE的測試結果反映為TAGE的總體MPKI比BATAGE低。其中在LONG_MOBILE測試集種類中，TAGE的總體MPKI為2.779，BATAGE的總體MPKI為3.549；在SHORT_MOBILE測試集種類中，TAGE的MPKI為3.614，BATAGE的MPKI為3.804。所以上述結果表明：在有些測試應用場景中，BATAGE的預測能力不如TAGE。此時需要采用混合預測方式來提升預測精度，對于總體MPKI與各種測試應用場景的總體MPKI，在3.4節(jié)將會進一步詳細展示。

3.4 仿真結果分析

本節(jié)在BATAGE不能適應所有測試應用場景的基礎上，進一步橫向比較混合模型與最新主流分支預測模型。在仿真結果上，展示混合模型與各個分支預測模型的總體MPKI與各個應用測試應用場景下的MPKI值，以及測試最佳MPKI與最差MPKI，性能結果提升由式（3）得出。具體各種預測模型的MPKI值如表4所示。根據(jù)結果可知，混合模型（權重策略，α=0.01）的MPKI為5.961，其值低于各個最新主流分支預測模型的MPKI。與較優(yōu)秀的TAGE-SC-L分支預測模型相比，混合模型（權重策略，α=0.01）預測準確性提升3.06%。

從表5、6可知：在LONG_SERVER測試應用場景中，混合模型（權重策略，α=0.99）表現(xiàn)最佳，其MPKI為5.024，相較于表現(xiàn)最佳的TAGE-SC-L分支預測模型提升了7.85%；在LONG_MOBILE測試應用場景中，混合模型（權重策略，α=0.50，0.01）表現(xiàn)最佳，相較于表現(xiàn)最佳的multi-perceptron分支預測模型提升僅為2.98%；在SHORT_SERVER測試應用場景中，混合模型（適應性增減策略）表現(xiàn)最佳，其MPKI為7.444，相較于表現(xiàn)最佳的BATAGE分支預測模型提升了2.08%；在SHORT_MOBILE測試應用場景中，混合模型（權重策略，α=0.50）表現(xiàn)最佳，其MPKI為3.082，相較于表現(xiàn)最佳的multi-perceptron分支預測模型提升了9.94%。在最佳MPKI與最差MPKI的情況中：各種預測模型的最佳MPKI都一樣；各種預測模型的最差MPKI，表現(xiàn)最佳的BATAGE分支預測模型比混合預測模型具有更為穩(wěn)健的預測能力。

從仿真實驗結果可知：觀察總體MPKI和各種測試應用場景的總體MPKI，混合預測模型的預測能力優(yōu)于最新主流的分支預測模型。這一改進歸因于混合預測模型能夠融合兩種分支預測模型的優(yōu)勢，有效利用它們在不同測試應用場景的優(yōu)勢，從考慮指令依賴性角度設計兩種不同的混合預測策略來提高條件分支指令預測的準確性。

4 結束語

在分支預測中，往往存在分支預測模型不能準確預測某種應用場景的問題。針對該情況，本文提出兩種不同的混合預測策略方案來緩解該問題。將BATAGE與TAGE分支預測模型的預測結果轉交Hybrid預測模型，Hybrid通過混合預測策略得出最終預測結果。本文首先驗證BATAGE的總體MPKI力是否都比TAGE的總體MPKI值要低，然后對混合模型與最新主流分支預測模型從總體MPKI、各種測試應用場景的總體MPKI、最佳與最差MPKI三個方面進行橫向比較。本文實驗結果表明：除了最佳MPKI和最差MPKI方面，混合預測模型表現(xiàn)比各種主流分支預測模型要好。未來將利用神經(jīng)網(wǎng)絡相關模型的優(yōu)越學習能力，在盡量不增大訓練時間的情況下，將BATAGE預測模型與神經(jīng)網(wǎng)絡模型相結合來提升預測準確度。

參考文獻：

［1］Smith J E，Sohi G S.The microarchitecture of superscalar processors［J］.Proceedings of the IEEE，1995，83（12）：1609-1624.

［2］Healy I，Giordano P，Elmannai W.Branch prediction in CPU pipeli-ning［C］//Proc of the 14th Annual Ubiquitous Computing，Electronics & Mobile Communication Conference.Piscataway，NJ：IEEE Press，2023：364-368.

［3］Mittal S.A survey of techniques for dynamic branch prediction［J］.Concurrency and Computation：Practice and Experience，2019，31（1）：e4666.

［4］Smith J E.A study of branch prediction strategies［C］//Proc of the 8th Annual Symposium on Computer Architecture.1981：135-148.

［5］McFarling S.Combining branch predictors，Technical Report TN-36［R］.［S.l.］：Digital Western Research Laboratory，1993.

［6］Seznec A，Michaud P.A case for（partially）TAGGED GE-OMETRIC history length branch prediction［J］.The Journal of Instruction-Level Parallelism，2006，8：23.

［7］Seznec A.TAGE-SC-L branch predictors again［C］//Proc of the 5th JILP Workshop on Computer Architecture Competitions：Championship Branch Prediction.2016.

［8］Seznec A.A 256 kbits L-TAGE branch predictor［J］.Journal of Instruction-Level Parallelism Special Issue：The Second Championship Branch Prediction Competition，2007，9：1-6.

［9］Seznec A.A 64 Kbytes ISL-TAGE branch predictor［C］//Proc of the 2nd JILP Workshop on Computer Architecture Competitions：Championship Branch Prediction.2011.

［10］李正平，高楊.一種改進型TAGE分支預測器的實現(xiàn)［J］.遼寧工業(yè)大學學報：自然科學版，2020，40（1）：1-4.（Li Zhengping，Gao Yang.Implementation of improved TAGE branch predictor［J］.Journal of Liaoning University of Technology：Natural Science Edition，2020，40（1）：1-4.）

［11］Villon L A Q，Susskind Z，Bacellar A T L，et al.A conditional branch predictor based on weightless neural networks［J］.Neurocomputing，2023，555：126637.

［12］Zhao J，Korpan B，Gonzalez A，et al.SonicBoom：the 3rd generation Berkeley out-of-order machine［C］//Proc of the 4th Workshop on Computer Architecture Research with RISC-V.2020：1-7.

［13］Zhao J，Gonzalez A，Amid A，et al.CODRA：a framework for evaluating compositions of hardware branch predictors［C］//Proc of the 22nd IEEE International Symposium on Performance Analysis of Systems and Software.Piscataway，NJ：IEEE Press，2021：310-320.

［14］Suggs D，Subramony M，Bouvier D.The AMD “zen 2” processor［J］.IEEE Micro，2020，40（2）：45-52.

［15］Evers M，Barnes L，Clark M.The AMD next-generation“zen 3”core［J］.IEEE Micro，2022，42（3）：7-12.

［16］Jiménez D A，Lin C.Dynamic branch prediction with perceptrons［C］//Proc of the 7th HPCA International Symposium on High-Performance Computer Architecture.Piscataway，NJ：IEEE Press，2001：197-206.

［17］Zangeneh S，Pruett S，Lym S，et al.BranchNet：a convolutional neural network to predict hard-to-predict branches［C］//Proc of the 53rd Annual IEEE/ACM International Symposium on Microarchitecture.Piscataway，NJ：IEEE Press，2020：118-130.

［18］Al-Khalid A S，Omran S S.Hybrid branch prediction for pipelined MIPS processor［J］.Journal of Electrical and Computer Engine-ering，2020，10（4）：3476.

［19］Dang N M，Cao Haixuan，Tran L.BATAGE-BFNP：a high-performance hybrid branch predictor with data-dependent branches speculative pre-execution for RISC-V processors［J］.Arabian Journal for Science and Engineering，2023，48（8）：10299-10312.

［20］Michaud P.An alternative TAGE-like conditional branch predictor［J］.ACM Trans on Architecture and Code Optimization，2018，15（3）：1-23.

［21］陳智勇，廉海濤，吳星星.一種改進的神經(jīng)網(wǎng)絡分支預測技術［J］.微電子學與計算機，2014，31（11）：152-155.（Chen Zhiyong，Lian Haitao，Wu Xingxing.An improved branch prediction based on the neural network［J］.Microelectronics & Computer，2014，31（11）：152-155.）

［22］Pruett S，Patt Y.Branch runahead：an alternative to branch prediction for impossible to predict branches［C］//Proc of the 54th Annual IEEE/ACM International Symposium on Microarchitecture.2021：804-815.

［23］Khan T A，Ugur M，Nathella K，et al.Whisper：profile-guided branch misprediction elimination for data center applications［C］//Proc of the 55th IEEE/ACM International Symposium on Microarchitecture.Piscataway，NJ：IEEE Press，2022：19-34.

［24］Villon P S M.Maintaining high performance in the presence of impossible-to-predict branches［D］.Austin：The University of Texas at Austin，2022.

［25］Jiménez D A.Multiperspective perceptron predictor［C］//Proc of the 5th JILP Workshop on Computer Architecture Competitions：Championship Branch Prediction.2016.

收稿日期：2023-12-25

修回日期：2024-03-18

基金項目：國家重點研發(fā)計劃資助項目（2021YFF0601200，2021YFF0601204）

作者簡介：方昕宇（1996—），男，湖北黃岡人，碩士，CCF會員，主要研究方向為計算機體系結構；周日貴（1973—），男（通信作者），江西南昌人，教授，博導，博士，主要研究方向為智能信息處理、智能信息相關軟硬件系統(tǒng)的開發(fā)（rgzhou@shmtu.edu.cn）；龔鳴清（1994—），男，湖北黃岡人，碩士，主要研究方向為高性能計算.