李正平，高 楊

一種改進(jìn)型TAGE分支預(yù)測(cè)器的實(shí)現(xiàn)

李正平，高 楊

（安徽大學(xué) 電子信息工程學(xué)院，安徽 合肥 230031）

針對(duì)傳統(tǒng)的TAGE分支預(yù)測(cè)器存在分支別名沖突以及對(duì)與歷史不相關(guān)的分支預(yù)測(cè)準(zhǔn)確率較低兩個(gè)問(wèn)題，提出了基于PC特征提取和提升基礎(chǔ)預(yù)測(cè)表優(yōu)先級(jí)的方式對(duì)預(yù)測(cè)器進(jìn)行改進(jìn)。將傳統(tǒng)的TAGE分支預(yù)測(cè)器與本文改進(jìn)的預(yù)測(cè)器共同使用SPEC2000的測(cè)試程序進(jìn)行驗(yàn)證。實(shí)驗(yàn)結(jié)果表明，改進(jìn)之后的分支預(yù)測(cè)器能夠有效地解決這兩個(gè)問(wèn)題，預(yù)測(cè)準(zhǔn)確率有著明顯的提升。

分支預(yù)測(cè)；處理器性能；特征提??；卷積核

現(xiàn)代處理器大都采用超流水、超標(biāo)量的設(shè)計(jì)結(jié)構(gòu)，分支預(yù)測(cè)技術(shù)是兩者的關(guān)鍵支撐技術(shù)[1]。為了提升處理器的主頻，設(shè)計(jì)者不得不增加流水線的級(jí)數(shù)，細(xì)化處理器的工作。然而，隨著流水線的級(jí)數(shù)增加，如果分支預(yù)測(cè)失敗使得清空流水線的代價(jià)就會(huì)越大[2]。處理器超標(biāo)量的設(shè)計(jì)使得指令并行性執(zhí)行成為了可能，極大地提高了處理器的性能。研究表明，在一般程序中平均8~10條匯編指令就有一條轉(zhuǎn)移指令，也就是說(shuō)在8發(fā)射結(jié)構(gòu)當(dāng)中每一拍都會(huì)出現(xiàn)1條分支指令。如果沒(méi)有分支預(yù)測(cè)，處理器每取一次指令，就會(huì)阻塞，直到分支指令執(zhí)行完畢。多發(fā)射結(jié)構(gòu)越復(fù)雜，阻塞的周期就會(huì)越長(zhǎng)，導(dǎo)致處理器的性能降低。因此，分支預(yù)測(cè)技術(shù)對(duì)于減少清空流水線代價(jià)，挖掘處理器多發(fā)射結(jié)構(gòu)的潛在能力，進(jìn)而提升處理器性能發(fā)揮著至關(guān)重要的作用。

TAGE分支預(yù)測(cè)器和之前的預(yù)測(cè)器相比做了很大的改進(jìn)，之前的預(yù)測(cè)器將所有的分支共同使用同一個(gè)表進(jìn)行預(yù)測(cè)[3]。TAGE分支預(yù)測(cè)器將分支分成兩類(lèi)，與歷史相關(guān)的分支和與歷史不相關(guān)的分支，分別使用基礎(chǔ)預(yù)測(cè)表和標(biāo)記預(yù)測(cè)表進(jìn)行預(yù)測(cè)，這使得分支預(yù)測(cè)準(zhǔn)確率有著顯著的提高。

近些年來(lái)，人們對(duì)TAGE分支預(yù)測(cè)器進(jìn)行不斷的改進(jìn)。改進(jìn)的角度主要從預(yù)測(cè)準(zhǔn)確率、面積、功耗3個(gè)方向出發(fā)。文獻(xiàn)[4]通過(guò)對(duì)歷史寄存器位進(jìn)行排列，降低了索引值和標(biāo)記值的運(yùn)算次數(shù)，節(jié)省了硬件資源，功耗和面積分別降低了90%和85%。文獻(xiàn)[5]使用單端口存儲(chǔ)器組件減少預(yù)測(cè)器的訪問(wèn)次數(shù)，在文獻(xiàn)[4]的基礎(chǔ)上進(jìn)一步降低功耗。關(guān)于提升分支預(yù)測(cè)器的準(zhǔn)確率，人們大都是將TAGE預(yù)測(cè)器與其他的專(zhuān)用預(yù)測(cè)器聯(lián)合使用。例如文獻(xiàn)[6]通過(guò)將TAGE預(yù)測(cè)器與循環(huán)分支預(yù)測(cè)器聯(lián)合使用，文獻(xiàn)[7]將TAGE預(yù)測(cè)器與統(tǒng)計(jì)校正預(yù)測(cè)器聯(lián)合使用，都取得了很好的效果。文獻(xiàn)[8]對(duì)歷史寄存器進(jìn)行壓縮，使得可以記錄更久的歷史信息，提高與歷史相關(guān)分支的預(yù)測(cè)準(zhǔn)確率。

