# 在Hazard尋求解法是否搞錯了什麼

###### tags: `IT鐵人`

## Stall

上一次講到了三種Hazard：

| 類型 | 原因 |
|-|-|
| Structural Hazard(結構危障) | 硬體資源不夠多，導致在同一時間內要執行的多個指令無法執行。 |
| Data Hazard(資料危障)| Pipeline中某一指令需要用到前面指令尚未產生的結果，也就是執行的指令所需的資料還無法獲得。 |
|Control Hazard(控制危障)| Branch的結果尚未產生時，後續的指令就已經進入Pipeline，如果決定要branch到別的位置便會發生錯誤。所以又稱為Branch Hazard。 |

其實都能透過暫停Pipeline來解決，意思是不要急著插入下一個指令，塞幾個空格進去，避開Hazard後再來好好執行原先要執行的指令，這個作法就稱為Stall。

因為Structural的解決方式很簡單，只要把Insturction Memory跟Data Memory分開即可，所以以下討論Data Hazard跟Control Hazard的解決方法。

## Data Hazard解決方法

Data Hazard可以用軟體跟硬體的方法解決，軟體的分為NOP跟重新排列，硬體則是使用Forwarding。

## NOP

通常我們Stall的方法是插入NOP，就是No Operation，以Data Hazard來說，需要寫回Register指令的後面兩個指令都不能用到該寫回的Register，因為這時該Register還沒更新到最新的結果，所以我們插入NOP的方式就會像是...


對於這樣的指令，因為$2要寫回去才能交給其他指令只用，所以要插入兩個NOP對齊WB跟ID，這樣子前半Cycle可以存入，後半Cycle可以取得更新的資料，就可以避免NOP。

||c1|c2|c3|c4|c5|c6|c7|c8|c9|c10
|-|-|-|-|-|-|-|-|-|-|-|
|sub|IF|ID|EX|MEM|*WB* (前半Cycle更新)||||
|nop (stall)||IF|ID|EX|MEM|WB|
|nop (stall)|||IF|ID|EX|MEM|WB|
|and||||IF|*ID* (後半Cycle取得)|EX|MEM|WB|
|add|||||IF|ID|EX|MEM|WB|
|sw||||||IF|ID|EX|MEM|WB|

## 重排指令順序

重排指令順序通常是在Compiler負責執行，也就是說在編譯程式的時候，它就要想辦法把程式重新排列以便避開Data Hazard。

因為只要隔開兩格即可避免Data Hazard，我們可以將底下移動後不影響結果的指令向上移動，就能夠填補那兩格NOP指令，以下提供一個範例：

|編號|指令||||
|-|-|-|-|-|
|0|lw|$t2|4($t0)||
|1|add|$t3|$t1|$t2|
|2|sub|$t6|$t6|$t7|
|3|lw|$t4|8($t0)||
|4|add|$t5|$t1|$t4|
|5|and|$t8|$t8|$t9|

在這邊0和1會在t2發生Data Hazard、3和4會在t4發生Data Hazard。

所以要在不影響結果的狀況下調動順序，我們可以將3拿到0的後面，然後1放在2的後面，如此一來就能保證t2及t4的指令會和原本Data Hazard的指令有兩格的差距，即可避免Data Hazard。結果如下：

|編號|指令||||
|-|-|-|-|-|
|0|lw|$t2|4($t0)||
|3|lw|$t4|8($t0)||
|2|sub|$t6|$t6|$t7|
|1|add|$t3|$t1|$t2|
|4|add|$t5|$t1|$t4|
|5|and|$t8|$t8|$t9|

看起來就像事先把t2跟t4的值先從Data Memory中讀出來，在後面沒有Hazard的地方做運算避開Hazard。

## Forwarding

重新排列順序有時後會發生無可避免的狀況，通常這時候就會直接插入NOP了，不過交給Compiler執行也會稍微耗費時間，所以我們也可以從硬體著手。

Forwarding的概念是這樣的，我直接把運算完的結果送到下一個指令要讀取的Register的地方，比如說我運算後要把結果存入t2，而後面的指令正好要取t2的數值，那麼我直接把數值交給它即可。

底下有一個範例，像是前三行的R1，後面的指令都直接需要，所以我們就接線過去把數值傳給它。

不過因為實際硬體的接線情況比較麻煩，原本的Datapath又會接的更複雜，想了解的同學就自己搜尋一下吧~


以實際生活發生的事情就像是：我去圖書館借書，要還的時候正好有人要借同一本書，那我就直接跟管理員說然後把書交給它。如此一來就可以避免丟進還書箱、圖書館員分類放好、想要的人再去找書完成借書程序。

## Control Hazard的解法

至於Control Hazard的解決方，前面提到Control Hazard是因為Branch導致有指令需要丟掉，其實只要插入3個NOP就能解決，因為這時候PC就會指到對的指令位址，Instruction Memory就會輸出正確的指令。

所以這樣解決就可以了。

## Dynamic Branch Prediction

如果不知道結果怎麼樣的話，那用猜的不就好了，沒錯！

既然最差的情況是要等3個NOP，猜錯的話也只是捨棄結果再來重新跑指令，但是如果猜對了就沒有任何stall，那我們還不如一開始就猜結果，猜對賺到，猜錯也不虧。

猜的方式這邊要介紹兩種，分別是1-bit跟2-bit。

## 1-bit Prediction Scheme

在這邊用Finit State Machine(FSM)表示，不知道這是什麼的同學，這邊簡單介紹一下，圓圈的部份代表現在的狀態，箭頭代表遇到什麼情況要轉換到哪個State。

以下是1-bit Prediction Scheme的FSM：


概念上就是如果這次的結果是yes，下個結果我就猜是yes，反之同理。

## 2-bit Prediction Scheme

以下是2-bit Prediction Scheme的FSM：


概念上就是如果發生了連續兩次的yes，那麼就相信下個結果也是yes。

如果我現在站在永遠yes的狀況，只出現了一次no，我仍然相信下次還是yes。

舉個例子：

> 假設我現在在深藍色的Predict taken的State，然後發生了下列順序的結果，T代表taken(答案為yes或是我猜測yes)，NT代表not taken(答案為no或是我猜測no)：
> |發生結果|2-bit猜測|是否match?|
> |-|-|-|
> |T|T|yes|
> |T|T|yes|
> |N|T|no|
> |T|T|yes|
> |N|T|no|
> |N|T|no|
> |N|N|yes|
> |N|N|yes|
> |T|N|no|
> |T|N|no|
> |N|T|no|

這樣子發生了11次猜測，只有5次猜對，答對率不到一半，雖然看起來很差，不過這是為了舉例做出的結跟，所以跟實際情況有出入。

如果是平常的for迴圈，1000次之後才會跳出去，那麼可能只有1~3次會答錯，這麼看起來答對率超過99%，是很棒的預測。

這邊主要要跟大家說可以用猜測的方式減少Control Hazard發生的機率，實際硬體接線也是很複雜，畢竟還要丟掉不要的指令以及通知Branch發生，這邊就不特別說明了。

|上一篇|下一篇|
|--|--|
|[Hazard](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/rk7NPf2kK)|[近水樓台先得月](https://hackmd.io/@dZfCcN4hT8aUuDPv3B8CWQ/SyCUTiyet)|

## What we done?

這篇教了大家概念上怎麼解決Hazard，雖然沒有跟大家說明硬體的部份，不過杰哥認為知道一下概念就好了，辛苦大家看到這邊了~ 最近幾篇的內容都蠻硬的，相信不少同學都被嚇到了，繼續努力吧~