---
# System prepended metadata

title: CPU-ORG 1-2-3
tags: [School]

---

# CPU-ORG 1-2-3

# Pipeline

```MIME=
add $t1, $t2, $t3
add $t4, $t5, $t6
```
![](https://hackmd.io/_uploads/r16k-wi8n.png)

1. Pipeline 分為 5 階段: `IF`->`ID`->`EX`->`MEM`->`WB`

2. 當第一個指令執行到第二階段時，讓第二個指令執行第一階段，依此類推

3. 指令要到 `WB` 階段結束後才會輸出結果

## Pipeline 實際架構

![](https://hackmd.io/_uploads/B1ZJJdjUh.png)

- 整個架構被 4 道牆(`閘門`)分成五等分

- 每個牆實際上都是一組暫存器，把前一個階段輸出的值存在裡面，並在某個時間統一輸出給下一個階段

    > 有控制訊號可以控制

### 問題

- 假設現在執行的指令為 `add $t1, $t2, $t3`，則當此指令執行到 `WB` 時，須將 `$t2 + $t3` 的值存回 `Register`，也就是需要再執行一次 `ID` 階段，但這有可能造成這個指令跟後面指令同時執行 `ID` 而衝突

### 解決

- 把控制訊號也存到 `"牆"` 內，這樣在往回的時候也可以同時使用控制訊號來 `插入` 指令

# Hazard

## Structure Hazard

![](https://hackmd.io/_uploads/r1RoSAaIn.png)

- `Line 1` 需要存取資料到記憶體

- `Line 4` 需要從記憶體提取指令

- 如果記憶體只有一個時，就會導致兩邊互相爭奪存取權，進而導致兩邊都無法執行

### Solution

- 增加硬體數量，把 Memory 增加為兩個：
    
    1. Data Memory 

    2. Instraction Memory

- Cache 也分為：

    1. Data Cache (D-Cache)
    
    2. Instraction Cache (I-Cache)

## Pipeline Hazard

### Problom 1

- 根據 `#Pipeline 2.` 如果下一個指令需要使用到前一個指令的輸出時，就會發生錯誤

    ```MIME=
    add $t1, $t2, $t3
    add $t4, $t1, $t5
    ```
    > Line 2 的 `EX` 階段需要使用到 Line 1 的輸出結果 (`$t1`) 做為輸入，但 Line 1 需要執行完 `WB` 階段才能輸出 `$t1`，因此 Line 2 的執行結果就會出錯
    > 
    > ![](https://hackmd.io/_uploads/Sylrv8sI3.png)

### Solution 1 - `Bubble`

- 在 Line 1 跟 Line 2 之間，插入 n 個 `Bubble` 指令，讓 Line 2 可以多延遲 n 個階段
    
    > 實際上 Bubble 也是一個指令，但可以是任意的，只要不影響執行結果即可
    > 任何指令只需要插入 `2個 Bubble` 就可以解決
    >
    > ![](https://hackmd.io/_uploads/HJ0v6LjL3.png)
    
### Solution 2 - `By Passing`

- 讓第一個指令在 `EX` 計算完後，直接把計算結果`傳送 (Passing)` 給下一個指令

    > 可以解決 `Bubble` 太浪費時間的問題
    > 
    > ![](https://hackmd.io/_uploads/r1SIwLoLh.png)

---

### Problom 2

- `Problom 1` 的延伸，如果前一行指令 (如`lw`) 要到 `MEM` 階段執行結束後才會有結果產生，則無法在下一行指令執行到 `EX` 前 Passing 給他

    ```MIME=
    lw $t1, 4[$t2]
    add $t3, $t1, $t4
    ```
    > `lw` 指令為讀取記憶體，所以需要到 `MEM` 階段後才會有輸出，但在 Line 1 執行完 `MEM` 階段時，Line 2 已經執行完 `EX` 階段了...
    > 
    > ![](https://hackmd.io/_uploads/r19C9LoU2.png)


### Solution 3 - `Bubble + By Passing`

- 結合 `Bubble` 跟 `By Passing`，這樣一來，最多只需使用 `1個 Bubble`

    > ![](https://hackmd.io/_uploads/S1rV2UsLn.png)

---

### Solution 4 - `Code Scheduling`

- 前面有說 `Bubble` 實際上也是一行指令，只是他沒有用，那何不放一行`有用的指令`在原本要放 `Bubble` 的位置呢？

    > 因為太難 Coding，但有能力的話，也是可以這樣做的

## Control Hazard

### Predict

- 分為 **Static、Dynamic**

    - **Static**：須依據規定撰寫程式
    - **Dynamic**：下述方法皆為 `Dynamic Predict`

---

### Problom 1

- 發生在 `Branch 指令` 時，如果在做 `if` 指令時，先做了下一個指令，萬一不符合 `if` 條件，則用不到下一行，而是要直接跳到 `整個 if 區塊後`
    
    ```MIME=
    LOOP: beq  $t1, $t2, END
          addi $t1, $t1, 1
          add  $t3, $t3, $t1
          j    LOOP
    END:  sw   $t1, 4[$t4]  
          and  $t1, $t1, $zero
    ```
    > ![](https://hackmd.io/_uploads/SkNqGPi83.png)


### Solution 1 - `無視`

- 如果符合 `if` 那就沒問題
- 如果不符合，則下一行指令直接當作 `Bubble`

    > ![](https://hackmd.io/_uploads/BJNz7DjU2.png)
    > 
    > Line 1 可以直接在 ID 階段比較兩個值的大小 (Flushing)

---

### Problom 2

- 使用 `Solution 1` 時，會多出一個 `Bubble`，但有可能我們不需要用到那個 `Bubble`

### Solution 2 - `1-bit Predict`

- 用 `1 bit` 去存上次執行到這個 `Branch` 時的狀態 `(True/False)`，下一次執行時，用這個 bit 去決定要把 Line 2 還是 Line N 放到 Pipeline 中

    > ![](https://hackmd.io/_uploads/HJH2qwsLh.png)


---

### Problom 3

- `Solution 1` 的預測正確率太低

### Solution 3 - `2-bit Predict`

- 改用`2 個 Bits` 去做預測 `(依照 MSB)`

    | MSB | LSB | Predict |
    | -------- | -------- | -------- |
    | 0 | 0 | no jump |
    | 0 | 1 | no jump |
    | 1 | 0 |    jump |
    | 1 | 1 |    jump |
    
    > 需要`連續`兩次猜測錯誤時，才改變猜測結果

# Cache

## Address

- 以 `1 byte` 為基礎
- `1 word` = `4 bytes`
- `block` 大小不固定，但考試以 `1 block` = `2 words` 為主
    
    > 相對於 `Memory` 以 `Addressable` 的方法傳輸資料，`Catch` 則是以 `block` 來實現

- Catch 以 `block` 為單位

## Locality

### Temporal Locality

- 時間區域性

- 現在使用的資料，等一下也會用到

### Spatial Locality

- 空間區域性

- 基本上就是把資料分成一塊一塊的(`block`)，每次拿資料都以塊(`block`)為單位

    ```python=
    def get_data_by_rows(data:list):
        for i in len(data):
            for j in len(data[i]):
                sum += data[i][j]
        return sum
    
    def get_data_by_cols(data:list):
        for j in len(data):
            for i in len(data[0]):
                sum += data[i][j]
        return sum
    ```
    
    > `get_data_by_rows` 的 locality 較**好**，因為資料是**照記憶體順序**抓的
    > `get_data_by_cols` 的 locality 較**差**，因為資料是**跳著**抓的

## Direct Mapped

![](https://hackmd.io/_uploads/rklQGu28h.png)
- 如果用二進制來看，可以發現**後兩個 bit** 相同的 word 都在同一個 block，而且剛好是他們在的 Block 的 `Index`
    
    > 0 ： 00 **00**
    > 4 ： 01 **00**
    > 8 ： 10 **00**
    > 12：11 **00**

- 且**前兩個 bit** 正好是該 Word 的 `Tag`

- **若 Cache 有 8 個 Block，則是以後三個 bit 相同的為一組**

    > $8 = 2^3$

#### 例題

- CPU 請求一個 Byte Address 為 38 的資料:

    1. `Byte Address 38` 為 `第 9 個 Word`
        > `floor(38 / 4) = 9`
    
    2. `第 9 個 Word` 對應到`第 1 個 Cache Block (Index 1)`
        > `9 % 4 = 1`
    
    3. `第 9 個 Word` 對應到 `Tag 2`
        > `floor(9 / 4) = 2`

### Byte Offset

![](https://hackmd.io/_uploads/B12rGAaU2.png)
 
- `Memory` 以 `Byte` 為單位

- `Cache` 以 `Block` 為單位

- 假設 `1 Block` = `1 Word`，`1 Word` = `4 Bytes`

- 所以 Memory 的 `Byte Address / 4` 就是少掉 `兩個 Bit`，而這 `兩個 Bit` 就是 `Offset`

- `Byte Offset` 會隨著不同的 `Block 大小` 改變而改變

### Valid bit

- 有些情況會導致 `Tag` 跟 `Data` 不匹配，例如：重開機

- `Valid bit` 用來防止不匹配的情況

- `Valid bit` 的初始狀態皆為 `0`

- 當某個 Block 的 `Valid bit` 為 `0` 時，代表該 Block 無效，CPU 會直接去 Memory 找資料，並把資料複製到 Cache，再把 `Valid bit` 設為 `1`

- 當 Block 的 `Valid bit` 為 `1` 時，代表該 Block 資料正確，可以直接取用

### Hit

:::success
找得到資料
:::

- CPU 需要的資料有在 Cache 中，並且在正確位置

### Miss

:::danger
找不到資料
:::

- CPU 需要的資料不在 Cache 中

- CPU 需要的資料在，但 Tag 錯誤

- CPU 需要的資料應該在的 Block 的 Valid bit 為 0



- 為了解決 `Structure Hazard`，所以 `Cache` 有兩種，因此 `Miss` 也分為兩種情況：
    
    ![](https://hackmd.io/_uploads/r1-N3AT8n.png)
    1. **Data Cache Miss**：發生在 `MEM` 階段 (指令抓不到資料)
    
    2. **Instraction Cache Miss**：發生在 `IF` 階段 (抓不到指令)

#### Data Cache Miss Solution

1. 暫停正在執行的指令

2. 等待直到抓到資料

3. 繼續執行下一階段 (`WB`)

#### Instraction Cache Miss Solution

- 重抓一次指令 (從 `IF` 重新執行)，直到抓到指令 (`Hit`)

### Hit / Miss 統整

![](https://hackmd.io/_uploads/SyB5SzAUn.png)


#### **Write Through** 寫穿
    
![](https://hackmd.io/_uploads/rJ41qz0L2.png)

- 更改資料時，把 `Memory` 跟 `Cache` 內的資料也改變
    > 缺點：速度極慢，且會無法發揮 `Cache` 的用途 (必須等 `Memory` 寫完才可以繼續執行)

    - Write Buffer：建立一個緩衝區讓 `CPU` 無需等待，但如果緩衝區滿了，還是需要等待

#### **Write Back** 寫回
    
![](https://hackmd.io/_uploads/S1Kx_fAU2.png)

- 只把新資料寫到 `Cache`，然後用一個 `Dirty bit` 把該 `block` 標記為 `Dirty Block`，在有其他 `Tag` 的資料要取代 `Dirty Block` 的時候才對 `Memory` 做更新

    - **Dirty Bit**：用來標記該 `Block` 是否為 `Dirty Block`，更新完後 `歸 0`

    - **Dirty Block**：該 `Block` 的資料是否有被更新過 (和 `Memory` 不一致)

## Associative Caches

- 關聯式快取

- 依照 `Direct Mapped` 的邏輯，如果每次都剛好呼叫到不同 `Tag` 相同 `Index` 的資料，就會導致其他 `Index` 的空間持續閒置，浪費了其他 `Index` 的空間

- 而 `Associative Caches` 就是把那些空間做利用，用 `Set Index` 進行分組，雖然增加了單次的搜尋時間，但提昇了 `Cache` 的利用率

- 使 `Miss Rate` 降低

#### n-Way Set Associative

- `n` 代表 `n Blocks per Set`

- 假設是 `2-Way Set Associative`，則代表每個 `Set` 有兩個 `Block`

- 假設 `Cache` 總共有 `8 個 Block`

![](https://hackmd.io/_uploads/BJv_Edkv2.png)


#### Fully Associative Cache

- 整個 `Cache` 只有 `1 個 Set`

- 利用率高，`Miss Rate` 低

- 相對的，搜尋時間很長

### Example

- 以 `2-Way Set Associative` 為例：
    
    ![](https://hackmd.io/_uploads/SkjU9TC8h.png)

- 假設序列為 `3` -> `4` -> `0` -> `8` -> `5` -> `3` -> `9`

    ![](https://hackmd.io/_uploads/B17FcpCLh.png)

- 第一步：`放入 3`

    ![](https://hackmd.io/_uploads/BJzpqaR8h.png)

- 第二步：`放入 4`

    ![](https://hackmd.io/_uploads/S1AJs60Ln.png)

- 第三步：`放入 0`

    ![](https://hackmd.io/_uploads/BySDs6RI3.png)

- 第四步：`將 4 取代為 8`

    ![](https://hackmd.io/_uploads/HyI_s6C83.png)

- 第五步：`放入 5`

    ![](https://hackmd.io/_uploads/rJQYsa0Ln.png)

- 第六步：`找到 3` -> `HIT!`，所以不動作

    ![](https://hackmd.io/_uploads/H1xcopA82.png)

- 第七步：`將 5 取代為 9`

    ![](https://hackmd.io/_uploads/S1pqspAIh.png)

- 共 `Hit 1 次`，`Miss 6 次`

- 如果是用 `Direct Mapped`，則是 `Hit 0 次`，`Miss 7 次`

### Replacement Policy (替換規則)

#### Least-Recently Used (LRU)

- 簡單來說就是把最久沒有被使用到的資料替換掉
    
    > 前面的範例就是用 LRU
    
#### Random

- 隨機替換

- 優點：使用的資源比 `LRU` 少

- 缺點：不符合 `Locality`

## Memory Bandwidth
![](https://hackmd.io/_uploads/HyGEMkywn.png)
![](https://hackmd.io/_uploads/rJMPMkkvh.png)

- One Word Wide：Memory 每次只能傳 1 Word 給 Bus

- Wider：Memory 每次可以提取 n 個 Word 並一次傳給 Bus，但硬體成本貴

- Interleaved (交錯)： 每次可以提取 n 個 Word，但每次只能傳 1 個 Word 給 Bus

### Example

- 假設有 4 Words 要傳
- 假設 Wider 模型為 4 Word Wide
- 假設 Memory 讀取 1 Word 需要 15 Cycle
- 假設 Memory 傳 1 Word 給 Bus 需要 1 Cycle

### Solution

#### One Word Wide

- `1 (Request to Bus)` + `15 * 4(Read Memory 4 times)` + `1 * 4 (Memory transfer data to Bus 4 times)` = `65 Cycles`

#### Wider 

- `1 (Request to Bus)` + `15` + `1` = `17 Cycles`
> 15 不用乘 4 是因為每次可以讀 4 Words

#### Interleaved

- `1 (Request to Bus)` + `15` + `1 * 4 (Memory transfer data to Bus 4 times)` = `20 Cycles`
> 15 不用乘 4 是因為每次可以讀 4 Words
> 但每個 Word 還是需要分開傳給 Bus，所以 1 * 4