高效混合預(yù)測(cè)策略的設(shè)計(jì)

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

關(guān)鍵詞：TAGE；BATAGE；分支預(yù)測(cè)；混合預(yù)測(cè)

中圖分類號(hào)：TP332 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

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

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

1 預(yù)測(cè)模型及預(yù)測(cè)模型架構(gòu)介紹

1.1 TAGE分支預(yù)測(cè)模型

TAGE分支預(yù)測(cè)模型結(jié)構(gòu)如圖1所示，由一張基礎(chǔ)預(yù)測(cè)表和四張標(biāo)記預(yù)測(cè)表組成，分別用T0，T1，T2，T3，T4表示?；A(chǔ)預(yù)測(cè)表由多項(xiàng)條目組成，每項(xiàng)條目是用于預(yù)測(cè)的飽和計(jì)數(shù)器，標(biāo)記預(yù)測(cè)表的每項(xiàng)條目由標(biāo)簽（tag）、預(yù)測(cè)位（pred）和評(píng)估置信度（u）三部分組成?；A(chǔ)預(yù)測(cè)表和標(biāo)記預(yù)測(cè)表的條目組成如圖2和3所示。

在TAGE分支預(yù)測(cè)模型中，每張標(biāo)記預(yù)測(cè)表需要不同長(zhǎng)度的分支歷史信息來匹配條目的標(biāo)簽，其所需長(zhǎng)度遵循

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

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

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

1.2 BATAGE分支預(yù)測(cè)模型

BATAGE與TAGE分支預(yù)測(cè)模型結(jié)構(gòu)相同，同樣也是由基礎(chǔ)預(yù)測(cè)表和標(biāo)記預(yù)測(cè)表組成。BATAGE與TAGE分支預(yù)測(cè)模型結(jié)構(gòu)不同主要在于引入貝葉斯置信度評(píng)估機(jī)制和條目分配受控分配機(jī)制替代原有TAGE的預(yù)測(cè)和更新機(jī)制，下面詳細(xì)介紹BATAGE與TAGE分支預(yù)測(cè)模型結(jié)構(gòu)的不同之處。

BATAGE條目組成：基礎(chǔ)預(yù)測(cè)表T0條目組成如圖2所示，由飽和計(jì)數(shù)器位所組成；標(biāo)記預(yù)測(cè)表從T1到T4條目組成如圖4所示，tag表示標(biāo)簽用于匹配，n1與n0記錄條件分支指令的跳轉(zhuǎn)和未跳轉(zhuǎn)次數(shù)。BATAGE分支預(yù)測(cè)模型會(huì)通過n1與n0字段計(jì)算當(dāng)前條目的錯(cuò)誤預(yù)測(cè)率并且選擇最終預(yù)測(cè)結(jié)果。

貝葉斯置信度評(píng)估機(jī)制應(yīng)用在分支預(yù)測(cè)階段，在BATAGE分支預(yù)測(cè)模型的預(yù)測(cè)階段：

a）在基礎(chǔ)預(yù)測(cè)表中，預(yù)測(cè)結(jié)果直接通過分支指令的PC值索引基礎(chǔ)預(yù)測(cè)表中的條目獲得。

b）在標(biāo)記預(yù)測(cè)表中，通過條件分支指令的PC值與分支歷史信息進(jìn)行哈希運(yùn)算，其結(jié)果去匹配標(biāo)記預(yù)測(cè)表的標(biāo)簽，其中不同的標(biāo)記預(yù)測(cè)表所需歷史信息長(zhǎng)度也是不同的。另外，BATAGE［20］分支預(yù)測(cè)模型所描述的貝葉斯置信度評(píng)估機(jī)制利用n0和n1字段來計(jì)算當(dāng)前錯(cuò)誤預(yù)測(cè)率qi。若錯(cuò)誤預(yù)測(cè)率越低，則置信度越高。

c）若標(biāo)記預(yù)測(cè)表都沒有匹配成功，則采用基礎(chǔ)預(yù)測(cè)表結(jié)果。反之，根據(jù)每張預(yù)測(cè)表得到的錯(cuò)誤預(yù)測(cè)率qi，選取結(jié)果qi最小對(duì)應(yīng)標(biāo)記預(yù)測(cè)表的預(yù)測(cè)結(jié)果；若qi存在相等的情況，此時(shí)根據(jù)匹配成功的標(biāo)記預(yù)測(cè)表所對(duì)應(yīng)歷史信息長(zhǎng)度情況，選擇歷史信息長(zhǎng)度最長(zhǎng)對(duì)應(yīng)標(biāo)記預(yù)測(cè)表的預(yù)測(cè)結(jié)果。

條目分配受控分配機(jī)制應(yīng)用在分支預(yù)測(cè)錯(cuò)誤階段，為每個(gè)錯(cuò)誤預(yù)測(cè)的預(yù)測(cè)表都分配新條目不是最佳策略，過度分配會(huì)導(dǎo)致許多預(yù)測(cè)表的條目通過貝葉斯置信度評(píng)估機(jī)制，導(dǎo)致預(yù)測(cè)不夠準(zhǔn)確，進(jìn)而導(dǎo)致分支預(yù)測(cè)模型缺乏足夠多歷史信息來提供準(zhǔn)確預(yù)測(cè)。

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

