iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

杰哥的考研紀錄系列 第 9

Day-9 在Hazard尋求解法是否搞錯了什麼

在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 近水樓台先得月

What we done?

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


上一篇
Day-8 Hazard
下一篇
Day-10 近水樓台先得月
系列文
杰哥的考研紀錄30

尚未有邦友留言

立即登入留言