【導(dǎo)讀】在CPU中的分支預(yù)測器是具體在哪個位置？形態(tài)大概是怎樣的？它是怎么起到作用的？如果預(yù)測失敗它又是怎樣繞過已經(jīng)失敗的預(yù)測從而增加重新預(yù)測的成功率的？小編綜合收集的資料一一回答這些問題。
1.位置：分支預(yù)測器位于整個CPU核心流水線的差不多最前端部分，也就是靠近一級指令緩存的位置。從指令緩存里面讀取指令時，需要由分支預(yù)測器來判斷從哪里讀取。
2.形態(tài)：分支預(yù)測器主要由兩個大塊組成（教科書上有可能不是這樣分），其中一塊是歷史記錄表，記錄以往執(zhí)行過的分支指令的偏向情況，幫助未來的預(yù)測，本質(zhì)上也是一塊高速緩存。另一塊是預(yù)測器的邏輯部分，這一部分用來維護(hù)記錄表，依據(jù)記錄表里面的記錄情況預(yù)測將來的分支走向。
3.預(yù)測方法舉例。比如說有一條分支指令，執(zhí)行了十幾次都是跳轉(zhuǎn)，那么預(yù)測器就會判斷，將來碰到這條指令時，它仍舊會跳轉(zhuǎn)。當(dāng)這條指令的預(yù)測結(jié)果連續(xù)兩次出錯的時候，預(yù)測器就會調(diào)整自己的預(yù)測結(jié)果，改為判斷它不跳轉(zhuǎn)。這一預(yù)測方法是現(xiàn)今仍在沿用的2-bit計(jì)數(shù)器陣列，源于前CDC公司的JamesSmith（現(xiàn)為WISC-Madison的榮譽(yù)教授）在上世紀(jì)80年代初左右的發(fā)明，實(shí)測結(jié)果表明它的預(yù)測準(zhǔn)確率基本上能到80%甚至90%上下。
4.后記：到了九十年代初期，這個圈子里一個叫做YalePatt的大牌教授引領(lǐng)了幾乎十年的分支預(yù)測研究浪潮，他們做的預(yù)測器比JamesSmith的先進(jìn)很多，被稱為自適應(yīng)預(yù)測，可以捕捉住更多的分支歷史模式。（在Patt手下做預(yù)測的那個博士生Tse-YuYeh后來參加一個學(xué)術(shù)會議，Intel的人看到了他們做的東西，直接把人給挖走了，那個預(yù)測器用在了P6微結(jié)構(gòu)里面，后來Tse-YuYeh離開Intel到了PASemi，現(xiàn)在好像是在Apple的CPU設(shè)計(jì)團(tuán)隊(duì)。）
后來又有很多人加入進(jìn)來做分支預(yù)測的研究，做出了關(guān)聯(lián)性分支預(yù)測、返回棧預(yù)測等等非常棒的預(yù)測器，現(xiàn)在的分支預(yù)測器結(jié)構(gòu)通常是競標(biāo)賽式的復(fù)合分支預(yù)測器，比如當(dāng)關(guān)聯(lián)性分支預(yù)測器的近期準(zhǔn)確率比較高時，優(yōu)先采用它，如果有其他預(yù)測器的近期準(zhǔn)確率更高，就放棄它。后來的研究越來越精細(xì)，針對分支預(yù)測做了很多很多的調(diào)優(yōu)，比如說如何在有限的空間里面盡可能減少大量分支指令對歷史記錄表的爭搶、嘗試對分支指令進(jìn)行分類，每一類使用專門的預(yù)測器進(jìn)行預(yù)測等等，現(xiàn)在的分支預(yù)測器非常強(qiáng)大，面對各種各樣的程序，預(yù)測準(zhǔn)確率都能非常堅(jiān)挺地保持在95%以上。
微結(jié)構(gòu)上的推測執(zhí)行技術(shù)有很多種，分支預(yù)測引領(lǐng)的控制流相關(guān)的推測執(zhí)行可能是其中最成功的一種。
[page]
附：分支預(yù)測圖解，從簡單到最復(fù)雜的：
這個是最簡單的分支預(yù)測，根據(jù)當(dāng)前指令的地址，放進(jìn)PHT中，根據(jù)右邊的這張狀態(tài)機(jī)，來確定是跳轉(zhuǎn)還是不跳轉(zhuǎn)。優(yōu)勢：簡單，具有相當(dāng)?shù)臏?zhǔn)確性。
兩級預(yù)測
這個預(yù)測機(jī)構(gòu)比較復(fù)雜，擁有兩級分支，相比之前的方法，加入了BHT，可以根據(jù)指令地址，記錄一部分歷史記錄，然后再放進(jìn)PHT中，決定跳轉(zhuǎn)還是不跳轉(zhuǎn)。優(yōu)點(diǎn)在于可以記錄下某一些跳轉(zhuǎn)的關(guān)系，加強(qiáng)聯(lián)系。
混合預(yù)測，集合了上面兩個的優(yōu)點(diǎn)，加上自己設(shè)定的選擇器。
可以方便的看到，基本上所有的預(yù)測機(jī)制都是通過以往的歷史記錄來加強(qiáng)或者削弱跳轉(zhuǎn)關(guān)系。第一種方法很直接，用一個狀態(tài)機(jī)來描述了整個機(jī)制。第二個方法甚至在第一個的基礎(chǔ)上記錄了N多個跳轉(zhuǎn)的記錄。
判斷出是否跳轉(zhuǎn)之后，CPU需要知道跳轉(zhuǎn)到哪里，因?yàn)椴皇敲看翁D(zhuǎn)的位置都是一樣的。所以在預(yù)測的基礎(chǔ)上又加上了BTB整個東西，這個東西記錄了之前跳轉(zhuǎn)的地址，因此CPU可以不計(jì)算跳轉(zhuǎn)的地址，直接預(yù)先load指令，如果出錯的話，將會刷新BTB，并且flush所有指令，重新load。
BTB的結(jié)構(gòu)如下：
BTB的工作方式如下：
那么如果將這些所有的東西結(jié)合到CPU的流水線上，將會變成如下的流程：