1.3 分支預(yù)測(cè)模型缺陷

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

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

BATAGE分支預(yù)測(cè)模型以TAGE分支預(yù)測(cè)模型為基礎(chǔ)，在不改變核心結(jié)構(gòu)的情況下引入了多項(xiàng)關(guān)鍵修改。這些修改包括：a）標(biāo)記預(yù)測(cè)表的條目新穎組合，用跳轉(zhuǎn)發(fā)生次數(shù)（n1）和非跳躍發(fā)生次數(shù)（n0）的計(jì)數(shù)器替換原始預(yù)測(cè)（pred）和評(píng)估置信度（u）位；b）采用貝葉斯置信估計(jì)機(jī)制進(jìn)行預(yù)測(cè)，而不是TAGE分支預(yù)測(cè)模型選擇最長(zhǎng)匹配歷史信息對(duì)應(yīng)預(yù)測(cè)表的預(yù)測(cè)結(jié)果；c）針對(duì)錯(cuò)誤分配情況，創(chuàng)新受控條目分配機(jī)制，用于評(píng)估條目分配的必要性。基于以上三點(diǎn)，這些修改使BATAGE模型能夠有效緩解冷計(jì)數(shù)器問題。

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

1.4 現(xiàn)有的預(yù)測(cè)模型結(jié)構(gòu)

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

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

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

2 優(yōu)化的預(yù)測(cè)模型結(jié)構(gòu)及混合預(yù)測(cè)策略

2.1 改進(jìn)的預(yù)測(cè)模型結(jié)構(gòu)

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

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

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

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 適應(yīng)性增減策略

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

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

算法1 適應(yīng)性增減策略預(yù)測(cè)算法

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

輸出：最終預(yù)測(cè)結(jié)果Rfinal。

a）初始化 由PC和history獲取TAGE預(yù)測(cè)結(jié)果RTAGE和BATAGE預(yù)測(cè)結(jié)果RBATAGE。

b）將PC和history進(jìn)行哈希運(yùn)算得出索引index

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

由index找到Hybrid預(yù)測(cè)模型對(duì)應(yīng)條目hybridEntry;

t←t+1;

end while

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

Rfinal←RTAGE;

返回Rfinal;

end if

e）if hybridEntry.count_tage<hybridEntry.count_batage then

Rfinal←RBATAGE;

返回Rfinal;

else

Rfinal←RTAGE;

返回Rfinal;

end if

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

算法2 適應(yīng)性增減策略更新算法

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

輸出：更新條目hybridEntry。

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

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

由index找到Hybrid預(yù)測(cè)模型對(duì)應(yīng)條目hybridEntry;

t←t+1;

end while

c）if resolveDir=preDir then //若實(shí)際結(jié)果與預(yù)測(cè)結(jié)果相同

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

hybridEntry.count_tage自增;

else //若此時(shí)選擇BATAGE分支模型

hybridEntry.count_batage自增;

end if

else //若實(shí)際結(jié)果與預(yù)測(cè)結(jié)果不相同

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

hybridEntry.count_tage自減;

else //若此時(shí)選擇BATAGE分支模型

hybridEntry.count_batage自減;

end if

end if

返回hybridEntry;

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

2.3 權(quán)重策略

權(quán)重策略選擇最終預(yù)測(cè)結(jié)果基于的前提：最近預(yù)測(cè)結(jié)果比早期預(yù)測(cè)結(jié)果更有價(jià)值。對(duì)于指令依賴性程序，該策略有助于快速適應(yīng)最近指令模式行為，并減少早期指令模式行為的影響。適應(yīng)性增減策略整合了全部歷史信息，而權(quán)重策略則強(qiáng)調(diào)即時(shí)性。這種方法特別是在指令模式行為突然轉(zhuǎn)變的情況下，能夠提供良好預(yù)測(cè)能力。

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

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

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

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

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

算法3 權(quán)重策略更新算法

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

輸出：更新條目hybridEntry。

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

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

由index找到Hybrid預(yù)測(cè)模型對(duì)應(yīng)條目hybridEntry;

t←t+1;

end while

c）if resolveDir=preDir then //若實(shí)際結(jié)果與預(yù)測(cè)結(jié)果相同

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

hybridEntry.Count_tage基于式（2）進(jìn)行更新;

else //若此時(shí)選擇BATAGE分支模型

hybridEntry.Count_batage基于式（2）進(jìn)行更新;

end if

else //若實(shí)際結(jié)果與預(yù)測(cè)結(jié)果不相同

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

hybridEntry.count_tage基于式（2）進(jìn)行更新;

else //若此時(shí)選擇BATAGE分支模型

hybridEntry.count_batage基于式（2）進(jìn)行更新;

