分支預(yù)測(cè)技術(shù)對(duì)性能影響研究

徐永新

（華為技術(shù)有限公司 江蘇省南京市 210012）

為了提升處理性能，現(xiàn)代CPU 采用多級(jí)流水線機(jī)制，經(jīng)典的五級(jí)流水線分成取指，譯碼，執(zhí)行，訪存，寫回等幾個(gè)階段。流水線機(jī)制可以有效提升指令的并行度，但是存在一些流水線沖突的場(chǎng)景，造成流水線效率的降低。這樣的流水線沖突包括結(jié)構(gòu)沖突，控制沖突和數(shù)據(jù)沖突。

流水線的控制沖突也稱為分支沖突。程序執(zhí)行過程中有許多分支跳轉(zhuǎn)的情況，流水線遇到分支跳轉(zhuǎn)時(shí)，并不知道后面要真正執(zhí)行的指令在哪里，因?yàn)榉种D(zhuǎn)的目標(biāo)地址還沒有被計(jì)算出來。這個(gè)時(shí)候流水線就需要采用某種策略，來預(yù)測(cè)后面將要執(zhí)行的分支。如果預(yù)測(cè)對(duì)了，那么流水線的效率將能維持在較好的水平。反之，預(yù)測(cè)錯(cuò)了，則錯(cuò)誤的流水線處理結(jié)果都會(huì)被丟棄，重新從正確的目標(biāo)地址取出指令重新執(zhí)行，這將嚴(yán)重影響流水線的執(zhí)行效率。

1 分支預(yù)測(cè)技術(shù)

1.1 靜態(tài)分支預(yù)測(cè)器

靜態(tài)分支預(yù)測(cè)是一種實(shí)現(xiàn)簡(jiǎn)單的方法，比如預(yù)測(cè)永遠(yuǎn)不發(fā)生跳轉(zhuǎn)，取指單元總是按順序取指，直到發(fā)現(xiàn)錯(cuò)誤才丟棄不正確的中間狀態(tài)，重新取指。

靜態(tài)分支預(yù)測(cè)特點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，但是預(yù)測(cè)的精度不高，在早期的CPU 設(shè)計(jì)中會(huì)使用這種方式。

1.2 動(dòng)態(tài)分支預(yù)測(cè)器

現(xiàn)代處理器使用較多的是動(dòng)態(tài)分支預(yù)測(cè)器，該類預(yù)測(cè)器能夠記錄分支的歷史跳轉(zhuǎn)信息，來預(yù)測(cè)將要執(zhí)行的分支跳轉(zhuǎn)行為。如果由于程序執(zhí)行的行為發(fā)生改變，預(yù)測(cè)器也會(huì)根據(jù)執(zhí)行情況自動(dòng)調(diào)整，從而擁有較好的預(yù)測(cè)準(zhǔn)確度和自適應(yīng)性。

動(dòng)態(tài)分支預(yù)測(cè)使用分支歷史表BHT 來記錄最近一次或者幾次的執(zhí)行情況。兩位飽和計(jì)數(shù)器是最常用的方向預(yù)測(cè)器。當(dāng)計(jì)數(shù)值為11 時(shí)，分支轉(zhuǎn)移則計(jì)數(shù)器值保持不變，當(dāng)計(jì)數(shù)值為00 時(shí)，分支不轉(zhuǎn)移則計(jì)數(shù)器保持不變，其他情況分支轉(zhuǎn)移則計(jì)數(shù)器加1，分支不轉(zhuǎn)移則計(jì)數(shù)器減1。根據(jù)飽和計(jì)數(shù)器來預(yù)測(cè)當(dāng)前跳轉(zhuǎn)行為，并根據(jù)實(shí)際分支轉(zhuǎn)移情況更新飽和計(jì)數(shù)器的值。