TAGE預(yù)測(cè)器標(biāo)記預(yù)測(cè)表優(yōu)先級(jí)比基礎(chǔ)預(yù)測(cè)表更高，導(dǎo)致與歷史不相關(guān)的分支預(yù)測(cè)準(zhǔn)確率較低；并且使用程序計(jì)數(shù)器(PC)的部分位索引預(yù)測(cè)表，分支別名問(wèn)題比較突出。針對(duì)TAGE分支預(yù)測(cè)器存在的這兩個(gè)問(wèn)題，對(duì)分支預(yù)測(cè)器的結(jié)構(gòu)進(jìn)行改進(jìn)，改進(jìn)之后的方法使得預(yù)測(cè)器的預(yù)測(cè)準(zhǔn)確率明顯提高。

1 傳統(tǒng)型TAGE分支預(yù)測(cè)器

1.1 傳統(tǒng)型TAGE分支預(yù)測(cè)器算法原理

TAGE分支預(yù)測(cè)器結(jié)構(gòu)圖如圖1所示。分支預(yù)測(cè)器共包含5張預(yù)測(cè)表和1個(gè)歷史寄存器，分別用T0、T1、T2、T3、T4、h表示。當(dāng)分支指令進(jìn)入預(yù)測(cè)器之后，就會(huì)得到5張表的預(yù)測(cè)結(jié)果，然后根據(jù)5張表的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的結(jié)果值作為本次的最終預(yù)測(cè)結(jié)果。其中，T0稱(chēng)為基礎(chǔ)預(yù)測(cè)表，作用是預(yù)測(cè)與歷史不相關(guān)的分支，T1~T4稱(chēng)為標(biāo)記預(yù)測(cè)表，作用是預(yù)測(cè)與歷史相關(guān)的分支?；A(chǔ)預(yù)測(cè)表的每一行是由2位飽和計(jì)數(shù)器組成，如圖2(a)所示。當(dāng)計(jì)數(shù)器的最高位是1時(shí)，預(yù)測(cè)分支指令發(fā)生，當(dāng)最高位是0時(shí)，預(yù)測(cè)指令不發(fā)生。標(biāo)記預(yù)測(cè)表的每一行由3個(gè)部分組成，分別是標(biāo)志位(tag)、飽和計(jì)數(shù)器(ctr)、置信度(u)，如圖2(b)所示。

圖1 TAGE分支預(yù)測(cè)器

圖2 預(yù)測(cè)表行組成

分支預(yù)測(cè)步驟：

(1)每一條分支指令對(duì)應(yīng)一個(gè)程序計(jì)數(shù)器值。首先將程序計(jì)數(shù)器(PC)的部分位索引T0表，得到兩位飽和計(jì)數(shù)器的值。

(2)將歷史寄存器h分成4等分。將程序計(jì)數(shù)器(PC)部分位分別與歷史寄存器的1/4長(zhǎng)度位寬、2/4長(zhǎng)度位寬、3/4長(zhǎng)度位寬、4/4長(zhǎng)度位寬進(jìn)行兩次不同的哈希計(jì)算，得到8個(gè)結(jié)果值，作為4張表的索引值和標(biāo)記值。

(3)利用索引值選取T1、T2、T3、T4 4張表對(duì)應(yīng)的行，取出對(duì)應(yīng)行的tag位與步驟(2)標(biāo)記值進(jìn)行比較。如果相等，則取出對(duì)應(yīng)行的ctr。否則，忽略該表的預(yù)測(cè)值。