end if

end if

返回hybridEntry;

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

3 仿真實(shí)驗(yàn)及結(jié)果分析

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

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

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

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

在multi-perceptron分支預(yù)測(cè)模型中，其中特征權(quán)重大小為1.270 6 Kb，特征權(quán)重表以外表所占大小為6.698 7 Kb。

在BATAGE分支預(yù)測(cè)模型中，基礎(chǔ)預(yù)測(cè)表項(xiàng)數(shù)8，每項(xiàng)為3 bit飽和計(jì)數(shù)器，總計(jì)0.002 9 KBit。標(biāo)記預(yù)測(cè)表為4張表（每張表項(xiàng)數(shù)1 024），其中每項(xiàng)由2個(gè)3 bit飽和計(jì)數(shù)器和10位標(biāo)簽組成，大小8 KBit。

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

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

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

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

P=MPKI預(yù)測(cè)模型-MPKI混合模型MPKI預(yù)測(cè)模型（3）

本文使用CBP軟件仿真平臺(tái)所提供的440個(gè)測(cè)試程序進(jìn)行實(shí)驗(yàn)，仿真實(shí)驗(yàn)數(shù)據(jù)結(jié)果為MPKI。應(yīng)用場(chǎng)景主要分為L(zhǎng)ONG_SERVER、LONG_MOBILE、SHORT_SERVER、SHORT_MOBILE四個(gè)種類。其中LONG_SERVER測(cè)試應(yīng)用場(chǎng)景有8個(gè)測(cè)試程序，LONG_MOBILE測(cè)試應(yīng)用場(chǎng)景有32個(gè)測(cè)試程序，SHORT_SERVER測(cè)試應(yīng)用場(chǎng)景有293個(gè)測(cè)試程序，SHORT_MOBILE測(cè)試應(yīng)用場(chǎng)景有107個(gè)測(cè)試程序。在每種測(cè)試應(yīng)用場(chǎng)景中，測(cè)試程序最大和最小條件分支指令數(shù)情況如表2所示。

本文進(jìn)行兩部分實(shí)驗(yàn)：

第一組實(shí)驗(yàn)為BATAGE與TAGE驗(yàn)證對(duì)比：按照上述440個(gè)測(cè)試程序劃分測(cè)試應(yīng)用場(chǎng)景進(jìn)行測(cè)試，驗(yàn)證BATAGE的MPKI力是否都比TAGE的MPKI值要低。

第二組實(shí)驗(yàn)為混合預(yù)測(cè)模型與最新主流分支預(yù)測(cè)模型進(jìn)行橫向比較：TAGE、TAGE-SC-L、BATAGE、multi-perceptron與混合模型進(jìn)行對(duì)比實(shí)驗(yàn)，將混合分支預(yù)測(cè)模型得到的總體MPKI和各種測(cè)試應(yīng)用場(chǎng)景的總體MPKI與這些主流分支預(yù)測(cè)模型進(jìn)行比較。

3.3 BATAGE與TAGE驗(yàn)證對(duì)比

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

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

3.4 仿真結(jié)果分析

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

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

從仿真實(shí)驗(yàn)結(jié)果可知：觀察總體MPKI和各種測(cè)試應(yīng)用場(chǎng)景的總體MPKI，混合預(yù)測(cè)模型的預(yù)測(cè)能力優(yōu)于最新主流的分支預(yù)測(cè)模型。這一改進(jìn)歸因于混合預(yù)測(cè)模型能夠融合兩種分支預(yù)測(cè)模型的優(yōu)勢(shì)，有效利用它們?cè)诓煌瑴y(cè)試應(yīng)用場(chǎng)景的優(yōu)勢(shì)，從考慮指令依賴性角度設(shè)計(jì)兩種不同的混合預(yù)測(cè)策略來提高條件分支指令預(yù)測(cè)的準(zhǔn)確性。

4 結(jié)束語

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

參考文獻(xiàn)：

［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］李正平，高楊.一種改進(jìn)型TAGE分支預(yù)測(cè)器的實(shí)現(xiàn)［J］.遼寧工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，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ìn)的神經(jīng)網(wǎng)絡(luò)分支預(yù)測(cè)技術(shù)［J］.微電子學(xué)與計(jì)算機(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

基金項(xiàng)目：國(guó)家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2021YFF0601200，2021YFF0601204）

作者簡(jiǎn)介：方昕宇（1996—），男，湖北黃岡人，碩士，CCF會(huì)員，主要研究方向?yàn)橛?jì)算機(jī)體系結(jié)構(gòu)；周日貴（1973—），男（通信作者），江西南昌人，教授，博導(dǎo)，博士，主要研究方向?yàn)橹悄苄畔⑻幚?、智能信息相關(guān)軟硬件系統(tǒng)的開發(fā)（rgzhou@shmtu.edu.cn）；龔鳴清（1994—），男，湖北黃岡人，碩士，主要研究方向?yàn)楦咝阅苡?jì)算.