本題鏈接：

https://hdlbits.01xz.net/wiki/Cs450/gshare

分支預(yù)測(cè)器生成條件分支指令方向的選擇/不選擇預(yù)測(cè)。它位于處理器流水線的前端，負(fù)責(zé)將指令導(dǎo)向正確的程序執(zhí)行路徑。分支預(yù)測(cè)器通常與分支目標(biāo)緩沖區(qū)(BTB)一起使用，其中 BTB 預(yù)測(cè)目標(biāo)地址，而分支預(yù)測(cè)器選擇的是分支到目標(biāo)還是繼續(xù)沿直通路徑獲取。

在流水線的后期（通常在分支執(zhí)行或停用時(shí)），執(zhí)行的分支指令的結(jié)果將被發(fā)送回分支預(yù)測(cè)器，以訓(xùn)練它通過(guò)觀察過(guò)去的分支行為來(lái)更準(zhǔn)確地預(yù)測(cè)未來(lái)的分支。當(dāng)存在錯(cuò)誤預(yù)測(cè)的分支時(shí)，也可能存在流水線刷新。

在本練習(xí)中，假定分支方向預(yù)測(cè)器位于右邊的圖中所示的假設(shè)的處理器流水線的提取階段。本練習(xí)只構(gòu)建由圖中的藍(lán)色虛線矩形顯示的分支預(yù)測(cè)器。

分支方向預(yù)測(cè)是一個(gè)組合路徑：pc寄存器用于計(jì)算已選擇/不選擇預(yù)測(cè)，影響next-pc多路復(fù)用器確定下一個(gè)周期pc的值。

相反，對(duì)模式歷史表（PHT）和分支歷史寄存器的更新將在下一個(gè)時(shí)鐘上升沿生效，正如存儲(chǔ)在觸發(fā)器中的狀態(tài)所預(yù)期的那樣。

Gshare 預(yù)測(cè)變量

分支預(yù)測(cè)器通常構(gòu)建為由程序計(jì)數(shù)器和分支歷史記錄索引的計(jì)數(shù)器表。表索引是分支地址和歷史記錄的哈希表，并嘗試為每個(gè)分支和歷史記錄組合提供自己的計(jì)數(shù)器索引（至少減少?zèng)_突次數(shù)）。每個(gè)計(jì)數(shù)器索引都包含一個(gè)兩位飽和計(jì)數(shù)器，用于執(zhí)行與過(guò)去相同的分支和歷史模式時(shí)記住分支方向。

這種預(yù)測(cè)變量樣式的一個(gè)例子是 gshare 預(yù)測(cè)變量。在 gshare 算法中，分支地址 （pc） 和歷史位“共享”表索引位?；?gshare 算法通過(guò)將 N 個(gè)分支地址位和 N 個(gè)全局分支歷史位一起計(jì)算 N 位 PHT 表索引。

然后使用 N 位索引訪問(wèn)兩位飽和計(jì)數(shù)器的 2^N 項(xiàng)表中的一項(xiàng)。此計(jì)數(shù)器的值提供預(yù)測(cè)（ 0?或 1 = 未取，2 或 3 = 已?。?。

訓(xùn)練以類似的方式索引表。訓(xùn)練 pc 和歷史用于計(jì)算表索引。然后，該索引處的兩位計(jì)數(shù)器根據(jù)分支的實(shí)際結(jié)果遞增或遞減。

引用

1. S. McFarling, "Combining Branch Predictors",?WRL Technical Note TN-36, Jun. 1993

描述

使用 7 位 pc 和 7 位全局歷史構(gòu)建 gshare 分支預(yù)測(cè)器，全局歷史記錄經(jīng)過(guò)哈希處理（使用異或）為 7 位索引。此索引訪問(wèn)包含兩位飽和計(jì)數(shù)器的 128 個(gè)計(jì)數(shù)器索引（類似于? cs450/counter_2bc ）。分支預(yù)測(cè)器應(yīng)包含一個(gè) 7 位全局分支歷史寄存器（類似于 cs450/history_shift ）。