(4)根據(jù)步驟(2)和(3)得到不止一個(gè)預(yù)測(cè)值。預(yù)測(cè)值優(yōu)先級(jí)次序?yàn)門(mén)4>T3>T2>T1>T0，根據(jù)優(yōu)先級(jí)選出最終的預(yù)測(cè)值。

1.2 算法缺陷

TAGE分支預(yù)測(cè)器將歷史寄存器進(jìn)行折疊，能夠區(qū)分不同歷史長(zhǎng)度的分支；并且預(yù)測(cè)器增加了標(biāo)志位，能夠在一定程度上降低分支別名的干擾。但是存在兩個(gè)較為明顯的缺陷：

(1)使用程序計(jì)數(shù)器(PC)的部分位運(yùn)算得到預(yù)測(cè)表的索引值和標(biāo)記值，這使得不同的分支索引到同一項(xiàng)的概率依然很大，分支別名的問(wèn)題并沒(méi)有從根本上得到解決。

(2)基礎(chǔ)預(yù)測(cè)表優(yōu)先級(jí)最低，分支預(yù)測(cè)器預(yù)測(cè)的最終值大多來(lái)自于標(biāo)記預(yù)測(cè)表，這使得對(duì)與歷史不相關(guān)的分支預(yù)測(cè)準(zhǔn)確率不高。

針對(duì)第一個(gè)缺陷，對(duì)程序計(jì)數(shù)器(PC)進(jìn)行特征提取，使用特征提取值代替程序計(jì)數(shù)器(PC)的部分位，這樣一來(lái)，特征值能夠充分反映整個(gè)程序計(jì)數(shù)器(PC)的信息，能夠和其他的程序計(jì)數(shù)器(PC)值區(qū)分開(kāi)來(lái)。針對(duì)第二個(gè)缺陷，可以提升基礎(chǔ)預(yù)測(cè)表的優(yōu)先級(jí)，使得基礎(chǔ)預(yù)測(cè)表與標(biāo)記預(yù)測(cè)表有著相同的優(yōu)先級(jí)。

2 改進(jìn)型TAGE分支預(yù)測(cè)器

2.1 PC特征提取

本文以64位處理器為例，PC的地址可以使用16個(gè)十六進(jìn)制數(shù)表示，將這16個(gè)數(shù)組成4*4的正方形，如下圖3(a)所示。PC的特征提取采用經(jīng)典的sobel算法使用的兩個(gè)卷積核。使用Sobel算法[9-11]的兩個(gè)卷積核可以提取每一個(gè)點(diǎn)在水平方向和垂直方向的一階倒數(shù)，然后使用移位的方式將兩個(gè)方向的倒數(shù)合并在一起組成PC的特征值。垂直方向的卷積核如圖3(b)所示，水平方向的卷積核如圖3(c)所示。

圖3 特征提取圖

具體的計(jì)算步驟：

(1)使用垂直窗口在圖1(a)上進(jìn)行滑動(dòng)，得到4個(gè)值，分別用0、1、2、3表示。這4個(gè)值都是4位的二進(jìn)制。

其中：

(2)使用水平窗口在圖1（a）上進(jìn)行滑動(dòng)，得到4個(gè)值，分別用0、1、2、3表示。這4個(gè)值也是4位的二進(jìn)制數(shù)。

其中：

(3)特征提取的最終結(jié)果用字母表示，是8位的。其中，的高4位由垂直方向得到的4個(gè)值進(jìn)行異或得到，低4位由水平方向得到的4個(gè)值進(jìn)行異或得到。

2.2 改進(jìn)型TAGE分支預(yù)測(cè)器結(jié)構(gòu)

