# 處理 Hazard

上次有提到處理 Hazard 時會用到 Latch，下面就是要介紹他實際是如何運作的。

# Data hazard

分成兩種，一種是「不是 Load」的，一種是「是 Load」；原因差在於「值算出來的時間點不同」

如果回憶上次的圖：

<iframe src="https://drive.google.com/file/d/1KVbsIdw0RRXWWRXaw9uf8dtePHantg4l/preview" height="580"></iframe>

## Load-use hazard

如果當前指令是「Load」，只有到了 MEM/WB 值才會出來，但是如果是他的下一條指令就要用到該值做計算，會發現來不及送回去給 ALU，[因此一定要等待](https://hackmd.io/VRFmQAXuS3SIiCnVy-J3nw?view#%E8%A7%A3%E6%B3%95%E4%BA%8C%EF%BC%9AStall)。

## 計算類的 data-hazard

這種可以用 Data Foward 處理。

因為 EX 階段計算好的值還需要經過 ==EX/MEM== 跟 ==MEM/WB== 兩個 Latch，才會送回去寫入 Register File，所以如果後面的指令有人要用這個尚未寫入的值，就要從 ==EX/MEM== 跟 ==MEM/WB== 這兩個 Latch 的輸出端(擋水閘流出端，或者說 Latch 的右半部)去拿

# Data Forwarding

用來處理計算類的 data-hazard。因為需要判斷有沒有用到相同的 reg，所以 latch 之間還需要傳遞 reg 的編號。

## EX Hazard

如果 ID/EX 需要使用到位於 EX/MEM 裡面的值，叫做 EX Hazard，下面的三個條件都要是 True 才會採用 EX/MEM 裡面的值：

- `EX/MEM.RegWrite = 1`
- 這條是在確保真的是一個「寫回指令」
- `EX/MEM.RegisterRd ≠ 0`
- 這條是在確保存入的 REG 不是第 0 個 REG
- 因為有規定 `x0` 不會被寫入任何值，他永遠是 0
- `EX/MEM.RegisterRd=ID/EX.RegisterR1`
- 檢查 ID/EX 裡要使用的 R1 跟 EX/MEM 要寫入的 Rd 是同個人
- `RegisterRd` 算是紀錄 `Rd` 的地址，用來判斷他是哪個 REG；`RegisterR1` 同理

:::warning
`R2` 也是有可能發生 hazard 的，所以 R2 也要做一樣的判斷
:::

## MEM Hazard

如果 ID/EX 需要使用到位於 MEM/WB 裡面的值，叫做 MEM Hazard，下面的**四個**條件都要是 True 才會採用 MEM/RB 裡面的值：

- `MEM/WB.RegWrite = 1`
- 這條是在確保真的是一個「寫回指令」
- `MEM/WB.RegisterRd ≠ 0`
- 這條是在確保存入的 REG 不是第 0 個 REG
- 因為有規定 `x0` 不會被寫入任何值，他永遠是 0
- `MEM/WB.RegisterRd=ID/EX.RegisterR1`
- 檢查 ID/EX 裡要使用的 R1 跟 EX/MEM 要寫入的 Rd 是同個人
- `RegisterRd` 算是紀錄 `Rd` 的地址，用來判斷他是哪個 REG；`RegisterR1` 同理
- `Not(Has EX Hazard)`
- 也就是把上面 EX Hazard 的判斷整坨放進來取 NOT
- 情境是這樣的，如果 A、B、C 是照順序的三個指令，B 跟 C 都會寫回到同一個 rd，而 A 會用到那個 rd
- 這時候 A 應該要使用的是位於 EX/MEM 裡面的 rd 值(C 指令的)，而不是 MEM/RB 的 Rd 值
- 但是如果單看上面三個判斷會發現無法判別出來，因此需要多加這條判斷

:::warning
`R2` 也是有可能發生 hazard 的，所以 R2 也要做一樣的判斷
:::

## 電路圖

下圖是實作這個判斷邏輯後的電路圖，它叫做 Forwarding Unit。

<iframe src="https://drive.google.com/file/d/1uyzcPHIHFRQ_4hGuBMhk_pwAYpAInrGA/preview" height="480"></iframe>

可以看到指向他的箭頭有上面用來判斷的那些人，像是 `EX/MEM.RegWrite`、`MEM/RB.RegWrite` 等等。

然後可以發現，我們將 ALU 的兩個輸入都加上了改良過的 MUX，有 2 個 bit 用來判斷；預設上來說，由上到下分別是 00、01、10、11。

而這 4 個值，除了 11 沒有用到，其他 3 個分別代表：

- `00`：使用當前 ID/EX 的值
- `01`：EX/MEM 傳過來的值
- `10`：MEM/RB 傳過來的值

:::warning
此時要注意，之前的 Rs2 原本應該就會有一個 MUX 用來判斷他是要用 IMM 或 Rs2，這裡為了不讓電路圖更亂，所以沒有畫入這個部分。
:::

:::info
- 對應之前 **上一條** 指令 or **上上一條** 指令可以 forward 給當前這條指令
- 因為當前指令運行時可以從 **上一條** 指令的 latch(EX/MEM) or **上上一條** 指令的 latch(MEM/WB) 拿資料來判斷
:::

# Load-use data hazard

這是 Load 所導致的危害，只能靠等待一個 cycle 解決；或是先透過編譯器幫我們調換順序。

而判斷條件比較簡單：

- `ID/EX.MemRead = 1`
- 也就是說確保這是條 `Load` 指令
- `ID/EX.RegisterRd = If/ID.RegisterRs1`
- 檢查有沒有發生 Dependency
- 當然也不要忘記還有 `Rs2`

而檢查到危害發生後，比較有趣的是如何「Stall」

## Stall

所謂的停下來，其實就是：

1. 把 PC 的值(IF 階段的指令)跟 IF/ID 裡面的值(跟 load 指令相依的指令)先「凍結」起來
- 為此，我們新設計了兩個 flag：
- `IF/IDWrite`：用來判定當前 `IF/ID` 內容要不要更新
- `PCWrite`：用來判定當前 `PC` 要不要更新
3. IF/ID 傳入的 Flag 都改成傳入 0

電路圖如下：

<iframe src="https://drive.google.com/file/d/11IhAGHdEMn6RG6n_EuVlCrVbRktlYPkm/preview" height="580"></iframe>

可以看到這個叫做 Hazard detection unit，他傳入的很簡單，就四個內容：三個 REG 的地址，跟 1 個 `ID/EX.MemRead`。
- 從 ID/EX 這個 latch 拉出來的就是 load 指令的內容
- 從 IF/ID 這個 latch 拉出來的就是會用到 load 指令的 rd 的指令的內容

有趣的是他拉出來的線路，首先可以看到他拉了`IF/IDWrite` 跟 `PCWrite`給 IF/ID 跟 PC，來決定要不要凍結資料；然後在 ID/EX 的 Control signal 部分，那三「組」訊號都改成要先經過一個 MUX。

- MUX 預設值就是選從 Control Unit 送過來的
- 但如果上面判斷出需要停下一個 cycle，則 Hazard detection unit 會送出訊號 1 過來，讓 MUX 選擇一個定值 0，然後後面就會將 Control signal 改成以 0 往下傳，效果就是會讓後面的「機器停擺」
- 而可以更神奇的發現，由於傳遞 0 下去後，下一個 cycle 送到 Hazard detection unit 的 `ID/EX.MemRead` 會是 0，所以就不會判斷有 Hazard，MUX 就又選回預設值。這樣恰好達成我們所需的「停下一個 cycle」的目的

:::warning
最終交由 Forwarding Unit 來把值送給相依的指令
:::

---

# Control hazard

現在換處理 Control hazard。上回有提到有兩種解法，一種是「預先算出來」，另一種是分支預測。
>Stall 解法沒人權

下面是預先算出來的電路圖：

<iframe src="https://drive.google.com/file/d/1PK5Szzi4FFBGw55kdo7x_n1Zu1HtkZzq/preview" height="580"></iframe>

可以看到在讀出指令後，就直接給他蹦出答案來，這就是上次提到的先偷偷算出來。

:::warning
別忘記 PC 的部分本身就有 latch 的效果，會把下一個地址擋在左側
:::

## 提前算出來

這種結構只要等一個 cycle 就可以知道要拿的指令是誰了，也就是下面這張圖的等一個 cycle：

<iframe src="https://drive.google.com/file/d/1RuaM1Fum1PeX9PER3K_Jix1FxCzz44Ny/preview" height="380"></iframe>

但是如果想要繼續以偷算的答案 forwarding 來解決的話，會造成更多的困擾：

## 困擾零

beq 的 dependency 發生時有隔一個指令。

這不是個困擾，因為可以用 forwarding 解決：

<iframe src="https://drive.google.com/file/d/1_kvad8w-WcBkUlDLNTcqnyrht6fRPnc9/preview" height="350"></iframe>

:::warning
注意，我們上面並沒有實作這樣的 forwarding 電路：)，我們是實作 EX 去拿 MEM 跟 RB 的值的 forwarding
:::

