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

0 Intro

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

0.1 CPU執(zhí)行過程

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

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

0.2 分支預(yù)測(cè)

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

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

0.2.1 TAGE預(yù)測(cè)器

利用飽和計(jì)數(shù)器作為預(yù)測(cè)表項(xiàng)–TAGE預(yù)測(cè)器；

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

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

0.2.2 跳轉(zhuǎn)地址

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

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