# Pipeline
## 1. Datapath

Take MIPS as example: Split Single-cycle **MIPS** Datapath into 5 Steps
1. IF (instruction fetch)
2. ID (instruction decode and register file read)
3. EX (execution or address calculation)
4. MEM (data memory access)
5. WB (write back)

<img src="https://hackmd.io/_uploads/HkNwE4u2C.png" width="80%">

## 2. Pipeline hazard

資源衝突或指令之間的相互依賴，可能會導致指令執行錯誤或性能下降的情況

### 2.1 Structure Hazard

不同 instruction 同時想去用同一資源，但該資源無法同時被多個 instruction 使用

<img src="https://hackmd.io/_uploads/H1ex0VEunA.png" width="60%">

- 解決方法
- 盡量讓每個 instruction 需要花的cycle 數差不多
- 每個 instruction 要在相同的 stage 用特定的 resource
- 例子：add 在第四個 stage 就已經算完可以準備 write back 了，但因為要避免 structure hazard，需要在第五個 stage 才能 write back

<img src="https://hackmd.io/_uploads/B1IkBVunC.png" width="60%">

### 2.2 Data Hazard

指令之間存在依賴性，而 pipeline 中後續指令需要前面指令的運算結果時，就會出現 data hazard

- 種類
1. True dependence → RAW (read after write)

其中一個指令需要讀取另一個指令寫入的資料

            1. ADD R1, R2, R3    # R1=R2+R3
            2. SUB R4, R1, R5    # R4=R1-R5

2. Anti-dependence → WAR (write after read)

            1. SUB R4, R1, R5    # R4=R1-R5
            2. ADD R1, R2, R3    # R1=R2+R3

在out-of-order (OOO) processor, WAR 會有hazard 問題

3. Output dependence → WAW (write after write)

            1. ADD R1, R2, R3    # R1=R2+R3
            2. SUB R1, R4, R5    # R1=R4-R5

在out-of-order (OOO) processor, WAW 會有hazard 問題

- 解決方法
- WAR, WAW
1. 確保 In-order execution
2. Register Renaming

            1. ADD R1, R2, R3    # R1=R2+R3
            2. SUB R1, R4, R5    # R1=R4-R5
        
                    ↓
            
            1. ADD R6, R2, R3    # R6=R2+R3
            2. SUB R7, R4, R5    # R7=R4-R5

- RAW
1. Insert the NOPs (no operation)
2. Forwarding (不等到第一個指令將結果寫回，直接在第一個指令完成 Execution 時將結果傳送給第二個指令的 Execution Input，這樣會比較快拿到前一筆的結果)

ex1:
<img src="https://hackmd.io/_uploads/SkRLP4u30.png" width="100%">

r1 有 RAW 問題，所以前一指令計算的 output 一出來，就直接接到下一指令計算的 input

Hardware architecture
<img src="https://hackmd.io/_uploads/HkR9wN_3C.png" width="100%">

ex2:

**forwarding沒辦法解決所有data hazard 問題**
<img src="https://hackmd.io/_uploads/HJDTwN_h0.png" width="100%">

3. Code Re-Ordering, use software to reschedule

### 2.3 Control Hazard

當遇到 branch or jump 指令時，program 的 execution path 可能改變，導致處理器在 branch decision 確定前取錯指令

- 例子: 在 cycle 4 才知道要不要 branch，可是如果要 branch 前面已經先讀了三個錯誤的 instruction 進來了
- 目標:
1. 決定 branch taken or not sooner
2. taken 的話，要能夠更快速的計算 branch address
- 方法：
1. 都先當作沒有要 branch，等真的要 branch 再把之前讀錯的 flush 掉
2. 早點決定 branch taken 或 not taken

種類

1. predict branch always taken (並早點算出branch的address)
2. predict branch always not taken
3. dynamic branch prediction: 用 branch prediction buffer 來紀錄上一次是 taken（跳） 還是 not taken（沒跳）
3. make the stall cycle useful (找別的事情做)