---
# System prepended metadata

title: Chapter_3 Pipeline
tags: [Computer Architecture]

---

# 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)
        
        其中一個指令需要讀取另一個指令寫入的資料
        
        ```python
            1. ADD R1, R2, R3    # R1=R2+R3
            2. SUB R4, R1, R5    # R4=R1-R5
        ```
        
    2. Anti-dependence → WAR (write after read)
        ```python
            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)
        ```python
            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
        
        ```python
            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 (找別的事情做)