[Computer Architecture Cheat sheet] — Pipeline Hazard

1. What is Pipeline Hazard
2. Three type of Data Hazard
3. Structure Hazard problem and solve
4. Data Hazard problem and solve
5. Control Hazard problem and solve
6. Branch Prediction
7. Delay Branch

What is Pipeline Hazard

pipeline無法在下一個Clock執行下一個指令的狀況就是pipeline hazard

Three type of Data Hazard

1. Structure Hazard :

硬體資源不足。(e.g.假設沒有IM與DM的差別，則IF 與MEM都有記憶體存取,重疊時會出問題 ,導致同一時間內無法執行多個指令)

2. Data Hazard :

管線中某一指令需要用到前一階段內指令尚未產生
的結果(data dependency)。

3. Control Hazard :

當Branch指令尚未決定是否分支，但後續指令已進入管線,故執行順序發生錯誤。

以下統整各Hazard的常用解決方式

Structure Hazard

Structure Hazard解決方法

1. 加入足夠硬體 [a.k.a “Increasing availablity of functionalunits”]
2. 暫停管線，讓會發生結構危障的指令錯開，以避免同一時脈週期使用相同硬體

Example

(假設所有data hazard都可以被forwarding解決)

如果memory只有一個，不分I-M or D-M

如上圖，在此Instruction sequence 中，如果我們只有一個Memory的話，lw指令與sw指令在c4時，皆同時想Access Memory，此時便有 Control Hazard

所以共需要執行9個cycle

Example

如上圖，在此Instruction sequence 中，如果我們只有一個Memory的話，beq想執行IF，但遇到LW所以有Control Hazard，於是Stall，然而下一指令又是S於是再Stall，又LW，又Stall。

所以共需要執行12個cycle

Data Hazard

有Data Hazard的情形為 : 某一指令的來源暫存器，是之前指令的目的暫存器但尚外將計算結果存入，此時此指令所fetch到的暫存器的值就是不正確的。

1. Data dependency
2. Data Hazard solve

Data dependency

1. RAW … (Read after Write)
2. WAR … (Write after Read)
3. WAW …(Write after Write)

因為只有RAW會真正造成Data Hazard，所有RAW的data hazard又稱為True data dependency，其餘稱為False data deapendency

Example

RAW : (1,2),(1,3),(2,4),(3,4)

WAR : none

WAW : (2,4)

Example

Data dependency:

(1,2),(1,3),(1,4),(2,4)

Data hazard:
(1,2),(1,3),(2,4)

Data Hazard 便是data depency超過距離 2且非load-use的

Note : Not all data dependency，只有 “ RAW “會產生 Data Hazard

Example

Two instruction with data dependency may not cause data hazard ?

ANS : YES

而且由此可知道，Data Hazard是因為達到 “某些條件 ”才會發生的，之後我們將使用此條件的判斷機制來建構 Forwarding Unit，作為解決 Data hazard的方法

Data Hazard 解決方法

軟體

1. 插入nop
2. Instruction rescheduling

Example … insert nop

插入足夠的nop指令使得有Data Hazard的指令間隔差距為2以上

Example … rescheduling

硬體

1. 若非 Load-use，以forwarding技術解決
2. 若是 Load-use，以stall one cylce、再forwarding 解決

Forwarding

Forwarding，又稱為bypassing，是利用資料提前的方式，讓需要計算的資料提早送達EX或MA之前。

Detcetion Data Hazard

由之前data dependcy 的觀念，可以得知data dependy如果達到某些條件就有可能會發生data hazard，這裡便是要討論該”條件”為何 ?

以上圖為例，我們可以由每個指令及其接續的兩個指令來判斷有無Data Hazard。

由接續的兩個指令來判斷的原因是因為

邏輯指令碼如下

即instr=sub$2,$1,$6，n_instr= and $12,$2,$5，nn_instr= add $14,$2,$2。如果Detect_Hazard(instr,n_instr,nn_instr) 偵測出來可能會有Hazard發生，便會依照EX_Hazard or MEM_Hazard來forward 資料給需要的指令。

所謂EX_Hazard便是在所需要的Data是在EX stage後才產生，為instr與n_instr的關係(差一指令)，此時instr指令有可能為R-type指令 … 。

同理MEM_Hazard便是在所需要的Data是在MA stage後才產生，為instr與nn_instr的關係(差二指令)，可能是lw指令…。

Forwarding Unit

上述邏輯指令碼中，我們沒有尚未實現Detect Hazard函數，此一邏輯函數在Data Path的電路中實質的存在為Forwarding Unit。

為了實現此功能函數，我們分為三個部份來做切入 :

1. instr 必須為有寫入暫存器的指令

(Control Signal — RegWrite來判斷)

2. instr寫入的暫存器不為 0

(instr的 Rd來判斷)

3. instr 寫入的暫存器與n_instr、nn_instr有data dependency

(instr的Rd與n_instr的rs/rt、nn_instr的rs/rt有沒有相同)

”三者都須滿足”才有可能發生 Data Hazard

ForwardA、ForwardB是Hazard Detection Unit產生的Control Signal，我們會將其傳送到ALU前的MUX使資料在運算之前能夠選擇資料是否來自Forwarding 的 data。

Forwarding Data Path

