基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)框架研究

陳 晨 陳志堅(jiān) 孟建熠 嚴(yán)曉浪

(浙江大學(xué)超大規(guī)模集成電路設(shè)計(jì)研究所 杭州 310027)

1 引言

隨著高端嵌入式應(yīng)用對(duì)處理器的性能要求越來(lái)越高，超深流水線、超標(biāo)量、多指令發(fā)射等技術(shù)紛紛應(yīng)用于高端嵌入式處理器設(shè)計(jì)中。高效準(zhǔn)確的分支預(yù)測(cè)框架是上述技術(shù)潛能得到發(fā)揮的前提和基礎(chǔ)[1]?；谏窠?jīng)網(wǎng)絡(luò)的分支預(yù)測(cè)方法[2,3]具有很高的分支預(yù)測(cè)精度，但神經(jīng)網(wǎng)絡(luò)算法復(fù)雜度高，資源消耗大，不適合于嵌入式應(yīng)用。當(dāng)前高端嵌入式應(yīng)用中廣泛采用的分支預(yù)測(cè)方法為二級(jí)自適應(yīng)分支預(yù)測(cè)方法[4]，該方法將分支指令地址和分支歷史信息進(jìn)行組合，從分支模式表中索引得到分支預(yù)測(cè)結(jié)果。分支模式表為每個(gè)動(dòng)態(tài)運(yùn)行的分支指令分配一個(gè)分支預(yù)測(cè)器[5]，預(yù)測(cè)器通過(guò)訓(xùn)練記錄對(duì)應(yīng)分支指令最近的分支跳轉(zhuǎn)信息，為分支指令再次執(zhí)行提供預(yù)測(cè)信息。

分支預(yù)測(cè)錯(cuò)誤的主要原因是破壞性分支重名[6,7]，因此很多研究將重點(diǎn)放在減小破壞性分支重名概率上。文獻(xiàn)[8]改變分支模式表中預(yù)測(cè)器的表征意義，表征的內(nèi)容由原本的分支跳轉(zhuǎn)方向改變?yōu)榉种D(zhuǎn)方向是否和分支目標(biāo)緩存器(BTB)中的偏置比特一致，該方法減小了破壞性分支重名概率，其缺點(diǎn)是需要結(jié)合BTB協(xié)同工作，設(shè)計(jì)復(fù)雜度高。文獻(xiàn)[9]將分支模式表分為一個(gè)跳轉(zhuǎn)型子表和一個(gè)非跳轉(zhuǎn)型子表，再增設(shè)一個(gè)選擇模式表來(lái)決定使用哪個(gè)子表的預(yù)測(cè)結(jié)果，該方法使每個(gè)子表中發(fā)生破壞性分支重名的概率降低，缺點(diǎn)是該方法基于兩次預(yù)測(cè)的疊加，一定程度上增加了預(yù)測(cè)不確定性。文獻(xiàn)[10,11]在TAGE分支預(yù)測(cè)方法[12]的基礎(chǔ)上增加輔助預(yù)測(cè)器，彌補(bǔ)主預(yù)測(cè)器針對(duì)特定應(yīng)用的不適應(yīng)性，解決了包括破壞性分支重名在內(nèi)的多種影響分支預(yù)測(cè)精度的因素，但該方法硬件資源耗費(fèi)很大。文獻(xiàn)[13]通過(guò)設(shè)立錯(cuò)誤分支表來(lái)記錄預(yù)測(cè)錯(cuò)誤分支指令的地址和間距，通過(guò)計(jì)數(shù)機(jī)制探測(cè)預(yù)測(cè)錯(cuò)誤分支指令并對(duì)其進(jìn)行糾正，從而消除分支預(yù)測(cè)錯(cuò)誤，但該方法同樣基于兩次預(yù)測(cè)的疊加，增加了預(yù)測(cè)不確定性。