將分支跳轉(zhuǎn)的指令地址和跳轉(zhuǎn)的目標(biāo)地址都記錄下來的緩沖區(qū)叫做分支目標(biāo)緩沖器BTB。程序計(jì)數(shù)器PC 值和BTB 中的分支指令地址進(jìn)行比較，如果相等則表明當(dāng)前是分支指令，如果同時(shí)預(yù)測(cè)會(huì)發(fā)生分支跳轉(zhuǎn)，則可以把BTB 中的目標(biāo)地址作為下一條取指地址。

基于BHT 和BTB 的結(jié)構(gòu)，衍生出一些改進(jìn)的分支預(yù)測(cè)器，比如Gshare 預(yù)測(cè)器，Agree 預(yù)測(cè)器，Bi-Mode 預(yù)測(cè)器等等。

1.3 基于神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)器

分支預(yù)測(cè)本質(zhì)上是機(jī)器學(xué)習(xí)問題，神經(jīng)網(wǎng)絡(luò)是一種比較有效的機(jī)器學(xué)習(xí)方法。神經(jīng)網(wǎng)絡(luò)的輸入層是當(dāng)前分支的地址所對(duì)應(yīng)的分支歷史寄存器狀態(tài)，每個(gè)分支歷史狀態(tài)有相應(yīng)的歷史權(quán)重，根據(jù)神經(jīng)網(wǎng)絡(luò)算法得出輸出層的值，用來表示當(dāng)前是跳轉(zhuǎn)還是不跳轉(zhuǎn)。如果預(yù)測(cè)成功對(duì)應(yīng)的權(quán)重會(huì)增加，預(yù)測(cè)失敗則權(quán)重減少?；谏窠?jīng)網(wǎng)絡(luò)的預(yù)測(cè)器可以邊訓(xùn)練邊預(yù)測(cè)。

基于神經(jīng)網(wǎng)絡(luò)的預(yù)測(cè)器的特點(diǎn)是經(jīng)過充分的訓(xùn)練之后預(yù)測(cè)準(zhǔn)確度比較高，但是訓(xùn)練的過程耗時(shí)較長，并且由于需要做矩陣運(yùn)算，其算法存在一定的時(shí)延問題。

2 分支預(yù)測(cè)對(duì)比實(shí)驗(yàn)

為了展示分支預(yù)測(cè)機(jī)制對(duì)性能的影響，筆者設(shè)計(jì)了一組實(shí)驗(yàn)，分別讓分支預(yù)測(cè)機(jī)制失效，分支預(yù)測(cè)機(jī)制成功，以及沒有分支指令等幾種情況作為對(duì)比，并測(cè)量出相應(yīng)的性能數(shù)據(jù)。

在實(shí)驗(yàn)中，程序的目標(biāo)是統(tǒng)計(jì)出數(shù)組中的奇數(shù)數(shù)量，并計(jì)算出所有的奇數(shù)之和。元素個(gè)數(shù)為k 的數(shù)組內(nèi)有n 個(gè)奇數(shù)，m 個(gè)偶數(shù)，被測(cè)程序需要遍歷數(shù)組統(tǒng)計(jì)奇數(shù)個(gè)數(shù)，并計(jì)算出所有奇數(shù)之和。循環(huán)查找的前后分別獲取cycles 值，其差值表示執(zhí)行循環(huán)所消耗的cycle 數(shù)。其部分代碼片段如下：

上述代碼使用C++編譯器按照下面的編譯選項(xiàng)，編譯出可執(zhí)行程序來驗(yàn)證。

表1：實(shí)驗(yàn)對(duì)比數(shù)據(jù)

g++ -O2 -g test.cpp -o test

2.1 分支預(yù)測(cè)成功實(shí)驗(yàn)

為了保證分支預(yù)測(cè)成功，在初始化數(shù)組的時(shí)候，把數(shù)組的前n個(gè)元素都初始化成奇數(shù)，后m 個(gè)元素都初始化成偶數(shù)，這樣有規(guī)律的排列，可以保證分支預(yù)測(cè)機(jī)制能準(zhǔn)確預(yù)測(cè)出分支的跳轉(zhuǎn)。代碼片段中需要注釋掉fisher_yates 函數(shù)。