改進(jìn)型TAGE分支預(yù)測(cè)器的結(jié)構(gòu)如圖4所示。為了解決第一個(gè)缺陷，增加了fe模塊，該模塊的作用是對(duì)程序計(jì)數(shù)器進(jìn)行特征提取，用特征值參與運(yùn)算，得到索引值和標(biāo)記值。為了解決第二個(gè)缺陷，將基礎(chǔ)預(yù)測(cè)表每一個(gè)行增加3個(gè)部分，分別是歷史發(fā)生統(tǒng)計(jì)值(taken cnt)，歷史不發(fā)生統(tǒng)計(jì)值(n_taken cnt)，置信度(u)，如圖5所示。其中，歷史發(fā)生統(tǒng)計(jì)值用于計(jì)數(shù)該分支歷史發(fā)生的次數(shù)，歷史不發(fā)生統(tǒng)計(jì)值用于計(jì)數(shù)該分支歷史不發(fā)生的次數(shù)，置信度用于統(tǒng)計(jì)發(fā)生次數(shù)的百分比。置信度是一個(gè)很重要的因素，它將決定分支預(yù)測(cè)器的最終預(yù)測(cè)值是來(lái)自于標(biāo)記預(yù)測(cè)器還是基礎(chǔ)預(yù)測(cè)器。為了增加基礎(chǔ)預(yù)測(cè)表優(yōu)先級(jí)，需要添加三態(tài)門(mén)，用于篩選標(biāo)記預(yù)測(cè)表T1的預(yù)測(cè)值。

圖4 改進(jìn)型TAGE分支預(yù)測(cè)器

ctrtake_cntn_taken_cntu

改進(jìn)型預(yù)測(cè)器預(yù)測(cè)步驟：

(1)對(duì)程序計(jì)數(shù)器進(jìn)行特征提取，得到特征值。

(2)將歷史寄存器h分成4等分。將特征值分別與歷史寄存器的1/4長(zhǎng)度位寬、2/4長(zhǎng)度位寬、3/4長(zhǎng)度位寬、4/4長(zhǎng)度位寬進(jìn)行2次不同的哈希計(jì)算，得到8個(gè)結(jié)果值，作為4張表的索引值和標(biāo)記值。

(3)利用索引值選取T1、T2、T3、T44張表對(duì)應(yīng)的行，取出對(duì)應(yīng)行的tag位與步驟2標(biāo)記值進(jìn)行比較。如果相等，則取出對(duì)應(yīng)行的ctr和u。否則，忽略該表的預(yù)測(cè)值。

(4)根據(jù)預(yù)測(cè)表的優(yōu)先級(jí)T4>T3>T2>T1，從標(biāo)記預(yù)測(cè)表選擇優(yōu)先級(jí)最高的ctr和u。

(5)從基礎(chǔ)預(yù)測(cè)表T0得到ctr和u。

(6)比較置信度。如果基礎(chǔ)預(yù)測(cè)表的置信度(u)大于標(biāo)記預(yù)測(cè)表的置信度，則取基礎(chǔ)預(yù)測(cè)表的預(yù)測(cè)值(ctr)作為最終的預(yù)測(cè)值，否則取標(biāo)記預(yù)測(cè)表的預(yù)測(cè)值(ctr)作為最終的預(yù)測(cè)值。

3 性能評(píng)估

本文對(duì)TAGE預(yù)測(cè)器結(jié)構(gòu)進(jìn)行優(yōu)化。為了測(cè)試改進(jìn)型TAGE分支預(yù)測(cè)器的效果，使用spec2000的部分子程序進(jìn)行測(cè)試，將測(cè)試結(jié)果與文獻(xiàn)[12]進(jìn)行對(duì)比，對(duì)比的結(jié)果如圖6所示。由表中的數(shù)據(jù)可知，改進(jìn)型的分支預(yù)測(cè)器預(yù)測(cè)準(zhǔn)確度有著明顯的上升。其中，編號(hào)為175.1的子測(cè)試程序主要用來(lái)測(cè)試與歷史不相關(guān)的分支，準(zhǔn)確度從之前的88.5%上升到現(xiàn)在的92.45%，準(zhǔn)確率足足提升了3.95%。編號(hào)為164, 181, 252.3, 300的4個(gè)子測(cè)試程序準(zhǔn)確度也有著相應(yīng)的提升。使用PC特征提取的值索引預(yù)測(cè)表能夠降低分支別名干擾的問(wèn)題，提升基礎(chǔ)預(yù)測(cè)表的優(yōu)先級(jí)能夠提高預(yù)測(cè)與歷史不相關(guān)分支的準(zhǔn)確率。

圖6 使用spec2000部分子程序測(cè)試對(duì)比圖

表1 資源消耗以及功耗對(duì)比

由表1可知，芯片的資源僅僅增加了4.8%，功耗增加了不足1%。以增加較小的芯片面積和功耗換取分支器的準(zhǔn)確率是非常值得的。

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