本文結(jié)合程序局部性原理，從研究分支預(yù)測(cè)錯(cuò)誤的行為特征出發(fā)，針對(duì)分支預(yù)測(cè)錯(cuò)誤在時(shí)間上的局部性分布規(guī)律，提出一種通過(guò)動(dòng)態(tài)調(diào)整分支預(yù)測(cè)器預(yù)測(cè)內(nèi)容從而降低預(yù)測(cè)錯(cuò)誤率的分支預(yù)測(cè)方法。該方法對(duì)未經(jīng)極性變換的原始分支預(yù)測(cè)結(jié)果進(jìn)行采樣，并以分支預(yù)測(cè)錯(cuò)誤率50%為閾值進(jìn)行研究，定義原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率高于該閾值的局部時(shí)間段為預(yù)測(cè)錯(cuò)誤高峰期。動(dòng)態(tài)監(jiān)測(cè)預(yù)測(cè)錯(cuò)誤高峰期的出現(xiàn)，并實(shí)時(shí)變換預(yù)測(cè)錯(cuò)誤高峰期內(nèi)分支預(yù)測(cè)器的預(yù)測(cè)極性，即原本預(yù)測(cè)跳轉(zhuǎn)的變換為預(yù)測(cè)不跳轉(zhuǎn)，反之亦然。本文通過(guò)實(shí)時(shí)監(jiān)測(cè)預(yù)測(cè)錯(cuò)誤高峰期并動(dòng)態(tài)調(diào)整預(yù)測(cè)極性，降低了經(jīng)過(guò)極性變換的最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率，提高了分支預(yù)測(cè)的穩(wěn)定性與整體效率。

本文提出的方法與上述相關(guān)工作的區(qū)別在于：對(duì)比于文獻(xiàn)[8,9]，本文提出的方法不以減小破壞性分支重名的概率為目的，而是通過(guò)研究分支預(yù)測(cè)錯(cuò)誤本身的行為特征進(jìn)而提高分支預(yù)測(cè)精度，因而可以針對(duì)包括破壞性分支重名在內(nèi)的所有導(dǎo)致分支預(yù)測(cè)錯(cuò)誤的因素進(jìn)行優(yōu)化；對(duì)比于文獻(xiàn)[10,11]，本文提出的方法沒(méi)有采用輔助預(yù)測(cè)器，因而在硬件資源上具有更高的利用效率；對(duì)比于文獻(xiàn)[13]，本文通過(guò)動(dòng)態(tài)地監(jiān)測(cè)分支預(yù)測(cè)錯(cuò)誤率，采用自適應(yīng)的監(jiān)測(cè)機(jī)制探測(cè)預(yù)測(cè)錯(cuò)誤高峰期，因而具有更好的實(shí)時(shí)性。

2 分支預(yù)測(cè)錯(cuò)誤的時(shí)間局部性分析

根據(jù)程序局部性原理，一部分代碼會(huì)在短時(shí)間內(nèi)被反復(fù)執(zhí)行，這部分代碼稱為程序熱點(diǎn)。不同程序熱點(diǎn)的交替執(zhí)行占據(jù)了整個(gè)程序的大部分運(yùn)行時(shí)間。一旦程序熱點(diǎn)中存在破壞性分支重名等特殊的分支行為，則會(huì)導(dǎo)致程序在短時(shí)間內(nèi)集中出現(xiàn)大量分支預(yù)測(cè)錯(cuò)誤。本文以嵌入式測(cè)試基準(zhǔn)程序Powerstone[14]作為目標(biāo)程序?qū)Ψ种ьA(yù)測(cè)錯(cuò)誤行為進(jìn)行分析。表1是基準(zhǔn)程序的簡(jiǎn)單介紹。

