1 6 淺談分支預測與 Hazards 議題 - ianchen0119/AwesomeCS GitHub Wiki

本篇章介紹經常發生在 Pinpline 上的潛在傷害 (Hazards) 以及針對各種 Case 所設立的解決機制。

Hazards

  • Structural Hazards

    在同一個 Clock Cycle 中，若 Pipeline 有兩個以上的指令需要使用同一個資源，便會產生 Structural Hazards 的問題。如此一來，後面的指令便會需要延後放入流水線，造成處理器無法在理想狀況下運行(一個 Cycle 處理一條指令)。

    該情況又稱為流水線泡沫化。

    為避免該狀況發生，在處理器設計階段時必須考慮設置兩個以上的 Data Unit 去處理指令以及資料的記憶體操作。或是將 Instruction 和 Data 的快取區隔開來。

  • Data Hazards

    假設有兩個算數指令，分別是 ADD 和 SUB ，並且 SUB 的輸入資料是 ADD 的輸出資料。若 SUB 在執行時， ADD 處理的結果還沒有被寫回記憶體，便會造成 Data Hazards 。

    細節可以參考 NCTU OCW 的 9:10 處。

    若不希望兩個指令中間有太多的閒置週期，可以利用 Forwarding 的技術解決，請見下圖。

    Forwarding

    其主要概念是: 不等到第一個指令將結果寫回，直接在第一個指令完成 Execution 時將結果傳送給第二個指令的 Execution Input 。

    圖片取自 slideshare 。

    Fowarding 確實能夠解決上述的 Case ，不過仍然會遇到流水線泡沫化的情況產生，像是:

    • Load-Use Data Hazards 若第一個指令為 Load 類型，則須要等到 Memory Access 階段才能將結果 Forward 給後一個指令的 Execution 。

    細節可以參考 NCTU OCW 的22:16 處。

    因此，我們日常開發所使用的編譯器都會對程式語言做 Code Re-Ordering 減少流水線泡沫化的狀況產生，簡單的舉例如下: 若在 C 程式碼中有兩項加法操作:

    int a = b + e;
int c = b + f;

    若我們真的按照程式碼的邏輯工作，計算機會這樣處理我們的程式:

    1. 讀取 b 變數所存放的值並放到 register 1。
    2. 讀取 e 變數所存放的值並放到 register 2。
    3. 將兩項 register 存放的值相加並放入 register 3。
    4. 將 register 3 的值寫回記憶體。
    5. 讀取 f 變數所存放的值並放到 register 4。
    6. 將兩項 register 存放的值相加並放入 register 5。
    7. 將 register 5 的值寫回記憶體。

    若這樣做，即使有 Forwarding 還是會在 2. 和 3. 之間以及 5. 和 6. 之間產生泡沫化的狀況。一共需要 13 個 Clock Cycle 才能完成。

    詳細計算方式如下: 第一個指令需要等待完整的流水線週期: 5 之後每個指令需要等待一個週期: 6 一共產生了兩次泡沫化: 2

    而聰明的編譯器會將我們的程式碼做編排優化:

    1. 讀取 b 變數所存放的值並放到 register 1。
    2. 讀取 e 變數所存放的值並放到 register 2。
    3. 讀取 f 變數所存放的值並放到 register 4。
    4. 將兩項 register(1,2) 存放的值相加並放入 register 3。
    5. 將 register 3 的值寫回記憶體。
    6. 將兩項 register(1,4) 存放的值相加並放入 register 5。
    7. 將 register 5 的值寫回記憶體。

    在搭配 Forwarding 的前提下，我們就可以避免泡沫化的問題發生，加速程式碼的運作。

  • Control Hazards

    Control hazards 發生在處理器被要求作條件分支時，做條件分支分析需等到條件需求被運算出來，才知道要執行的下一條指令位置，而在 pipeline 的處理過程中可以先利用 Branch prediction 猜測下一條指令。如果判斷錯誤會造成的暫存器資料改變，需要還原回來以及對 pipeline 做清空的操作，十分浪費效能。

Branch prediction

Branch prediction 主要有兩類:

  • Static Branch prediction 靜態的分支預測不會根據條件來調整策略，最常見的有:
    1. loop 一律猜測會往前跳 (backward branch is taken) 。 由於 while, for 等 loop 通常都會重複執行一次以上。假設它一定會向後跳轉，只要在迴圈執行超過兩次的狀態下就能出現成效。
    2. if-else 一律猜測不會進行跳轉 (forward branch is not taken) 。 不論是一個條件分支或是多個條件分支，一定只有一個分支會如期運行，其他不符合條件都會向前進行轉跳。

      為避免大家搞混前後的定義，特別補充一下。 向前跳轉的定義: 跳轉後指令的位置大於目前指令。 向後跳轉的定義: 跳轉後指令的位置小於目前指令，也就是往回跳。

  • Dynamic Branch prediction 動態的分支預測會根據不同的使用情況做出調整。假設程式碼當中用了 100 次 BEQ 條件轉跳指令，動態分支預測會為 100 個 BEQ 指令個別建立歷史紀錄。這麼做的原因是: 不同的 BEQ 的比較條件不盡相同，若這 100 個指令都參照同一個歷史紀錄，會造成大量的錯誤預測，導致處理器需要反覆的清空流水線。

二位元飽和計數器

由於現今的處理器多採用動態分支預測提高處理器的工作效率，本節就特別以飽和計數器為例，向大家介紹最簡單的動態預測策略。

二位元飽和計數器

圖片來源: Link 。

計數器一共有 4 個狀態機，其狀態分別是:

MSB LSB
0 0
0 1
1 0
1 1

若 MSB == 0 不轉跳， 反之，若 MSB == 1 則轉跳。 這樣子做的好處是: 不會因為犯錯一次就改變想法，假設原本預測不轉跳，那必須要連續猜錯兩次才會改變想法。

如果設計者希望計數器猜錯更多次才改變想法，我們可以將計數器從二位元增加至三位元，甚至是更多位元。不過，一昧的增加位元不一定能帶來更好的性能。

Reference