# Hazard

## :bulb: Background

### pipeline (review)
---

  pipeline 將一個指令分為5個stage (IF、ID、EX、MEM、WB)，使得同一個clock cycle可以同時處理多條指令。

  ideal pipeline speed up = # of stages，然而如果each stage執行秒數各不同，受限於執行時間最大的stage，使得speed up 小於理想值。

## :book: Introduction
---

  pipeline存在一種情況使得下一條指令無法在下一個clock cycle 順利執行。這種情形稱為``pipeline hazard``

### Hazard type

1. Structural hazard

資源使用衝突，使得必須等待前一指令resource使用完畢。

ex: 假設pipeline 只有單一memory，那麼同一個cycle Mem stage (load \ store) 與 IF stage (instruction fetch) 產生資源使用衝突
<br>

:::success

:bulb: solution

&emsp;&emsp;use separate instruction / data memory or caches
:::

2. Data hazard

指令所使用data相依於前一指令計算結果


:::warning
因add指令在ALU階段執行Register value還沒進行更新，但sub指令此時需要ALU計算結果
:::

3. Control hazard

需要等待control flow結果才能決定使否執行下一行指令

    if (x > 10) x++;
    else x--;

:::warning
x > 10 結果還沒出來，此時x++指令已經載入至cpu中。
若 x > 10 為 false 則必須把先前載入指令flush，並跳至x- -指令
:::
---

### **Resolving Data hazard**

#### 1. Stall (insert bubble)

當偵測到Data hazard產生時，insert bubbles (No Operation)，直到執行結果寫回至register

#### 2. Forwarding

adding extra hardware 將執行結果forward到下一個指令


:::danger
Load-Use Data Hazard 無法只靠forwarding就能解決，這是因為一般指令結果在EX stage就能知道，但ld / sd指令要在Mem stage取得資料才能知道結果
:::


:::success

:bulb: solution

&emsp;&emsp;Stall and Forwarding
:::
#### 3. Data hazard Conclusion

在hazard處理上應避免Stall，因過多Stall將使得pipeline退回non-pipeline執行效率，因此在program方面==load use data hazard==可以透過==調整指令執行順序==，減少因stall所需的clock cycle


----

### **Resolving Control hazard**

1. Stall (insert bubble)

insert bubble (NOP) 等到branch 指令結果出來

2. Branch Prediction

**a. Static branch prediction**

根據typical branch behavior，預設branch結果

ex: ==for loop== 預設結果為 ==true==、 if statement 預設結果為 ==false==

**b.Dynamic branch prediction**

根據執行狀況，更改預測選項

ex: 若branch result一直為 true，那麼預測應該更改為true，反之亦然

:::success
如果實際結果與預測結果不符，那麼將會指令flush掉，並重新載入正確指令，但如果預測正確將會減少不必要的flush與stall
:::

----

### **Conclusion**

所有Hazard皆可透過Stall技巧解決，但應盡力避免，改採用其他方法，因過多Stall將使得pipeline優勢蕩然無存。因此像==Struct Hazard==透過==seperate memory or caches==、==Data Hazard==透過==Forwarding==、==Condiction Hazard==透過==Branch Prediction==，減少不必要的Stall，維持pipeline應有的Performance。

---

### Reference

[1] P.A.Patterson and J.L. Hennessy, Computer Organization and Design RISC-V

###### tags: `Computer Architecture`

<style>
@import url('https://fonts.googleapis.com/css2?family=PT+Serif&display=swap');
@import url('https://fonts.googleapis.com/css?family=Noto+Serif+TC&amp;display=swap');
@import url('https://fonts.googleapis.com/css2?family=Fira+Code&family=Noto+Serif+TC&display=swap');

* {
font-family: 'PT Serif', 'Noto Serif TC', sans-serif;
letter-spacing: 0.02em;
/* font-size: 16px;
letter-spacing: 0.02em; */
}

.easy{
color:green;
}
.medium{
color:#eda35e;
}
.red{
color:red;
}

.proof {
padding:10px;
background-color: #f7f7f7;
}

</style>