采用二級(jí)自適應(yīng)分支預(yù)測(cè)方法對(duì)目標(biāo)程序進(jìn)行分支預(yù)測(cè)，分析程序運(yùn)行過(guò)程中分支預(yù)測(cè)錯(cuò)誤的行為特征。分支模式表共有213個(gè)分支預(yù)測(cè)器，以單個(gè)分支預(yù)測(cè)器為研究對(duì)象，分別對(duì)213個(gè)預(yù)測(cè)器進(jìn)行動(dòng)態(tài)監(jiān)測(cè)。對(duì)于每個(gè)預(yù)測(cè)器，選取時(shí)間上連續(xù)10次訪問(wèn)作為一個(gè)局部監(jiān)測(cè)時(shí)間段，實(shí)時(shí)統(tǒng)計(jì)該時(shí)間段內(nèi)的動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率；同時(shí)統(tǒng)計(jì)程序運(yùn)行結(jié)束后該預(yù)測(cè)器整體的靜態(tài)分支預(yù)測(cè)錯(cuò)誤率。為了保證有足夠的分支預(yù)測(cè)錯(cuò)誤次數(shù)以便分析其行為特征，將每個(gè)目標(biāo)程序運(yùn)行過(guò)程中發(fā)生分支預(yù)測(cè)錯(cuò)誤次數(shù)最多的預(yù)測(cè)器作為研究樣本，并選取各個(gè)樣本在程序運(yùn)行過(guò)程中發(fā)生分支預(yù)測(cè)錯(cuò)誤較多的一段時(shí)間進(jìn)行預(yù)測(cè)錯(cuò)誤行為分析。圖1是每個(gè)研究樣本在選取時(shí)間內(nèi)的分支預(yù)測(cè)錯(cuò)誤率，本文將圖中所示未經(jīng)極性變換的分支預(yù)測(cè)錯(cuò)誤率定義為原始分支預(yù)測(cè)錯(cuò)誤率(包括動(dòng)態(tài)和靜態(tài))，同時(shí)將原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率高于 50%(閾值)的時(shí)間段定義為預(yù)測(cè)錯(cuò)誤高峰期。從圖中可以看出各個(gè)目標(biāo)程序中研究樣本的動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率以靜態(tài)分支預(yù)測(cè)錯(cuò)誤率為界限上下抖動(dòng)，無(wú)論靜態(tài)分支預(yù)測(cè)錯(cuò)誤率高或低，都會(huì)多次出現(xiàn)動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率高于 50%(閾值)的時(shí)間段，即預(yù)測(cè)錯(cuò)誤高峰期。在圖中未顯示的其余大部分時(shí)間段中，分支預(yù)測(cè)錯(cuò)誤次數(shù)相對(duì)較少，也較少出現(xiàn)預(yù)測(cè)錯(cuò)誤高峰期。因此預(yù)測(cè)錯(cuò)誤高峰期具有集中出現(xiàn)的特點(diǎn)。

表1 Powerstone測(cè)試基準(zhǔn)程序簡(jiǎn)介

通過(guò)對(duì)比分析分支模式表中除研究樣本以外的其他分支預(yù)測(cè)器，發(fā)現(xiàn)上述預(yù)測(cè)器研究樣本的分支預(yù)測(cè)錯(cuò)誤行為具有普遍意義，表現(xiàn)為：對(duì)于各個(gè)預(yù)測(cè)器，在未經(jīng)極性變換的情況下，在程序運(yùn)行過(guò)程中動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率在時(shí)間上分布不均勻，并以靜態(tài)分支預(yù)測(cè)錯(cuò)誤率為界限抖動(dòng)，另外，無(wú)論該預(yù)測(cè)器靜態(tài)分支預(yù)測(cè)錯(cuò)誤率高或低，預(yù)測(cè)錯(cuò)誤高峰期都容易在一段時(shí)間內(nèi)集中出現(xiàn)。即分支預(yù)測(cè)錯(cuò)誤具有時(shí)間上的局部性。

3 預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)框架

圖1 分支預(yù)測(cè)錯(cuò)誤的時(shí)間局部性

根據(jù)分支預(yù)測(cè)錯(cuò)誤的時(shí)間局部性，本文提出一種基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)方法。本方法的核心思想是：對(duì)未經(jīng)極性變換的原始分支預(yù)測(cè)錯(cuò)誤率進(jìn)行自適應(yīng)監(jiān)測(cè)，篩選出程序運(yùn)行過(guò)程中原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率高于50%的預(yù)測(cè)錯(cuò)誤高峰期，將預(yù)測(cè)錯(cuò)誤高峰期內(nèi)的預(yù)測(cè)極性進(jìn)行變換，即原本預(yù)測(cè)跳轉(zhuǎn)的變換為預(yù)測(cè)不跳轉(zhuǎn)，反之亦然，使得經(jīng)過(guò)極性變換的最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率在程序運(yùn)行過(guò)程中始終保持在50%以下，減小最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率抖動(dòng)幅度，降低整體分支預(yù)測(cè)錯(cuò)誤率。

