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