1. 首先我們先從EX與WB的結果，拉兩條資料線路回ALU之前

2.但ALU 前多出來的MUX 需要有Signal控制，因此加入Forwarding Unit：

3.而決定Forwaring unit輸出，則先是確定有『寫回』的動作，故需要有RegWrite ，並且是EX/MEM 與MEM/WB 的RegWrite皆要有：

4. 確認有『寫回』動作後，還要判斷寫回與之後指令是否有衝突，若沒有則不會有Data Hazard的問題，而有衝突的可能是 :

a.)EX Hazard : EX/MEM.Rd = ID/EX.Rs or ID/EX.Rt

b.)MEM Hazard : MEM/WB.Rd = ID/EX.Rs or ID/EX.Rt

5. 綜合上述，得到發生data hazard的條件為 :

EX_Hazard

MEM_Hazard

也可以得知，Forwarding Unit 的Input/Output :

進一步實作此"Combination Logic"

Load-use Data Hazard

當LW指令後面的指令馬上使用到共用的暫存器(有data dependency的)時，上述單純的Forwarding便無法直接解決Data Hazard的問題，因為LW需要WB之後，才進行計算，但是同一時間只能有一次的記憶體存取，因此需要將下一個指令先“Stall”一次，確認LW完成後才能繼續進行。

以下為Load-use的例子:

Load-Use Hazard Detection Units

由上表的例子，我們可以看得出來第1、2 行會有Load-use的狀況，但在管線執行當下，無法馬上判斷，因此我們必須偵測是否有Load-use的情形

1.在EX階段確認是否有LW指令，實際做法為拉ID/EX.MemRead至Hazard Detection Unit

2. 確認EX階段有LW後,判斷下一指令是否有衝突,即LW指令的Rd，與下
一指令的Rs、Rt是否有相同。因此我們除了直接將ID階段的Rs與Rt往
上拉、還要從EX階段下方的ID/EX.Rd 拉一條訊號線回Hazard Dection Unit

3.以上2步驟確認為Load-use後,要暫停LW之後指令，並讓LW往前一階段，因此HDU將輸出PCWrite、IF/IDWrite兩條控制線，以控制PC與IF/ID暫
存階段，不要正常接收Clock的訊號而進行後續指令。 (保有原指令即是stall)

4. 為了避免ID階段訊號傳到EX階段，造成2次執行的錯誤發生， HDU會輸
出一控制訊號，使原本的 9-bits control signal全數歸零[Deassert all 9 control signals]，也就是產生一個nop在EX階段。

綜合上述,完整的資料、控制線圖如下:

我們也可以得知HDU的輸入、輸出:

Control Hazard

Control Dependency

一個指令具有control dependent的條件為: 如果之後的指令結果會影響此指令的執行與否 : beq

Move the branch decision earlier

我們若是能夠提前預知branch與否，我們便可減少將之前的指令flush掉的penalty，故我們能夠改動原始設計如下。

0. 原本Branch是在EX階段決定要不要跳，是為了平衡各階段的執行時間

1. 嘗試將其放在MEM階段

2. 嘗試將其放在ID階段 … [Final version]

先加上一個”比較器”

Note : 不可能將branch完成時間移至 ID stage。因為此時尚無法擷取出暫存器內容來進行比較

上述目的為降低penalty，但卻沒有真正解決，而解決Control Hazard的方法也分為硬體與軟體

• 硬體 — Branch Predtion
• 軟體 — Delay Branch
• Stall

Branch Prediction

Processor 試著用簡單的方法(硬體可以實現)去猜測branch指令到底會不會跳的方式。

Static prediction

總是猜跳、或是猜不跳

Dynamic prediction

透過類似finite state machine(有限狀態機)的機制來猜測，實際是透過檢視上次分支與否，來判斷這次是否分支。會使用到”Branch prediction buffer”(預測緩衝器) 、”Branch history table,BHT”(分支歷史表 ) 。BHT 是由分支指令位址較低的部分，做為索引的小型記憶體，其中包含一個位元來指示最近分支是否發生

分支預測器告訴我們分支是否成立，但分支目的位址仍需計算。在5-stage pipeline 中會有一個週期的懲罰，因此我們可用”Branch target buffer”(分支目的位址緩衝器) 作為快取，來存放目的地 ，或是目的地指令來消除這個懲罰。

1-bit predict FSM

2-bit predict FSM

Example

sadf

Dynamic prediction Data Path

asd

Delay Branch

是一種Software-base的解決方式，又稱為Insert Safety Instruction(插入安全指令) ，也就是利用插入不論是否分支都會執行到的指令，來減少猜錯Branch所造成的Penalty，功能類似nop，但不會有空執行的狀況。

其中共有三種方式:

1. From Before
2. From Target
3. From Fall through

其中第一種最佳，需先嘗試。若有Data Hazard狀況，才試用二、三種。

若分支機率很高，則試用第二種

分支機率低則第三種。

NOTE :

Delay Branch是一個簡單而有效率的方式。隨著處理器管線的延長、以及每個時脈週期分發指令個數的增加,分支的延遲變得愈來愈長,而一個延遲插槽已不敷使用。因此相較於代價更高、但彈性大的動態方案,延遲分支已經失去吸引力。