基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)方法中，最基本的硬件單元是預(yù)測(cè)錯(cuò)誤高峰期監(jiān)測(cè)器。預(yù)測(cè)錯(cuò)誤高峰期會(huì)根據(jù)具體應(yīng)用和輸入數(shù)據(jù)不同而動(dòng)態(tài)出現(xiàn)。本文通過(guò)自適應(yīng)的動(dòng)態(tài)監(jiān)測(cè)機(jī)制來(lái)判斷預(yù)測(cè)錯(cuò)誤高峰期，監(jiān)測(cè)器通過(guò)狀態(tài)機(jī)控制。一種狀態(tài)機(jī)的狀態(tài)轉(zhuǎn)換圖如圖2所示。圖中C(Correct)表示未經(jīng)極性變換的原始分支預(yù)測(cè)結(jié)果(即預(yù)測(cè)器自身)和正確分支跳轉(zhuǎn)結(jié)果一致，M(Mismatch)表示未經(jīng)極性變換的原始分支預(yù)測(cè)結(jié)果和正確分支跳轉(zhuǎn)結(jié)果不一致。初始狀態(tài)為IDLE，每當(dāng)確認(rèn)C發(fā)生后，直接越過(guò)相鄰狀態(tài)跳轉(zhuǎn)到下一個(gè)狀態(tài)，例如從 M4到M2，從M2到IDLE等；每當(dāng)確認(rèn)M發(fā)生后，跳轉(zhuǎn)到相鄰狀態(tài)，例如從C3到C2，從M1到M2等；程序運(yùn)行過(guò)程中，處于圖2虛線左側(cè)狀態(tài)(M3, M4)的時(shí)刻均為預(yù)測(cè)錯(cuò)誤高峰期。此狀態(tài)機(jī)的運(yùn)行方式加強(qiáng)了C發(fā)生的影響權(quán)重，這便于篩選出預(yù)測(cè)錯(cuò)誤率較高(例如 90%)的預(yù)測(cè)錯(cuò)誤高峰期。這樣的設(shè)計(jì)更利于整體性能的提高，因?yàn)閷?duì)于預(yù)測(cè)錯(cuò)誤率較低(例如 60%)的預(yù)測(cè)錯(cuò)誤高峰期，由于動(dòng)態(tài)監(jiān)測(cè)機(jī)制本身具有一定的誤差性，若強(qiáng)行對(duì)預(yù)測(cè)器進(jìn)行極性變換，往往達(dá)不到理想效果。

圖2 監(jiān)測(cè)器狀態(tài)轉(zhuǎn)換圖

基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)框架的一種實(shí)現(xiàn)如圖3所示，預(yù)測(cè)電路由分支模式表、監(jiān)測(cè)器表和數(shù)據(jù)選擇器組成。分支模式表由分支預(yù)測(cè)器構(gòu)成；監(jiān)測(cè)器表由圖2所示的狀態(tài)機(jī)構(gòu)成。分支歷史信息和分支指令地址進(jìn)行異或操作后得到索引值，從分支模式表中讀出一個(gè)分支預(yù)測(cè)器的值作為原始分支預(yù)測(cè)結(jié)果；同時(shí)用該索引值的一部分索引監(jiān)測(cè)器表，從中讀出一個(gè)狀態(tài)機(jī)的狀態(tài)作為數(shù)據(jù)選擇器的選通信號(hào)，根據(jù)該狀態(tài)決定最終分支預(yù)測(cè)結(jié)果：若狀態(tài)顯示處于預(yù)測(cè)錯(cuò)誤高峰期，則將原始分支預(yù)測(cè)結(jié)果的極性變換后作為最終分支預(yù)測(cè)結(jié)果，反之則直接將原始分支預(yù)測(cè)結(jié)果作為最終分支預(yù)測(cè)結(jié)果。

監(jiān)測(cè)器表中的狀態(tài)機(jī)在分支預(yù)測(cè)信息被后級(jí)流水線確認(rèn)后被更新，每次僅更新被確認(rèn)分支指令所對(duì)應(yīng)的狀態(tài)機(jī)，根據(jù)原始分支預(yù)測(cè)結(jié)果是否與正確分支跳轉(zhuǎn)結(jié)果一致對(duì)狀態(tài)進(jìn)行轉(zhuǎn)換，狀態(tài)轉(zhuǎn)換方式如圖2所示。分支模式表中的預(yù)測(cè)器僅當(dāng)其輸出的原始分支預(yù)測(cè)結(jié)果與正確分支跳轉(zhuǎn)結(jié)果不一致時(shí)被更新為正確分支跳轉(zhuǎn)結(jié)果。

圖3 基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)框架結(jié)構(gòu)

