本篇章介紹經常發生在 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 的技術解決，請見下圖。

  

  其主要概念是: 不等到第一個指令將結果寫回，直接在第一個指令完成 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 == 0 不轉跳，
反之，若 MSB == 1 則轉跳。
這樣子做的好處是: 不會因為犯錯一次就改變想法，假設原本預測不轉跳，那必須要連續猜錯兩次才會改變想法。

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

Reference

• CPU 的分支預測器是怎樣工作的？
• 維基百科-分支預測器
• NCTU OCW
• 南京大學計算機組織投影片