iT邦幫忙

2021 iThome 鐵人賽

DAY 2
0
Software Development

微自幹的作業系統輕旅行系列 第 7

淺談分支預測與 Hazards 議題

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

Hazards

  • Structural Hazards

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

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

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

  • Data Hazards

    假設有兩個算數指令,分別是 ADDSUB ,並且 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, forloop 通常都會重複執行一次以上。假設它一定會向後跳轉,只要在迴圈執行超過兩次的狀態下就能出現成效。
    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


上一篇
透過 RISC-V 模擬器搞懂指令管線化
下一篇
IEEE-754 與浮點數運算
系列文
微自幹的作業系統輕旅行38

尚未有邦友留言

立即登入留言