分支預(yù)測器BPU是深入研究一個高性能處理器的一個很好的開始項目；

0 Intro

條件分支是指后續(xù)具有兩路可執(zhí)行的分支?？梢苑譃樘D(zhuǎn)分支(taken branch)和不跳轉(zhuǎn)分支(not-taken branch)。不跳轉(zhuǎn)分支，指接下來會順序執(zhí)行緊挨著JMP的指令。跳轉(zhuǎn)分支，通過JMP跳轉(zhuǎn)到另外一塊內(nèi)存去執(zhí)行那里的指令。
分支預(yù)測器的主要功能是：預(yù)測執(zhí)行過程中的分支指令(Eg: if-else、循環(huán)語句等)的跳轉(zhuǎn)方向，進(jìn)行提前取指并執(zhí)行正確的指令流；
常見的分支預(yù)測器：
1.靜態(tài)預(yù)測器：不依賴于程序執(zhí)行歷史，總是預(yù)測跳轉(zhuǎn)或者不跳轉(zhuǎn)；
2.動態(tài)預(yù)測器：一般使用一個計數(shù)器來記錄分支跳轉(zhuǎn)和不跳轉(zhuǎn)的次數(shù)，如果跳轉(zhuǎn)次數(shù)多于不跳轉(zhuǎn)次數(shù)，則預(yù)測分支會跳轉(zhuǎn)；
3.兩級自適應(yīng)預(yù)測器：使用一個全局歷史寄存器來記錄最近的分支執(zhí)行情況，并依據(jù)這些信息來預(yù)測分支的跳轉(zhuǎn)方向；
4.局部歷史表：該預(yù)測器策略為每個分支維護(hù)一個局部歷史表，記錄該分支最近的執(zhí)行情況，并依據(jù)這些信息來預(yù)測分支的跳轉(zhuǎn)方向；
5.相關(guān)預(yù)測器：該預(yù)測器不僅考慮分支的歷史執(zhí)行情況，還考慮其他相關(guān)分支的執(zhí)行情況，以提高預(yù)測的準(zhǔn)確性；
依據(jù)上面的預(yù)測器原理可以設(shè)計成不同的預(yù)測器組件；

0.1 CPU執(zhí)行過程

典型CPU執(zhí)行五級流水線：取指、譯碼、執(zhí)行、訪存和寫回；
取指：根據(jù)程序計數(shù)器（pc）的記錄，依次取出指令傳遞給譯碼單元并更新pc；
譯碼：根據(jù)不同的指令集架構(gòu)進(jìn)行指令行為區(qū)分，識別出指令的操作及操作數(shù)等；
執(zhí)行：得到指令的對應(yīng)的操作類型及操作數(shù)后，進(jìn)行執(zhí)行操作；
訪存：從memory中讀取或?qū)懭雖emory中；
寫回：將指令執(zhí)行的結(jié)果寫回到寄存器中，用于后續(xù)指令；

為了提高CPU的性能，減少時鐘浪費，一般措施是引入：引入分支預(yù)測及亂序執(zhí)行技術(shù)；
亂序執(zhí)行：可以提高指令執(zhí)行的效率，當(dāng)前條指令處于等待狀態(tài)而后續(xù)的指令不依賴于前條指令時，可以優(yōu)先執(zhí)行后續(xù)指令，通過引入亂序執(zhí)行，有效縮短指令執(zhí)行時間。
分支預(yù)測：可以避免流水線的空閑等待，在指令流水型執(zhí)行時，不必等待執(zhí)行結(jié)果，提前進(jìn)行指令預(yù)測并取指令進(jìn)行后續(xù)動作，可以大大減少指令等待時間，接下來對分支預(yù)測技術(shù)進(jìn)行詳細(xì)介紹。

0.2 分支預(yù)測

分支預(yù)測主要用來預(yù)測下一條指令，當(dāng)沒有分支預(yù)測機(jī)制時，需要等待指令操作數(shù)計算出跳轉(zhuǎn)地址后才能確定下一條執(zhí)行指令，并由取指令單元取指令，這個過程會導(dǎo)致流水線處于等待狀態(tài)。對于現(xiàn)代處理器來說，若預(yù)測結(jié)果錯誤，需要沖刷流水線。
預(yù)測任務(wù)主要分為兩個部分：1.預(yù)測是否跳轉(zhuǎn)；2.預(yù)測跳轉(zhuǎn)的地址；
靜態(tài)與動態(tài)預(yù)測器的區(qū)別：就是會不會參考程序的執(zhí)行歷史；
最典型的動態(tài)預(yù)測器：2-bit飽和計數(shù)器；----狀態(tài)機(jī)表示的邏輯還是很清楚的；

最最理想的情況：可以為每一個分支都分配一個2bit飽和計數(shù)器，但是這樣的做法會帶來巨大的開銷，因此一般情況下使用pc的一部分去尋址pattern history table（PHT），查詢表中飽和計數(shù)器的數(shù)值，做出預(yù)測，但會導(dǎo)致不同分支尋址到相同的表項而做出錯誤的預(yù)測（aliasing），我們會在下面提到一些解決方法：

0.2.1 TAGE預(yù)測器

利用飽和計數(shù)器作為預(yù)測表項–TAGE預(yù)測器；

TAGE預(yù)測器核心思想：使用多個不同長度的歷史寄存器來捕捉分支指令的歷史行為。
TAGE的預(yù)測機(jī)制：Base Predicitor使用PC部分位來索引，3bit飽和計數(shù)器用于計算預(yù)測結(jié)果，2bit的userful counter及partial tage作為表項，構(gòu)成標(biāo)記預(yù)測器；

四個標(biāo)記預(yù)測器采用不同長度的全局歷史寄存器（GHR），四個標(biāo)記預(yù)測表大小一致，因此需要先將GHR壓縮為相同位寬后與PC部分位進(jìn)行哈希作為索引查詢表項（利用哈希解決aliasing問題），查詢到tag命中（tag的哈希計算方法不同于索引的哈希計算方法），則取出該標(biāo)記預(yù)測器的預(yù)測結(jié)果，預(yù)測結(jié)果由3bit的飽和計數(shù)器計算得出。
Tage最終的預(yù)測結(jié)果取GHR最長的標(biāo)記預(yù)測器的預(yù)測結(jié)果。
上述表格：predictor(3bit飽和計數(shù)器)+ tag(1bit 是否命中) + u(userful counter用來記錄是否需要更新)。

0.2.2 跳轉(zhuǎn)地址

上面是解決的分支指令跳不跳的問題–即taken or not taken的問題；
當(dāng)做出對跳轉(zhuǎn)的預(yù)測時，需要查詢跳轉(zhuǎn)的地址，這一部分一般由BTB實現(xiàn)。BTB是類似于cache的結(jié)構(gòu)，主要用來記錄目標(biāo)的跳轉(zhuǎn)地址。BTB表用（partial）pc作為索引，當(dāng)一個分支指令第一次執(zhí)行時，記錄該分支指令的目標(biāo)地址并分配一個表項，當(dāng)前面提到的預(yù)測器得到taken/not taken的預(yù)測結(jié)果后，在BTB中查詢跳轉(zhuǎn)地址。

未完待續(xù)…
[Ref]
https://www.birentech.com/Research_nstitute_details/1.html