基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)方法按照監(jiān)測(cè)方式不同可以分為：全局監(jiān)測(cè)(GM)，按組監(jiān)測(cè)(SM)和局部監(jiān)測(cè)(PM)3種類型。各種類型的結(jié)構(gòu)如圖4所示。對(duì)于全局監(jiān)測(cè)，整個(gè)分支模式表對(duì)應(yīng)一個(gè)監(jiān)測(cè)器，該監(jiān)測(cè)器負(fù)責(zé)篩選出全局的預(yù)測(cè)錯(cuò)誤高峰期。對(duì)于局部監(jiān)測(cè)，分支模式表中每個(gè)預(yù)測(cè)器都對(duì)應(yīng)一個(gè)監(jiān)測(cè)器，各監(jiān)測(cè)器負(fù)責(zé)篩選出對(duì)應(yīng)于各預(yù)測(cè)器的預(yù)測(cè)錯(cuò)誤高峰期。全局監(jiān)測(cè)的監(jiān)測(cè)粒度較粗，對(duì)預(yù)測(cè)錯(cuò)誤高峰期的探測(cè)靈敏度低，但只需要一個(gè)監(jiān)測(cè)器，硬件資源耗費(fèi)極小，而局部監(jiān)測(cè)的監(jiān)測(cè)粒度更細(xì)，對(duì)預(yù)測(cè)錯(cuò)誤高峰期的探測(cè)靈敏度更高，但監(jiān)測(cè)器的數(shù)量需要和預(yù)測(cè)器一致，硬件資源耗費(fèi)很大。按組監(jiān)測(cè)是上述兩種方式的折中，將分支模式表分為若干組，每組對(duì)應(yīng)一個(gè)監(jiān)測(cè)器，負(fù)責(zé)篩選出該組預(yù)測(cè)器對(duì)應(yīng)的預(yù)測(cè)錯(cuò)誤高峰期。此方式在監(jiān)測(cè)靈敏度和硬件資源上相對(duì)比較平衡。

圖4 3種監(jiān)測(cè)方式結(jié)構(gòu)

4 實(shí)驗(yàn)結(jié)果

本文以國(guó)產(chǎn)32位高性能嵌入式處理器CK610[15]及其平臺(tái)為基礎(chǔ)，分別實(shí)現(xiàn)本文提出的基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)方法和現(xiàn)有的 Gshare以及Bi-Mode分支預(yù)測(cè)方法，以Powerstone測(cè)試基準(zhǔn)程序作為目標(biāo)程序。先分析預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法自身幾種監(jiān)測(cè)方式的適用性，然后分析使用該方法后最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率的下降情況，最后給出該方法與Gshare以及Bi-Mode分支預(yù)測(cè)方法的綜合預(yù)測(cè)錯(cuò)誤率比較結(jié)果。

首先對(duì)預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法自身的幾種監(jiān)測(cè)方式進(jìn)行比較，圖5表示3種監(jiān)測(cè)方式在各種硬件資源配置下對(duì)于目標(biāo)程序的平均預(yù)測(cè)錯(cuò)誤率。當(dāng)硬件資源很小時(shí)(對(duì)應(yīng)于圖5中小于4 kbit)，全局監(jiān)測(cè)最優(yōu)；當(dāng)硬件資源增加后(對(duì)應(yīng)于圖5，在8 ～256 kbit之間)，按組監(jiān)測(cè)最優(yōu)；而當(dāng)硬件資源進(jìn)一步增加(對(duì)應(yīng)于圖5中大于256 kbit)，局部監(jiān)測(cè)最優(yōu)。其原因在于，對(duì)于不同的監(jiān)測(cè)方式，監(jiān)測(cè)器所消耗的資源不同，因此分配到分支模式表上的資源也不同。當(dāng)硬件資源很小，分支模式表的容量問(wèn)題成為影響分支預(yù)測(cè)精度的最主要因素，全局監(jiān)測(cè)可用于分支模式表的硬件資源最多，因此可獲得相對(duì)較好的分支預(yù)測(cè)結(jié)果；隨著硬件資源的增加，分支模式表的容量問(wèn)題得到緩解，但對(duì)于局部監(jiān)測(cè)來(lái)說(shuō)，每個(gè)預(yù)測(cè)器都需要一個(gè)對(duì)應(yīng)的監(jiān)測(cè)器，可用于分支模式表的硬件資源仍然有限，而按組監(jiān)測(cè)則在分支模式表和監(jiān)測(cè)器的硬件資源分配上取得了較好的平衡，因此可獲得最好的分支預(yù)測(cè)結(jié)果；當(dāng)硬件資源繼續(xù)增加達(dá)到一定程度后，分支模式表的容量對(duì)分支預(yù)測(cè)精度的影響進(jìn)一步減小，具有最高監(jiān)測(cè)靈敏度的局部監(jiān)測(cè)方式將獲得最好的分支預(yù)測(cè)結(jié)果?，F(xiàn)階段嵌入式處理器中分支預(yù)測(cè)可接受的硬件資源約在64 kbit以內(nèi)，從圖5中可以看出按組監(jiān)測(cè)方式在此區(qū)間內(nèi)是最優(yōu)的。