初始化完畢之后的數(shù)據(jù)排列如下：

基于上述的規(guī)律數(shù)據(jù)，CPU 在執(zhí)行條件判斷語句if ((data[i]% 2)== 1)時(shí)，將很快學(xué)到其規(guī)律，分支預(yù)測(cè)基本上是成功的。

2.2 分支預(yù)測(cè)機(jī)制失效實(shí)驗(yàn)

為了讓分支預(yù)測(cè)機(jī)制失效，需要將有規(guī)律的數(shù)組變成一個(gè)隨機(jī)排列的數(shù)組。Fisher-Yate 算法是用來將一個(gè)有限集合生成隨機(jī)排列的算法。在隨機(jī)化奇數(shù)偶數(shù)排列之后，分支預(yù)測(cè)器將無法預(yù)測(cè)分支跳轉(zhuǎn)，從而讓分支預(yù)測(cè)機(jī)制失效。隨機(jī)化之后的數(shù)據(jù)排列呈現(xiàn)無規(guī)律的狀態(tài)：

基于上述的無規(guī)律數(shù)據(jù)，CPU 在執(zhí)行條件判斷語句if ((data[i]% 2) == 1)時(shí)，無法通過歷史數(shù)據(jù)來判斷分支跳轉(zhuǎn)的規(guī)律，分支預(yù)測(cè)極大概率是失敗的。

2.3 無分支指令實(shí)驗(yàn)

為了避免分支指令對(duì)性能造成的影響，編程中可以采用技巧，避免使用條件判斷語句。判斷奇數(shù)可以看數(shù)據(jù)的最低位是否為1，使用位運(yùn)算來代替條件判斷。比如可以把循環(huán)里面的代碼改成如下的方式：

3 實(shí)驗(yàn)數(shù)據(jù)

筆者在AMD Ryzen 5 4600H CPU 上運(yùn)行測(cè)試程序，改變循環(huán)次數(shù)，分別針對(duì)無規(guī)律數(shù)據(jù)分支預(yù)測(cè)失敗，有規(guī)律數(shù)據(jù)分支預(yù)測(cè)成功，無規(guī)律數(shù)據(jù)無分支指令，有規(guī)律數(shù)據(jù)無分支指令這四種情況，測(cè)量出了一組執(zhí)行時(shí)間cycle 值的對(duì)比數(shù)據(jù)。

表1中第一行表示數(shù)組大小，即循環(huán)次數(shù)分別為10000 到50000 次，其余的數(shù)字表示測(cè)得的對(duì)應(yīng)情況的cycle 數(shù)。由實(shí)驗(yàn)數(shù)據(jù)可知，分支預(yù)測(cè)失敗的情況下的執(zhí)行時(shí)間基本上是預(yù)測(cè)成功的4.2倍左右。而沒有分支指令的情況下，有規(guī)律的數(shù)據(jù)和無規(guī)律的數(shù)據(jù)，對(duì)執(zhí)行時(shí)間沒有影響，兩者對(duì)比數(shù)據(jù)沒有顯著的差別。

4 結(jié)語

通過對(duì)分支預(yù)測(cè)機(jī)制的介紹，以及實(shí)驗(yàn)數(shù)據(jù)的展示，我們可以得出下面的結(jié)論：

（1）現(xiàn)代CPU 往往都有設(shè)計(jì)良好的分支預(yù)測(cè)機(jī)制，如果某段程序執(zhí)行路徑不是關(guān)鍵瓶頸，則不必花時(shí)間去做精細(xì)的分支優(yōu)化，交給CPU 和編譯器去做優(yōu)化處理即可。

（2）如果某段程序代碼屬于關(guān)鍵執(zhí)行路徑，則在大規(guī)模循環(huán)中需要優(yōu)化分支判斷，讓分支條件的判斷是有規(guī)律的，這樣才能有效利用CPU 的分支預(yù)測(cè)機(jī)制。

（3）如果可以使用運(yùn)算技巧來避免分支判斷，也可以消除無規(guī)律的分支判斷給流水線帶來的效率影響。