李正平，高 楊

一種改進型TAGE分支預測器的實現(xiàn)

李正平，高 楊

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

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

分支預測；處理器性能；特征提取；卷積核

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

TAGE分支預測器和之前的預測器相比做了很大的改進，之前的預測器將所有的分支共同使用同一個表進行預測[3]。TAGE分支預測器將分支分成兩類，與歷史相關的分支和與歷史不相關的分支，分別使用基礎預測表和標記預測表進行預測，這使得分支預測準確率有著顯著的提高。

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

TAGE預測器標記預測表優(yōu)先級比基礎預測表更高，導致與歷史不相關的分支預測準確率較低；并且使用程序計數器(PC)的部分位索引預測表，分支別名問題比較突出。針對TAGE分支預測器存在的這兩個問題，對分支預測器的結構進行改進，改進之后的方法使得預測器的預測準確率明顯提高。

1 傳統(tǒng)型TAGE分支預測器

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

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

圖1 TAGE分支預測器

圖2 預測表行組成

分支預測步驟：

(1)每一條分支指令對應一個程序計數器值。首先將程序計數器(PC)的部分位索引T0表，得到兩位飽和計數器的值。

(2)將歷史寄存器h分成4等分。將程序計數器(PC)部分位分別與歷史寄存器的1/4長度位寬、2/4長度位寬、3/4長度位寬、4/4長度位寬進行兩次不同的哈希計算，得到8個結果值，作為4張表的索引值和標記值。

(3)利用索引值選取T1、T2、T3、T4 4張表對應的行，取出對應行的tag位與步驟(2)標記值進行比較。如果相等，則取出對應行的ctr。否則，忽略該表的預測值。

(4)根據步驟(2)和(3)得到不止一個預測值。預測值優(yōu)先級次序為T4>T3>T2>T1>T0，根據優(yōu)先級選出最終的預測值。

1.2 算法缺陷

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

(1)使用程序計數器(PC)的部分位運算得到預測表的索引值和標記值，這使得不同的分支索引到同一項的概率依然很大，分支別名的問題并沒有從根本上得到解決。

(2)基礎預測表優(yōu)先級最低，分支預測器預測的最終值大多來自于標記預測表，這使得對與歷史不相關的分支預測準確率不高。

針對第一個缺陷，對程序計數器(PC)進行特征提取，使用特征提取值代替程序計數器(PC)的部分位，這樣一來，特征值能夠充分反映整個程序計數器(PC)的信息，能夠和其他的程序計數器(PC)值區(qū)分開來。針對第二個缺陷，可以提升基礎預測表的優(yōu)先級，使得基礎預測表與標記預測表有著相同的優(yōu)先級。

2 改進型TAGE分支預測器

2.1 PC特征提取

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

圖3 特征提取圖

具體的計算步驟：

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

其中：

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

其中：

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

2.2 改進型TAGE分支預測器結構

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

圖4 改進型TAGE分支預測器

ctrtake_cntn_taken_cntu

改進型預測器預測步驟：

(1)對程序計數器進行特征提取，得到特征值。

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

(3)利用索引值選取T1、T2、T3、T44張表對應的行，取出對應行的tag位與步驟2標記值進行比較。如果相等，則取出對應行的ctr和u。否則，忽略該表的預測值。

(4)根據預測表的優(yōu)先級T4>T3>T2>T1，從標記預測表選擇優(yōu)先級最高的ctr和u。

(5)從基礎預測表T0得到ctr和u。

(6)比較置信度。如果基礎預測表的置信度(u)大于標記預測表的置信度，則取基礎預測表的預測值(ctr)作為最終的預測值，否則取標記預測表的預測值(ctr)作為最終的預測值。

3 性能評估

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

圖6 使用spec2000部分子程序測試對比圖

表1 資源消耗以及功耗對比

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

4 結束語

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

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

[2]茍鵬飛, 喻明艷, 楊兵, 等. 基于類型預測的甚塊預測器[J]. 計算機學報, 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

國家自然科學基金項目(61474001)

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

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

責任編校：孫 林