為了檢驗(yàn)經(jīng)過(guò)極性變換的最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率低于未經(jīng)極性變換的原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率，采用預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法對(duì)第2節(jié)所研究的分支預(yù)測(cè)錯(cuò)誤率重新進(jìn)行監(jiān)測(cè)，研究樣本和監(jiān)測(cè)時(shí)間段均和圖1保持一致，局部監(jiān)測(cè)時(shí)間段也和圖1保持一致，即選取時(shí)間上連續(xù)10次訪問(wèn)作為一個(gè)局部監(jiān)測(cè)時(shí)間段。采用按組監(jiān)測(cè)方式，分支模式表包含 213個(gè)分支預(yù)測(cè)器，使用 29個(gè)監(jiān)測(cè)器，監(jiān)測(cè)器狀態(tài)轉(zhuǎn)換采用圖2所示方式。圖6顯示了各目標(biāo)程序中原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率和最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率的比較情況，可以看出，通過(guò)極性變換，最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率在整體上明顯低于原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率。

圖5 3種監(jiān)測(cè)方式預(yù)測(cè)錯(cuò)誤率比較

圖6 最終動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率下降情況

圖7 預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法和其他分支預(yù)測(cè)方法的預(yù)測(cè)錯(cuò)誤率比較

圖7顯示了預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法與Gshare以及 Bi-Mode分支預(yù)測(cè)方法在各目標(biāo)程序中分支預(yù)測(cè)錯(cuò)誤率的比較情況。預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法采用按組監(jiān)測(cè)方式，當(dāng)硬件資源小于1 kbyte時(shí)，分支模式表占用7/8的硬件資源，監(jiān)測(cè)器表占用1/8的硬件資源；當(dāng)硬件資源大于1 kbyte時(shí)，分支模式表占用3/4的硬件資源，監(jiān)測(cè)器表占用1/4的硬件資源。監(jiān)測(cè)器狀態(tài)轉(zhuǎn)換采用圖2所示方式。從圖中可以看出，對(duì)于大部分目標(biāo)程序，預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法均優(yōu)于 Gshare和Bi-Mode分支預(yù)測(cè)方法，只有 ucbqsort程序中，Bi-Mode分支預(yù)測(cè)方法在特定硬件資源下產(chǎn)生最優(yōu)的預(yù)測(cè)精度。另外，預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法的預(yù)測(cè)精度優(yōu)勢(shì)會(huì)在一定區(qū)間內(nèi)達(dá)到最大值，但隨著硬件資源的增加，精度優(yōu)勢(shì)會(huì)逐漸減弱，對(duì)于adcpm, des這兩個(gè)目標(biāo)程序來(lái)說(shuō)，當(dāng)達(dá)到一定硬件資源時(shí)，3種分支預(yù)測(cè)方法的預(yù)測(cè)精度基本一致。其原因是，預(yù)測(cè)極性動(dòng)態(tài)變換分支預(yù)測(cè)方法是以篩選出預(yù)測(cè)錯(cuò)誤高峰期為基礎(chǔ)的，隨著硬件資源增加，未經(jīng)極性變換的原始分支預(yù)測(cè)錯(cuò)誤率自身便會(huì)達(dá)到很低的水平，從而使得程序運(yùn)行過(guò)程中出現(xiàn)的預(yù)測(cè)錯(cuò)誤高峰期數(shù)量減少，各個(gè)預(yù)測(cè)錯(cuò)誤高峰期自身的預(yù)測(cè)錯(cuò)誤率也會(huì)降低，這給預(yù)測(cè)極性動(dòng)態(tài)變換帶來(lái)了困難。這也解釋了為何ucbqsort程序中Bi-Mode分支預(yù)測(cè)方法產(chǎn)生最優(yōu)的預(yù)測(cè)精度，因?yàn)樵摮绦蛭唇?jīng)極性變換的原始分支預(yù)測(cè)錯(cuò)誤率已經(jīng)很低。