分支預(yù)測(cè)器有兩組接口：一組用于預(yù)測(cè)，另一組用于訓(xùn)練。預(yù)測(cè)接口用于處理器的獲取階段，要求分支預(yù)測(cè)器對(duì)所獲取的指令進(jìn)行分支方向預(yù)測(cè)。一旦這些分支沿著流水線前進(jìn)并被執(zhí)行，分支的真實(shí)結(jié)果就變得已知。使用實(shí)際的分支方向結(jié)果對(duì)分支預(yù)測(cè)器進(jìn)行訓(xùn)練。

當(dāng)一個(gè)給定的?pc?分支預(yù)測(cè)被請(qǐng)求（predict_valid?= 1）時(shí)，分支預(yù)測(cè)器用于做出預(yù)測(cè)的分支歷史記錄器的預(yù)測(cè)的分支方向和狀態(tài)。然后（在下一個(gè)上升沿）為預(yù)測(cè)的分支更新分支歷史寄存器。

當(dāng)要求對(duì)分支進(jìn)行訓(xùn)練 （ train_valid = 1 ）時(shí)，分支預(yù)測(cè)器會(huì)被告知正在訓(xùn)練的分支的 pc 和分支歷史記錄值，實(shí)際的分支結(jié)果以及分支是否為錯(cuò)誤預(yù)測(cè)（需要流水線刷新）。更新模式歷史表 （PHT） 以訓(xùn)練分支預(yù)測(cè)器以便下次更準(zhǔn)確的預(yù)測(cè)此分支。此外如果正在訓(xùn)練的分支被錯(cuò)誤預(yù)測(cè)，也會(huì)在錯(cuò)誤預(yù)測(cè)的分支完成執(zhí)行后立即將分支歷史寄存器復(fù)位。

如果在同一周期中發(fā)生錯(cuò)誤預(yù)測(cè)和預(yù)測(cè)（針對(duì)不同的、較新的指令）的訓(xùn)練，則兩個(gè)操作都需要修改分支歷史記錄寄存器。發(fā)生這種情況時(shí)，訓(xùn)練優(yōu)先。因?yàn)闊o(wú)論如何都會(huì)丟棄被預(yù)測(cè)的分支。如果同一 PHT 條目的訓(xùn)練和預(yù)測(cè)同時(shí)發(fā)生，則預(yù)測(cè)會(huì)在訓(xùn)練之前得到 PHT 狀態(tài)，因?yàn)橛?xùn)練僅在下一個(gè)時(shí)鐘上升沿修改 PHT 。下面的時(shí)序圖顯示了訓(xùn)練時(shí)的時(shí)序和同時(shí)預(yù)測(cè) PHT 條目0的時(shí)序。第4周期的訓(xùn)練請(qǐng)求改變了第5周期的 PHT 進(jìn)入狀態(tài)，但是第4周期的預(yù)測(cè)請(qǐng)求輸出了第4周期的 PHT 狀態(tài)，而沒(méi)有考慮第4周期訓(xùn)練請(qǐng)求的影響。

areset 是一個(gè)異步復(fù)位，它將整個(gè) PHT 清除到 2b'01（弱不選擇）。它還會(huì)將全局歷史記錄寄存器清除為 0。

題目

答案

輸出波形

異步復(fù)位

訓(xùn)練條目（pc = 0xa, history = 0 和?2）

錯(cuò)誤預(yù)測(cè)的歷史記錄恢復(fù)

分支預(yù)測(cè)器（英語(yǔ)：Branch predictor）是一種數(shù)字電路，在分支指令執(zhí)行結(jié)束之前猜測(cè)哪一路分支將會(huì)被執(zhí)行，以提高處理器的指令流水線的性能。

條件分支指令通常具有兩路后續(xù)執(zhí)行分支。即不采?。╪ot taken）跳轉(zhuǎn)，順序執(zhí)行后面緊挨JMP的指令；以及采取（taken）跳轉(zhuǎn)到另一塊程序內(nèi)存去執(zhí)行那里的指令。

是否條件跳轉(zhuǎn)，只有在該分支指令在指令流水線中通過(guò)了執(zhí)行階段（execution stage）才能確定下來(lái)。