通過(guò)對(duì)TAGE分支預(yù)測(cè)器的結(jié)構(gòu)進(jìn)行探究，發(fā)現(xiàn)預(yù)測(cè)器存在兩個(gè)缺陷，并對(duì)預(yù)測(cè)器結(jié)構(gòu)進(jìn)行針對(duì)性改進(jìn)，提出PC特征提取和提升基礎(chǔ)預(yù)測(cè)表的優(yōu)先級(jí)的方式。和傳統(tǒng)的TAGE分支預(yù)測(cè)器相比，改進(jìn)型的預(yù)測(cè)器準(zhǔn)確率有著顯著的提高。分支預(yù)測(cè)器的預(yù)測(cè)準(zhǔn)確率是影響處理器性能的關(guān)鍵因素，是處理器設(shè)計(jì)的重中之重，因此，這種提升預(yù)測(cè)器準(zhǔn)確率的方式顯得尤為重要。

[1] 肖建青, 沈緒榜, 李偉, 等. 一種組合延遲槽和預(yù)譯碼技術(shù)的新型分支預(yù)測(cè)器[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2015, 36(4): 820-825.

[2]茍鵬飛, 喻明艷, 楊兵, 等. 基于類(lèi)型預(yù)測(cè)的甚塊預(yù)測(cè)器[J]. 計(jì)算機(jī)學(xué)報(bào), 2012, 35(7): 1539-1552.

[3]Sprangle E, Chappell R S, Alsup M, et al. The agree predictor: a mechanism for reducing negative branch history interference[J]. Acm Sigarch Computer Architecture News, 1997, 25(2): 284-291.

[4] Schlais D J, Lipasti M H. BADGR: A practical GHR implementation for TAGE branch predictors[C]. 2016 IEEE 34th International Conference on Computer Design (ICCD), Scottsdale, AZ, 2016:. 536-543.

[5]Chatzidimitriou A, Papadimitriou G, Gizopoulos D, et al. Analysis and Characterization of Ultra Low Power Branch Predictors[C]. 2018 IEEE 36th International Conference on Computer Design (ICCD). IEEE, 2018.

[6]Seznec A, Miguel J S, Albericio J. The Inner Most Loop Iteration counter: a New Dimension in Branch History[J]. IEEE Micro, 2016, 36(3): 1.

[7]Seznec. A new case for the TAGE branch predictor[C]. 2011 44th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO), Porto Alegre, 2011: 117-127.

[8]Gope D, Lipasti M H. Bias-Free Branch Predictor[C]. IEEE/ACM International Symposium on Microarchitecture, 2015.

[9] Xiangxi Z, Yonghui Z, Shuaiyan Z, et al. FPGA implementation of edge detection for Sobel operator in eight directions[C].Chengdu, 2018: 520-523.

[10] Yusoff N M, Abdul Halim I S, Abdullah N E, et al. Real-time Hevea Leaves Diseases Identification using Sobel Edge Algorithm on FPGA: A Preliminary Study[C].Shah Alam, Malaysia, 2018: 168-171.

[11] Israni S, Jain S. Edge detection of license plate using Sobel operator,[C].Chennai, 2016: 3561-3563.

[12] Maa Y C, Yen M H, Wang Y T. Evaluating and improving variable length history branch predictors[C]. Computer Symposium. IEEE, 2010.

Implementation of Improved TAGE Branch Predictor

LI Zheng-ping, GAO Yang

（School of Electronics and Information Engineering, Anhui University, hefei 230031, China）

In this paper, the traditional TAGE branch predictor has two problems of branch alias conflict and low prediction accuracy for branches that are not related to history. The proposed method is improved based on PC feature extraction and the priority of the basic prediction table. The traditional TAGE branch predictor is used in conjunction with the improved predictor to verify the SPEC2000 test procedure. The experimental results show that the improved prediction accuracy of the branch predictor is obviously improved.

branch prediction; processor performance; feature extraction; convolution kernel

TP302.1

A

1674-3261(2020)01-0001-04

10.15916/j.issn1674-3261.2020.01.001

2019-11-01

國(guó)家自然科學(xué)基金項(xiàng)目(61474001)

李正平(1979-)，男，安徽宣城人，教授，博士。

優(yōu)先出版地址：http://kns.cnki.net/kcms/detail/21.1567.T.20191230.0916.002.html

責(zé)任編校：孫 林