CPU 的分支預測器是怎樣工作的？

12-19

在CPU中的分支預測器是具體在哪個位置？形態大概是怎樣的？它是怎麼起到作用的？如果預測失敗它又是怎樣繞過已經失敗的預測從而增加重新預測的成功率的？

1. 位置：分支預測器位於整個CPU核心流水線的差不多最前端部分，也就是靠近一級指令緩存的位置。從指令緩存裡面讀取指令時，需要由分支預測器來判斷從哪裡讀取。

2. 形態：分支預測器主要由兩個大塊組成（我隨口掰的，教科書上很可能不是這樣分），其中一塊是歷史記錄表，記錄以往執行過的分支指令的偏向情況，幫助未來的預測，本質上也是一塊高速緩存。另一塊是預測器的邏輯部分，這一部分用來維護記錄表，依據記錄表裡面的記錄情況預測將來的分支走向。

3. 預測方法舉例。比如說有一條分支指令，執行了十幾次都是跳轉，那麼預測器就會判斷，將來碰到這條指令時，它仍舊會跳轉。當這條指令的預測結果連續兩次出錯的時候，預測器就會調整自己的預測結果，改為判斷它不跳轉。這一預測方法是現今仍在沿用的2-bit計數器陣列，源於前CDC公司的James Smith（現為WISC-Madison的榮譽教授）在上世紀80年代初左右的發明，實測結果表明它的預測準確率基本上能到80+%甚至90%+上下。

到了九十年代初期，我們這個圈子裡一個叫做Yale Patt的大牌教授引領了幾乎十年的分支預測研究浪潮，他們做的預測器比James Smith的先進很多，被稱為自適應預測，可以捕捉住更多的分支歷史模式。（八卦：在Patt手下做預測的那個博士生Tse-Yu Yeh後來參加一個學術會議，Intel的人看到了他們做的東西，直接把人給挖走了，那個預測器用在了P6微結構裡面，後來Tse-Yu Yeh離開Intel到了PA Semi，現在好像是在Apple的CPU設計團隊。）

後來又有很多人加入進來做分支預測的研究，做出了關聯性分支預測、返回棧預測等等非常棒的預測器，現在的分支預測器結構通常是競標賽式的複合分支預測器，比如當關聯性分支預測器的近期準確率比較高時，優先採用它，如果有其他預測器的近期準確率更高，就放棄它。後來的研究越來越精細，針對分支預測做了很多很多的調優，比如說如何在有限的空間裡面儘可能減少大量分支指令對歷史記錄表的爭搶、嘗試對分支指令進行分類，每一類使用專門的預測器進行預測等等，現在的分支預測器非常強大，面對各種各樣的程序，預測準確率都能非常堅挺地保持在95%以上。

微結構上的推測執行技術有很多種，分支預測引領的控制流相關的推測執行可能是其中最成功的一種。

@泰羅Taro 的答案已經說了個大概了，我再來結合當年幾篇經典的原版論文詳細地補充一下。

首先先說明分支預測的大類，靜態預測(static prediction)和動態預測(dynamic prediction)。

所謂靜態預，就是無論執行的是什麼指令，分支預測器總是執行相同的prediction strategy。動態預測則會根據執行指令的不同，依據program counter(PC)的值以及歷史信息等做出不同的預測。顯然後者由於利用了更多的信息，所以在一般情況下會更加精確，但也並不是說前者就完全沒用了，畢竟實現起來非常簡單，可以降低晶元成本+節省功耗，而且預測準確率其實也不是很差。

靜態預測

@Tianheng Chen的答案中所說的「最簡單」的分支預測其實並不是最簡單的，最簡單的predictor應該是這樣的：

預測所有的分支都會跳轉（taken）

完了。

哈哈是不是有一種「沒有設計就是最好的設計」的感覺？

那麼這樣最簡單的分支預測器的準確度是多少呢？來看看James Smith的論文[1]中跑了6個benchmark的結果：

卧槽居然都在50%以上，最高的還達到了99.4%！簡直有點不科學啊。

從概率的角度看，這樣預測的準確度期望值也就是50%左右。然而實際上由於程序中的循環很多，比如一個程序里最多的一個loop循環了幾十萬次，幾乎每次都是taken，其他的branch即使預測錯了幾千個，平均下來預測的準確度還是會很高。

類似的靜態預測策略還有：

某些指令一律預測跳轉，其他指令一律預測不跳轉。（例如判斷是大於等於的一律跳轉，判斷是小於的一律不跳轉）
做出和上次是否taken相同的預測。
預測向前的分支（backward branch)會跳轉，向後的分支(forwad branch)不跳轉。（這裡的前後指的的是地址空間的前後，針對的情況就是每當到了一個循環的末尾判斷是否繼續循環時會預測向前跳繼續循環）

以上這些策略的精確度都還不錯，平均值都有70%以上，具體數據可以去看原來的論文[1]。所以當你設計一個對性能要求不是特別高但又要低功耗低成本的時候，採用靜態策略是不錯的選擇。

2. 動態預測
在文章[1]中，James Smith就提出了一種簡單的 2-bit 狀態機（實質上也是一個saturated counter）：
初始值為00，每當一個branch taken，就+1，branch沒有taken則-1。到11和00的時候則加減一則各自維持現狀，根據第一位的值來進行預測，例如11預測taken，01預測 not taken。

用一個2bit狀態機的核心思路就是：這次預測錯了不要緊，再給你一次機會，還是預測錯了的話那再改變預測結果。總之就是提供了一定的容錯率。可想而知這樣的預測準確率自然也是提高了的：

