# CPU-ORG 1-2-3
# Pipeline
```MIME=
add $t1, $t2, $t3
add $t4, $t5, $t6
```
1. Pipeline 分為 5 階段: `IF`->`ID`->`EX`->`MEM`->`WB`
2. 當第一個指令執行到第二階段時，讓第二個指令執行第一階段，依此類推
3. 指令要到 `WB` 階段結束後才會輸出結果
## Pipeline 實際架構
- 整個架構被 4 道牆(`閘門`)分成五等分
- 每個牆實際上都是一組暫存器，把前一個階段輸出的值存在裡面，並在某個時間統一輸出給下一個階段
> 有控制訊號可以控制
### 問題
- 假設現在執行的指令為 `add $t1, $t2, $t3`，則當此指令執行到 `WB` 時，須將 `$t2 + $t3` 的值存回 `Register`，也就是需要再執行一次 `ID` 階段，但這有可能造成這個指令跟後面指令同時執行 `ID` 而衝突
### 解決
- 把控制訊號也存到 `"牆"` 內，這樣在往回的時候也可以同時使用控制訊號來 `插入` 指令
# Hazard
## Structure Hazard
- `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 的執行結果就會出錯
>
> 
### Solution 1 - `Bubble`
- 在 Line 1 跟 Line 2 之間，插入 n 個 `Bubble` 指令，讓 Line 2 可以多延遲 n 個階段
> 實際上 Bubble 也是一個指令，但可以是任意的，只要不影響執行結果即可
> 任何指令只需要插入 `2個 Bubble` 就可以解決
>
> 
### Solution 2 - `By Passing`
- 讓第一個指令在 `EX` 計算完後，直接把計算結果`傳送 (Passing)` 給下一個指令
> 可以解決 `Bubble` 太浪費時間的問題
>
> 
---
### 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` 階段了...
>
> 
### Solution 3 - `Bubble + By Passing`
- 結合 `Bubble` 跟 `By Passing`，這樣一來，最多只需使用 `1個 Bubble`
> 
---
### 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
```
> 
### Solution 1 - `無視`
- 如果符合 `if` 那就沒問題
- 如果不符合，則下一行指令直接當作 `Bubble`
> 
>
> 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 中
> 
---
### 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
- 如果用二進制來看，可以發現**後兩個 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
- `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` 也分為兩種情況：
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 統整
#### **Write Through** 寫穿
- 更改資料時，把 `Memory` 跟 `Cache` 內的資料也改變
> 缺點：速度極慢，且會無法發揮 `Cache` 的用途 (必須等 `Memory` 寫完才可以繼續執行)
- Write Buffer：建立一個緩衝區讓 `CPU` 無需等待，但如果緩衝區滿了，還是需要等待
#### **Write Back** 寫回
- 只把新資料寫到 `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`
#### Fully Associative Cache
- 整個 `Cache` 只有 `1 個 Set`
- 利用率高，`Miss Rate` 低
- 相對的，搜尋時間很長
### Example
- 以 `2-Way Set Associative` 為例：
- 假設序列為 `3` -> `4` -> `0` -> `8` -> `5` -> `3` -> `9`
- 第一步：`放入 3`
- 第二步：`放入 4`
- 第三步：`放入 0`
- 第四步：`將 4 取代為 8`
- 第五步：`放入 5`
- 第六步：`找到 3` -> `HIT!`，所以不動作
- 第七步：`將 5 取代為 9`
- 共 `Hit 1 次`，`Miss 6 次`
- 如果是用 `Direct Mapped`，則是 `Hit 0 次`，`Miss 7 次`
### Replacement Policy (替換規則)
#### Least-Recently Used (LRU)
- 簡單來說就是把最久沒有被使用到的資料替換掉
> 前面的範例就是用 LRU
#### Random
- 隨機替換
- 優點：使用的資源比 `LRU` 少
- 缺點：不符合 `Locality`
## Memory Bandwidth
- 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
Sign in with Wallet
Connect another wallet