如果沒(méi)有分支預(yù)測(cè)器，處理器將會(huì)等待分支指令通過(guò)了指令流水線的執(zhí)行階段，才把下一條指令送入流水線的第一個(gè)階段—取指令階段（fetch stage）。這種技術(shù)叫做流水線停頓（pipeline stalled）或者流水線冒泡（pipeline bubbling）或者分支延遲間隙。這是早期的RISC體系結(jié)構(gòu)處理器采用的應(yīng)對(duì)分支指令的流水線執(zhí)行的辦法。

分支預(yù)測(cè)器猜測(cè)條件表達(dá)式兩路分支中哪一路最可能發(fā)生，然后推測(cè)執(zhí)行這一路的指令，來(lái)避免流水線停頓造成的時(shí)間浪費(fèi)。如果后來(lái)發(fā)現(xiàn)分支預(yù)測(cè)錯(cuò)誤，那么流水線中推測(cè)執(zhí)行的那些中間結(jié)果全部放棄，重新獲取正確的分支路線上的指令開(kāi)始執(zhí)行，這招致了程序執(zhí)行的延遲。

在分支預(yù)測(cè)失敗時(shí)浪費(fèi)的時(shí)間是從取指令到執(zhí)行完指令（但還沒(méi)有寫(xiě)回結(jié)果）的流水線的級(jí)數(shù)?，F(xiàn)代微處理器趨向采用非常長(zhǎng)的流水線，因此分支預(yù)測(cè)失敗可能會(huì)損失10-20個(gè)時(shí)鐘周期。越長(zhǎng)的流水線就需要越好的分支預(yù)測(cè)。

一條條件跳轉(zhuǎn)指令第一次遇到，還沒(méi)有任何信息可以去預(yù)測(cè)分支。此后保持這條指令是采取還是不采取跳轉(zhuǎn)的歷史記錄，就可以作為再遇到這條指令時(shí)猜測(cè)最可能的分支。

飽和計(jì)數(shù)器（saturating counter）或者稱雙模態(tài)預(yù)測(cè)器（bimodal predictor）是一種有4個(gè)狀態(tài)的狀態(tài)機(jī)：

• 強(qiáng)不選擇（Strongly not taken）

• 弱不選擇（Weakly not taken）

• 弱選擇（Weakly taken）

• 強(qiáng)選擇（Strongly taken）

當(dāng)一個(gè)分支命令被求值，對(duì)應(yīng)的狀態(tài)機(jī)被修改。分支不采納，則向“強(qiáng)不選擇”方向降低狀態(tài)值；如果分支被采納，則向“強(qiáng)選擇”方向提高狀態(tài)值。這種方法的優(yōu)點(diǎn)是，該條件分支指令必須連續(xù)選擇某條分支兩次，才能從強(qiáng)狀態(tài)翻轉(zhuǎn)，從而改變了預(yù)測(cè)的分支。

全局分支預(yù)測(cè)器（global branch predictor）并不為每條條件跳轉(zhuǎn)指令保持專用的歷史記錄。相反，它保持一份所有條件跳轉(zhuǎn)指令的共享的歷史記錄。優(yōu)點(diǎn)是能識(shí)別出不同的跳轉(zhuǎn)指令之間的相關(guān)性。缺點(diǎn)是歷史記錄被不相關(guān)的不同的條件跳轉(zhuǎn)指令的執(zhí)行情況稀釋了（diluted）；甚至歷史記錄沒(méi)有一位是來(lái)自同一個(gè)分支指令，如果有太多的不同的分支指令。

這種方法只有在歷史緩沖區(qū)足夠長(zhǎng)，才能發(fā)揮出性能。但是模式歷史表的條目數(shù)是歷史緩沖區(qū)位數(shù)的指數(shù)量級(jí)。因此只能是在所有的條件跳轉(zhuǎn)指令間共享這個(gè)大的模式歷史表。

參考內(nèi)容：

分支預(yù)測(cè)器 - 維基百科，自由的百科全書(shū) (wikipedia.org)：

https://zh.wikipedia.org/zh-cn/%E5%88%86%E6%94%AF%E9%A0%90%E6%B8%AC%E5%99%A8

Combining Branch Predictors：

https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-TN-36.pdf