而另外一個Smith：Alan Smith，又在論文[2]中對這個狀態機進行了改進和探索，並且在同一篇論文中提出了Target Buffer的設計。以下是他提出的另外一些狀態機，比如這種：

圖比較多就不一一貼了。

再再後來就是Yale Patt大神出來放大招了，這裡才是 @泰羅Taro 答案中所說的，稱之為 2 Level Adaptive Training，汲取了上述方法的精華，估計也是目前採用最廣泛最成熟的方法。其核心原理如圖：（摘自其論文[3]）

左邊是一個History Table，記錄著每一條branch instruction是否跳轉了的歷史記錄，然後根據這個值，索引到中間的Pattern Table。比如一條指令歷史記錄一直是跳轉的，那麼這時候HR的值就是1111 （假設只有4位），然後就會用PT中第16個位置的值做出預測。而做出預測的根據則是前面所說的狀態機的方法。同時本次的實際跳轉結果也會輸入到做出預測的這個狀態機中進行training。

呼，講到這終於差不多把主要思路講完了。。下面看結果：

圖中每兩條虛線之間是4%。可以看到大部分預測的準確率都已經達到了96%以上了。

把research做到這個份兒上，還讓不讓別人發paper了（╯" - ")╯︵ ┻━┻

所以後續的很多research都是針對這個模型的優化，但上升的空間已經很小了，畢竟你不能把預測率做過100%嘛。。但廣大科研青年還是發現即使只有10%的上升空間，也還是大有可為的。

比如你把hit rate從99%提高到了99.5%，你也可以宣稱把miss rate降低了50%嘛。（嚴肅臉

不過其實這個領域的研究前沿我並不了解，權當拋磚引玉。

[1] A study of branch prediction strategies
[2] IEEE Xplore Abstract
[3] Two-level adaptive training branch prediction

我來寫一寫我上課學過的分支預測。從簡單到最複雜的：
1.

這個是最簡單的分支預測，根據當前指令的地址，放進PHT中，根據右邊的這張狀態機，來確定是跳轉還是不跳轉。優勢：簡單，具有相當的準確性。

2.
兩級預測

這個預測機構比較複雜，擁有兩級分支，相比之前的方法，加入了BHT，可以根據指令地址，記錄一部分歷史記錄，然後再放進PHT中，決定跳轉還是不跳轉。優點在於可以記錄下某一些跳轉的關係，加強聯繫。

混合預測，集合了上面兩個的優點，加上自己設定的選擇器。

可以方便的看到，基本上所有的預測機制都是通過以往的歷史記錄來加強或者削弱跳轉關係。第一種方法很直接，用一個狀態機來描述了整個機制。第二個方法甚至在第一個的基礎上記錄了N多個跳轉的記錄。

判斷出是否跳轉之後，CPU需要知道跳轉到哪裡，因為不是每次跳轉的位置都是一樣的。所以在預測的基礎上又加上了BTB整個東西，這個東西記錄了之前跳轉的地址，因此CPU可以不計算跳轉的地址，直接預先load指令，如果出錯的話，將會刷新BTB，並且flush所有指令，重新load。
BTB的結構如下：

BTB的工作方式如下：

那麼如果將這些所有的東西結合到CPU的流水線上，將會變成如下的流程：

以上圖片摘自學校講義，如有侵權，請告知。萬分感謝。

不得不搬運一下Yee在StackOverflow上的回答，感覺是在SO上看過的最深入淺出的答案了：
java - Why is processing a sorted array faster than an unsorted array?

體系結構量化分析一書講得很透徹建議一看

computer arch裡面講的就不複述了，無非就是幾個狀態機量化，然後各種hash的方式.

Prof講到這個內容的時候，印象最深的是他問「你們覺得90%的成功率高嘛？」我們一幫人點點頭，尼瑪10次裡面猜對9次還不高？
他說：「很爛...因為現代的CPU 都是deep pipeline, miss一次代價就很大. 而90%這個hit rate在數量級非常大的時候，簡直不能看」.

分支預測用於配合流水線，可以提前將指令發射到流水線中。
如果預測失敗，就要排空流水線，重新載入實際的下一條指令，這樣會導致效率下降。

一般的BTB裡面就是這樣：強轉移，弱轉移，弱不轉移，強不轉移。

預測的狀態轉移如下圖：

分支預測是基於硬體層的
由於多流水的出現，當Cpu的某條流水因為某些原因滯後的時候，會拉低整個程序的運行速度，所以就需要分支預測來進行預測並進行下一步操作

其工作機理就是在一條指令執行的同時，在一條分支進程上上根據一套分支預測規律預測並執行可能的下一條指令，待主進程指令運行結束後，判斷下一條指令是否和預測結果相同，如果相同直接將分支進程的運算結果拷貝到主進程中，如預測錯誤，主進程繼續運行，分支進程進行下一次預測。
這裡有一個比較著名的分支預測問題
兩個數組內容相同，一個排序，另一個沒有排序，運行如下程序
Int d=0;
For(int I =0;I& If (num[i]&<100)
D++

提一個小點。

往回跳的jmpx指令，預測他一定會跳轉。（往回跳九成九是循環，那麼只循環1次的邏輯和概率應該很少吧）

csapp 第四章有比較詳細講到過，在5 stage design里，execute stage算出預測結果正確與否，如果錯誤，那麼fetch ，decode stage會注入bubble來消除影響。雖然我看的迷迷糊糊的(⌒▽⌒)