## 困擾一

beq 的 dependency 發生時沒有隔一個指令，並且用了兩個指令的結果。

這是個困擾，因為需要等 1 個 cycle：

<iframe src="https://drive.google.com/file/d/1y9SVjFBALgEiqqFsXw_qE9zXB0WjMtjb/preview" height="380"></iframe>

## 困擾二

beq 的 dependency 發生時沒有隔一個指令，用了 load 指令的結果。

這也是個困擾，因為需要等兩個 cycle：

<iframe src="https://drive.google.com/file/d/1kFCHuufTZrzKysEeEiqEDsr1vkRHfJ5J/preview" height="380"></iframe>

:::warning
可見光是為了「先算」，就因為需要 forwarding 而衍生出兩種需要等待的困擾，這不是個好消息
:::

# 分支預測

既然堅持 forwarding 會衍生三種情形，那麼我們乾脆億點，用猜的就不用考慮了。
確實，只要用猜的，就可以省略掉一堆麻煩。

上回有提到我們是直接猜 Non Branch (靜態分枝)，或是使用預測單元來預測 (動態分枝)。

而一旦預測錯，就會將後面的指令變為 nop：

<iframe src="https://drive.google.com/file/d/1kG_tINdEqD4S9oh-AYvurvKQqb04yY40/preview" height="250"></iframe>

