本題鏈接：

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

分支預測器通常由程序計數(shù)器和分支歷史索引的計數(shù)器表組成。表中的每個條目通常使用兩位狀態(tài)，因為一位狀態(tài)（只記住最后一個結(jié)果）沒有足夠的滯后并且太容易翻轉(zhuǎn)狀態(tài)。

這個效果不錯的兩位狀態(tài)機是一個飽和計數(shù)器，它最多可以向上計數(shù)到 3（2'b11）或向下計數(shù)到 0（2'b00），但不會環(huán)回。? “taken”結(jié)果會使計數(shù)器增加，而 “not-taken” 結(jié)果會使計數(shù)器減少。 當計數(shù)為 2 或 3（2'b1x）時，將采用預測分支。 當強偏置分支偶爾采用不同的方向時，添加一些滯后可以防止預測的翻轉(zhuǎn)。在翻轉(zhuǎn)預測之前需要在相反方向上增加兩個增量。

參考

1. ?R. Nair, "Optimal 2-bit branch predictors",?IEEE Trans. Computers, vol. 44 no. 5, May, 1995

描述

建立一個兩位飽和計數(shù)器。

當 train_valid = 1 并且?train_taken = 1 時，計數(shù)器遞增（最大為 3）。當 train_valid = 1 和 train_taken = 0 時，計數(shù)器遞減（最小為 0）。當不訓練時（train_valid = 0），計數(shù)器保持其值不變。

areset 是一個異步復位，它將計數(shù)器復位為弱不選擇 (2'b01)。 輸出?state[1:0] 是兩位計數(shù)器的值。

題目

答案

輸出波形

異步復位

向上計數(shù)，然后向下計數(shù)

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

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

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

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

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

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

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

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

• 強不選擇（Strongly not taken）

• 弱不選擇（Weakly not taken）

• 弱選擇（Weakly taken）

• 強選擇（Strongly taken）

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

參考內(nèi)容：

分支預測器 - 維基百科，自由的百科全書 (wikipedia.org)：

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

Optimal 2-bit branch predictors | IEEE Journals & Magazine | IEEE Xplore：

https://ieeexplore.ieee.org/document/381956