徐永新

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

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

流水線的控制沖突也稱為分支沖突。程序執(zhí)行過程中有許多分支跳轉的情況，流水線遇到分支跳轉時，并不知道后面要真正執(zhí)行的指令在哪里，因為分支跳轉的目標地址還沒有被計算出來。這個時候流水線就需要采用某種策略，來預測后面將要執(zhí)行的分支。如果預測對了，那么流水線的效率將能維持在較好的水平。反之，預測錯了，則錯誤的流水線處理結果都會被丟棄，重新從正確的目標地址取出指令重新執(zhí)行，這將嚴重影響流水線的執(zhí)行效率。

1 分支預測技術

1.1 靜態(tài)分支預測器

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

靜態(tài)分支預測特點是實現(xiàn)簡單，但是預測的精度不高，在早期的CPU 設計中會使用這種方式。

1.2 動態(tài)分支預測器

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

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

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

基于BHT 和BTB 的結構，衍生出一些改進的分支預測器，比如Gshare 預測器，Agree 預測器，Bi-Mode 預測器等等。

1.3 基于神經網(wǎng)絡的預測器

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

基于神經網(wǎng)絡的預測器的特點是經過充分的訓練之后預測準確度比較高，但是訓練的過程耗時較長，并且由于需要做矩陣運算，其算法存在一定的時延問題。

2 分支預測對比實驗

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

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

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

表1：實驗對比數(shù)據(jù)

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

2.1 分支預測成功實驗

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

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

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

2.2 分支預測機制失效實驗

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

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

2.3 無分支指令實驗

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

3 實驗數(shù)據(jù)

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

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

4 結語

通過對分支預測機制的介紹，以及實驗數(shù)據(jù)的展示，我們可以得出下面的結論：

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

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

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