5 結(jié)束語(yǔ)

本文通過(guò)研究程序運(yùn)行過(guò)程中分支預(yù)測(cè)錯(cuò)誤的行為特點(diǎn)，提出一種基于預(yù)測(cè)極性動(dòng)態(tài)變換的分支預(yù)測(cè)方法。該方法監(jiān)測(cè)未經(jīng)極性變換的原始動(dòng)態(tài)分支預(yù)測(cè)錯(cuò)誤率，篩選出程序運(yùn)行過(guò)程中的預(yù)測(cè)錯(cuò)誤高峰期，將高峰期內(nèi)預(yù)測(cè)器的預(yù)測(cè)極性進(jìn)行變換后作為最終分支預(yù)測(cè)結(jié)果，從而降低經(jīng)過(guò)極性變換的最終分支預(yù)測(cè)錯(cuò)誤率。根據(jù)預(yù)測(cè)錯(cuò)誤率監(jiān)測(cè)方式不同可進(jìn)一步分為全局監(jiān)測(cè)、按組監(jiān)測(cè)和局部監(jiān)測(cè) 3種類型，在分支預(yù)測(cè)精度和硬件成本之間取得平衡。該方法可以滿足高性能嵌入式處理器在可控成本內(nèi)實(shí)現(xiàn)高精度分支預(yù)測(cè)的要求。

[1] Hennessy J and Patterson D. Computer Architecture: A Quantitative Approach[M]. Fifth Edition, Beijing: China Machine Press, 2012: 162-167.

[2] Jiménez D. An optimized scaled neural branch predictor[C].2011 IEEE 29th International Conference on Computer Design (ICCD), Amherst, 2011: 113-118.

[3] Jiménez D. Oh-snap: optimized hybrid scaled neural analog predictor[C]. Proceedings of the 3rd Championship on Branch Prediction, Detroit, 2011: 9-12.

[4] Yeh T and Patt Y. Two-level adaptive training branch prediction[C]. Proceedings of the 24th Annual International Symposium on Microarchitecture, New York, 1991: 51-61.

[5] Zhang Long, Tao Fang, and Xiang Jin-feng. Researches on design and implementations of two 2-bit predictors[J].Advanced Engineering Forum, 2011, 1(1): 241-246.

[6] Young C, Gloy N, and Smith M. A comparative analysis of schemes for correlated branch prediction[C]. Proceedings of the 22nd Annual International Symposium on Computer Architecture, New York, 1995: 276-286.

[7] Talcott A, Nemirovsky M, and Wood R. The influence of branch prediction table interference on branch prediction scheme performance[C]. Proceedings of the 3rd Annual International Conference on Parallel Architectures and Compilation Techniques, Manchester, 1995: 89-98.

[8] Sprangle E, Chappell R, Alsup M,et al.. The agree predictor:a mechanism for reducing negative branch history interference[C]. Proceedings of the 24th Annual International Symposium on Computer Architecture, New York, 1997:284-291.

[9] Lee C, Chen I, and Mudge T. The bi-mode branch predictor[C]. 30th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO,97), Research Triangle Park, NC,1997: 4-13.

[10] Seznec A. A 64 kbytes ISL-TAGE branch predictor[C].Proceedings of the 3rd Championship Branch Prediction,Detroit, 2011: 13-16.

[11] Seznec A. A new case for the TAGE branch predictor [C].Proceedings of the 44th Annual IEEE/ACM International Symposium on Microarchitecture, New York, 2011: 117-127.

[12] Seznec A and Michaud P. A case for (partially)-tagged geometric history length predictors[J].Journal of Instruction Level Parallelism, 2006, 8(1): 1-23.

[13] Sendag R, Yi J, and Chuang Peng-fei. Branch misprediction prediction: complementary branch predictors[J].Computer Architecture Letters, 2007, 6(2): 49-52.

[14] Scott J, Lea H, Arends J,et al.. Designing the low-power M*CoreTM architecture[C]. Proceedings of IEEE Power Driven Microarchitecture Workshop, Barcelona, 1998:145-150.

[15] Meng Jian-yi. C-SKY microsystems, 32-bit high performance and low power embedded processor[OL]. http://www.c-sky.com, 2012, 5.