其方法跟上面 Load-use data hazard 時 stall 所使用的方式類似，但是有對結構做一些處理：

<iframe src="https://drive.google.com/file/d/1XELo35vvP4lmaPmICjQYBXvEt3x39r1G/preview" height="580"></iframe>

- 將上面結構中，加法器的部分被集成到了 Control Unit 裡面，並且他會拉出：
- 一個 `IF Flush` 訊號來判斷 IF/ID 這個 Latch 內的值需不需要通通設為 0
- 一個 `ID Flush` 訊號來判斷 ID/EX 這個 Latch 內的值需不需要通通設為 0
- 可以看到他跟上面提到的 Load data hazard 所使用的訊號做 OR，也就是說只要發生其中一種就要將後面的工作全部停擺
- 但是可以注意到，我們只是將 ID/EX 裡面那幾個控制訊號設為 0，而 IF/ID 則是整個都設為 0 了

:::warning
上圖要注意，少畫了很多東西：
1. 理論上 branch 也會遇到 data hazard，加上因為把運算移到 ID 階段，所以需要特地為他弄 forwarding unit、hazard detection unit 也要修改，因為提前運算導致 branch 遇到 load-use hazard 需要等 2 個 cycle；但是教科書沒有把他畫出來，只有提到有這件事
2. 所以上圖是假設有這兩個修正的東西的前提下畫的，並且都通通塞到 Control unit 裡面了，也才因此可以拉 IF/ID flush 出來
3. 下面的 Bonus 部分我則是把 branch predictor 放在 EX stage，就可以直接用 EX 有的東西了
:::

## Branch History Table (BHT)/ Branch Prediction Buffer (BPB)

如果是動態預測，我們會再稍微==修改 PC 部分的電路==，改成讀取一個分支歷史表格，去猜要分枝還是不分枝。

這個表格是由「產生分支的指令的 index 的最後 n 個 bits」來判斷要使用哪個 entry 紀錄的值；而記錄的值就是 1 個 bit，分枝 T，或不分枝 NT。

下面是一個 `n=2` 的簡單例子，可以看到如果有某個指令 beq，他的地址最後兩個 bit 是 `00`，則他會猜 NT，也就是不分枝。

| entry index | value |
|:-----------:|:------:|
| 00 | NT (0) |
| 01 | T (1) |
| 10 | NT (0) |
| 11 | T (1) |

:::info
地址需要省略最後兩個 bit ，因為地址都是 4 的倍數
:::

## 修改 Table 的原則

下面介紹兩種原則。

第一種是一旦猜錯就修正。下圖是迴圈 index 的運算，並且 table 只有 1 bit，可以看到雖然他第一次猜錯，但是因為他後面就都會猜對了，但是到了最後一個又會猜錯，因此正確率為 80%：

<iframe src="https://drive.google.com/file/d/187IPu5QJv7586natPW9OfJywHYCrVgj8/preview" height="380"></iframe>

但是為了有更高的正確率，所以除了擴增為 2 個 bit ，使用了下面的狀態圖來判斷當前要猜甚麼：

