# Dynamic Branch Prediction
Dynamic Branch Prediction是一種處理器設計技術，用於預測程序中Branch指令的執行方向（即是否被採取）。由於Branch指令的執行方向取決於執行時期所具有的特定條件，因此這種預測通常是基於先前執行時期的Branch行為和模式。

Dynamic Branch Prediction器會根據程序的運行情況，動態地調整其預測，以提高準確性。這樣做可以減少由於Branch錯誤預測而導致的流水線中斷和性能損失。
## 1-Bit Predictor: Shortcoming

1-Bit Predictor是一種非常簡單的Branch Predictor，它僅使用一個位元（通常是1或0）來預測Branch指令的執行方向。當Branch指令執行時，這個位元會記錄上次該Branch指令的執行情況，以便下次執行時使用。當這個位元為1時，表示上次Branch指令被執行並採取Branch；當位元為0時，表示上次Branch指令未被執行，或者採取了另一個Branch。

1-Bit Predictor的缺陷在於其容易產生內部循環Branch（inner loop branches）錯誤預測（misprediction）。


內部循環中的Branch指令在最後一次迭代時被誤判為被採取（taken），這會導致在該迭代的結尾處執行外部循環中的Branch指令。接下來，當下一次迭代開始時，如果Branch Predictor仍將其誤判為未被採取（not taken），就會導致錯誤的Branch預測。

#### 舉例來說：

外部循環：
for (int i = 0; i < 10; i++) {
    內部循環：
    for (int j = 0; j < 5; j++) {
        if (condition) {
            // do something
        }
    }
}

在這個例子中，內部循環被執行5次，而外部循環被執行10次。假設在內部循環的Branch 條件（if條件）在第5次迭代時首次為true，但在下一次迭代時為false。

現在，我們使用1位預測器來預測這個Branch 的執行方向。當我們執行第一次內部循環時，Branch 條件為true，Branch 預測器會誤判為Branch 會被採取（taken）。因此，外部循環的Branch 指令也會被執行。

接下來，當我們執行第二次內部循環時，Branch 條件為false，但由於Branch 預測器仍然記錄著上一次Branch 被採取的情況，它會再次誤判為Branch 會被採取。因此，外部循環的Branch 指令再次被執行，導致了錯誤的Branch 預測。

這種情況下，1位預測器的缺陷在於它無法記憶Branch的歷史，只能記錄上次的執行情況，並且無法根據Branch的上下文進行更精確的預測。這樣的缺陷導致在內部循環中經常發生Branch預測錯誤，從而影響程序的執行效率。
## 2-Bit Predictor
1-Bit Predictor是一種改進的Branch Predictor，相對於 1-Bit Predictor，在預測Branch指令的執行方向上提供了更多的信息。它使用兩個位元來記錄Branch指令的執行歷史，以更準確地預測Branch指令的執行方向。

2-Bit Predictor通常使用有限狀態機（Finite State Machine, FSM）來實現。根據先前的Branch行為，它可以進行如下的預測：

* 強烈採取（Strongly Taken）：表示該Branch指令很可能被採取。
* 弱採取（Weakly Taken）：表示該Branch指令可能被採取，但不是非常確定。
* 強烈不採取（Strongly Not Taken）：表示該Branch指令很可能不被採取。
* 弱不採取（Weakly Not Taken）：表示該Branch指令可能不被採取，但不是非常確定。

2-Bit Predictor的優點包括：

* 更準確的預測：相對於1-Bit Predictor，2-Bit Predictor提供了更多的預測信息，因此能夠更準確地預測Branch指令的執行方向。

* 能夠適應Branch模式的變化：由於2-Bit Predictor可以記錄多個Branch模式，因此可以更靈活地適應Branch模式的變化，提高了預測的準確性。

* 簡單且有效：雖然比1-Bit Predictor複雜一些，但2-Bit Predictor的實現相對簡單，並且在提供更好的預測準確性的同時，佔用的資源也不會過多。

## Calculating the Branch Target
計算Branch Target是在Branch 指令的執行過程中決定下一個執行位置的關鍵步驟。即使使用了Branch 預測器，仍然需要計算Branch Target。在許多處理器中，Branch 指令的執行會產生1個時脈週期的開支，尤其是當Branch 預測錯誤時。為了減少這種開支，通常會使用Branch 目標緩存（Branch Target Buffer, BTB）來加速Branch Target的計算。

Branch 目標緩存是一種高速緩存，用於存儲Branch 指令的目標地址。當執行Branch 指令時，處理器會將當前的程式計數器（PC）作為索引，查找Branch 目標緩存中相應的項目。如果命中並且Branch 預測器預測該Branch 會被採取，那麼處理器可以立即從Branch 目標緩存中取得目標地址，而不必等待Branch 指令的執行結果確定。

這樣一來，即使在Branch 預測錯誤的情況下，如果Branch 目標緩存能夠提供正確的目標地址，就可以避免額外的時脈週期開支，從而減少了Branch 預測錯誤的影響。這使得處理器可以更快速地恢復並繼續執行程序，從而提高了整體的執行效率。

## Delayed Branch
Delayed Branch是一種處理器設計技術，用於減少Branch指令所帶來的性能損失。當處理器執行一條Branch指令時，它通常需要等到Branch指令的執行結果確定後才能繼續執行下一條指令。然而，如果處理器能夠預先執行Branch指令後的幾個指令，而不等待Branch結果，這樣就可以充分利用處理器的流水線，減少Branch指令帶來的延遲。