<iframe src="https://drive.google.com/file/d/1WVrAgzURuXk081ekcregSR5lgzzyjIxt/preview" height="580"></iframe>

這張圖說明，如果從原本左邊的猜「對」狀態，錯一次會到不穩定的猜「對」狀態，再錯一次會到不穩定的猜「錯」狀態，最後再猜「錯」一次會到穩定的猜錯狀態。

那這樣我們的表格就會變為：

## 更多分枝預測

- 除了猜「錯」，我們可以嘗試預測猜「對」
- 這時候就還需要猜要「跳到哪裡」
- Correlating predictor
- 有時候還可以結合周圍的「區域行為 local behavior」，和一些「全域資訊 global information」來判斷要如何分枝
- Tournament branch predictor
- 這種 predictor 是去預測某個區塊要用哪種 predictor
- 屬於 predictor 的 predictor

---

# 例外處理

大致上的流程是先偵測到例外，然後再跳轉到相對應的 Handler 指令區域。

RISC 採取的作法是，如果偵測到例外：

- 會先將發生例外時的 PC 值存在 SEPC 這個獨特的 REG 內
- 目的是為了如果之後還可以繼續執行的話就可以跳回來
- 會將例外的種類存在 SCAUSE 這個特殊的 64 bit REG 內
- 這個 REG 負責記錄例外的種類等等資訊
- 但是大多的 bit 侍衛使用的狀態
- 最後跳到特定的 Common Entry Point
- 也就是說記憶體中有個專門的區域用來放例外處理的指令
- 這裡舉的 Common Entry Point 例子是 $\text{0000 0000 1C09 0000}_{\text{hex}}$

其他架構有另一種做法，又叫做 Vectored Interrupts：

- 一樣會記錄發生例外的 PC 以便稍後返回
- 但是會根據例外的種類「跳到不同的例外處理區域」
- 會先將例外的種類存入一個 vector table base REG
- 例外的種類如下：
- Undefined opcode 是 $\text{00 0100 0000}_{\text{two}}$
- Hardware malfunction 是 $\text{01 1000 0000}_{\text{two}}$
- 最後再根據對應的例外種類跳到對應的區域

## Pipeline 結構

<iframe src="https://drive.google.com/file/d/1XELo35vvP4lmaPmICjQYBXvEt3x39r1G/preview" height="580"></iframe>

其實就跟上面的架構一樣，只不過多了 SPEC 跟 SCAUSE 兩個模塊，用來表示要記錄相關資訊到對應的 REG 上；並且有個 Common entry 1C090000。

發生例外的時候，要做兩件事：

1. 讓後面未出錯的指令繼續執行
2. 將前面的指令 Flush 掉

從上面的可以看到，似乎只要讀完指令後就可以判定是否有例外發生，因為例外發生相關的訊號也都是由 Control Unit 產生，並且可以看到除了 `ID Flush` 還多了 `EX Flush`

# Bonus？


這張圖是使用上面提到的狀態圖來做分支預測的電路圖，也是作業的電路圖。

- 可以看到預測器會輸出 branch_or_not 來決定遇到 branch 指令要跳還是不跳
- branch 指令 B 當前在 ID，下一條猜的指令 C 已經在猜好了在 IF
- branch 指令 B 送到 EX，猜的指令 C 送到 ID，下一條指令 D 在 IF
- branch 指令會送 branch_EX、branch_PC ... 那 4 個輸入訊號給 predictor
- 如果 predictor 發現猜錯了，會透過輸出的 PC_fixing_flag 跟 fixing_PC 來修正當前正在 IF 的指令 D 變為正確的指令 E
- 並且會透過 flush 來把 IF/ID 裡面有關指令 C 的部分清除掉
- flush 會拉一條到 ID/EX 是因為編寫 iverilog 的時候要清除 ID 的指令 C 的資料

:::warning
iverlog 在編寫的時候會因為 always 內可以根據 postdege, negedge 或是 * 而有不同的寫法，上面的電路中有些元件內部是用 * 來做到有值變更即變動；有些是用 postdege (尤其是 Latch 來做到擋水閘的效果)，predictor 計算的部分是用 negedge 來確保資料已送達。
:::

---

## 回顧

- latch 的右半邊流出當前 stage 的內容
- 所以如果是階段 $i$ 需要上個指令的內容，那只能從階段 $i+1$、階段 $i+2$... 的 latch 拿
- 例如 EX 只能拿 EX/MEM 跟 MEM/RB 的東西