Ch.4-3 Pipeline Processor
Outline
- An overview of pipelining(介紹pipeline是什麼&概念)
- A pipelined datapath(利用已知的概念推出datapath)
- Pipelined control(根據datapath做出對應的control)
- Data hazards and forwarding(用forwarding解決hazards)
- Data hazards and stalls(用stalls解決hazards)
- Branch hazards(想辦法令branch hazards對processor的影響降到最低)
4-3–1 Pipeline Overview
KEY POINT:單位任務的latency沒有縮短,而是throughput提升了
Laundry Example
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
但是要注意到一點:因為任務本身有執行次序的問題,剛開始時通常一個工作單位只會做一件事(因偉其他任務還沒進來/在等待);而所有任務都將完成,工作階段要結束時,也會只剩下一點點任務要做
頭尾兩個時段的throughput會是整個流程中,最少的階段
工作階段剛開始時,等待任務進入的時間稱為fill time
工作階段要結束時,任務逐漸完成的時間稱為drain time
這兩個時間非常重要,因為他們會直接影響到pipeline processor的效能
Compare with Single-Cycle, Multi-Cycle, and Pipeline
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- Single-Cycle
一個cycle中只能有一個指令被執行
可以見圖中的load有完整運用這一個cycle
然而換到store時,卻有一小段wasted
- Multi-Cycle
將一個指令可能會用到的工作階段分割成多個
每個cycle負責其中一小部分
如此可依照指令的不同,用不同的cycle完成
如圖中load用了5個cycle,store用4個,接著換R-format開始用
- Pipeline
一個cycle中可以同時做多件事情
主要是提升throughput,使得效能提升
但也會衍生一些問題(hazard)
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
- single-cycle:
因為一個cycle只能完成一個指令,做完才能換下一個
所以若一次有3個load要完成,一個花費時間是800ps
則總花費時長為3 * 800 = 2400 ps
- pipeline:
處理單一指令的概念有點類似multi-cycle,也是切成多工作階段
而使用的datapath的部分則是跟single-cycle類似
重點是加入了一個cycle可以一次執行多個工作階段的要素
(同一個工作階段的資源一次還是只有一個任務可以使用)
一樣以一次有3個load要完成的話
假設總共有五個階段,每個花費的時間是200ps
去掉不能重疊的部分(進來要先instruction fetch)有200ps
因為有三個任務,去掉自己不需要算
總花費時長是5 * 200 + (3-1) * 200 = 1400
Why Pipeline?
因為資源就放在那哩,不用很浪費R!
用了可以提升效能,減少花費時間
好資源,不用嗎?
4-3–2 Pipeline Datapath
Designing a Pipelined Processor
- 找出要做的動作(IF、IF、EX、MEM、WB)
- 找出對應的硬體資源,以完成指令
- 注意不能發生資源衝突(不同指令要用同一個硬體資源)
- 配置好的control,使得元件能在對的時間做對的事
Datapath
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
結合single-cycle的datapath設計
還有multi-cycle切割的概念(別忘了storage element)
注意 feedback path會造成hazards,須注意
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Example
load
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
Image Not Showing
Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →
注意!
register file的write register此時是誰?
因為是pipeline,正常而言已經是後面其他指令指定的寫入暫存器了
所以會直接把"這一次"的load取得的資料送到"當下"的寫入暫存器,但這將是錯的!(一來正確暫存器沒有存到值,二來之後也會洗掉現在暫存器存的)
所以!
在最後memory要傳回資料時,應該把指定哪一個write register也傳回(如下圖,橘色線部分,在一開始就把“寫入暫存器”存入pipeline register中並向下遞送,最後要寫回資料時在一併跟著資料傳回去)



Structural Hazard
因為不同的指令使用不同元件的時間不一樣
(如上面紅圈處,R-format第4個就WB,但load要第五個才WB)
為了解決這樣的問題,令每個指令使用元件的時間變得一樣
(如下圖)

store

beq

在上一小段中提到的「為了解決structural hazard而增加的粉紅框框」就是extra stage。
Graphically Representing Pipelines







4-3–3 Pipeline Control
整體而言,control signal與single-cycle並無不同
只是多了RegDst以及下控制信號的時機的不同



Example
此題範例經過刻意設計,所有指令沒有用到相同的暫存器
但實際上不會這麼順利,若用到一樣的暫存器就會發生hazard









Summary
- 為什麼設計處理器看起來好像很簡單?
因為採用MIPS
MIPS的特性是:指令長度一樣、指令格式少、只有L/S要用到memory
- Pipeline真簡單
Noooooooooooooooooooooo並沒有!
那是因為還沒討論到特殊狀況
pipeline中最大的問題是「hazard」
將在之後的小節中討論
4-3–4 Data Hazard and forwarding
Pipeline Hazards
- Structural Hazards
超過一個指令要存取相同的硬體資源的狀況

圖中這種狀況是因為同時要寫入跟讀取memory,但是memory只有一個read port跟一個write port,且不能同時運作
所以這種狀況最簡單的解決方式:增加一個記憶體,總共兩個,一個負責data,另一個負責instruction
- Data Hazards
需要用到某個資料,但那個資料並沒有被產生(在那個當下)
- Control Hazards
要做決定時,需要某個結果,但是那個結果並沒有被運算出來
(通常是branch才會發生--需要知道下一個指令是誰,但還不知道到底要不branch)

紅線的部分是feedback path,上面那條可能在branch
的時候,發生control hazard,下面那條可能在要load
的時候,發生data hazard
最簡單的解決方法:等待
只要發生hazard,就等到造成hazard的原因消失,再繼續動作
如此很簡單,但是會使得pipeline的整體效能下降
在這個小節中,將會介紹用forwarding的方式解決
Data Hazards

Type of Data Hazards
- RAW(read after write)
描述一個指令應該"讀取先被寫入的資料"
但是卻先讀取"而還沒被寫入"
(所以是讀取到錯誤的、舊的資料)
- WAR(write after read)
先有讀取,後面才有寫入的指令
然而寫入的動作卻先行完成,之後才讀取
(所以是讀取到錯誤的、新的資料)
- WAW(write after write)
有兩個寫入的指令
但是後面的寫入卻比前面的先執行了
原在前面的寫入才真的寫入
(所以最後寫入的會是錯誤的、舊的資料)

Handling Data Hazards
因為MIPS的簡單,所以我們在這邊只要處理RAW的hazard就好了
要如何處理 hazard呢?我們要detect and resolve
先偵測有沒有hazard的情況發生,再來解決
(偵測方法我問號)解決方法如下:
- Compiler insert NOP (software solution)
當系統偵測到潛在的hazard可能發生時,就在指令後面插入一個NOP,讓他空運轉。
這是軟體的解決方法。
- Forward (hardware solution)
利用系統偵測,然後即時把資料送到需要用的地方。
這樣可以不用停下來。
這是硬體的解決方法。
- Stall (hardware solution)
如果發現RAW的狀況(要讀取的資料還沒到)就讓後面的指令先停止。
把後面的指令停下來,等前面的先做完並更新暫存器的值,再解鎖後面的指令。
這是硬體的方法。
可以發現1.3兩種方法,都是利用waiting的方式解決hazard,雖然waiting肯定是可以解決hazard的,但是這樣會使得pipeline processor的整體效能下降。
Compiler insert NOP (software solution)


Forward (hardware solution)

因為:
- sub要寫回暫存器的資料其實第3個cycle就生成了
- and實際要用到$2的資料是在第4個cycle的ALU
- or實際要用到$2的資料是在第5個cycle的ALU

所以:
可以直接把已產生的資料,送到有需要的人那裏
HOW?
用pipeline register,因為算完後都會存在這裏面

這張是實際的forward pipeline架構圖
圖中的
- 介於EX跟MEM之間的pipeline register有一條線,會連接到forward unit傳回去給ALU
- 介於MEM跟WB之間的pipeline register也有一條線,連接到forward unit傳回去給ALU
基於以上狀況,需要新的MUX來做選擇,以便選擇是要用原本的資料還是forwarding的資料
這個時候的control訊號,是觀察前面指令要寫入的暫存器編號是不是跟後面指令當下要用的暫存器編號一樣(比較rs、rt)
注意橘色信號的部分,是表示暫存器是否真的要寫入,因為沒有要寫入的話,就不需要forward了
Detecting Data Hazards
Hazard Conditions
- 當前要讀取的暫存器編號,跟前一個指令寫入的暫存器編號一樣
- 當前要讀取的暫存器編號,跟前兩個指令寫入的暫存器編號一樣
這兩種情況發生時,就需要forward
不過要注意前面的暫存器是不是真的要寫入,沒寫入的話就不需要forward,且$0暫存器的資料不需要被forward,因為他永遠都是0
所以實際上要注意的狀況是:
- 檢查前一個指令是否真的要寫入暫存器,且寫入的暫存器不為$0,並且寫入的暫存器與當前指令要讀取的暫存器一致
- 檢查前兩個指令是否真的要寫入暫存器,且寫入的暫存器不為$0,並且寫入的暫存器與當前指令要讀取的暫存器一致
上兩個狀況都滿足=同時都可以forwarding,應選擇較新、較近的狀況(前一個指令產出的資料)
Forwarding Logic

Example




4-3–5 Data Hazard and stall
專門解決forwarding不能解決的問題

Pipeline with Stalling Unit

左上角的方塊是hazard deetcted unit,用以偵測是否發生hazard
方法是橘色粗線的部分檢查是否為lw指令,並且看lw要用的暫存器是誰
然後再跟左邊黑線所偵測到的暫存器核對是否一致
如果是,代表會發生data hazard,那就要原地踏步
方法:
不要讓「長江後浪推前浪」
也就是不要讓pipeline register有新的資料進入,那就會送舊資料
運算舊的資料相當於原地踏步一次
- 令第一個pipeline register的控制信號為0(不要寫入)
這樣經過ID的指令就不會被更新
- 還要令PC的值不更新,也就是不會fetch新的指令
否則原應decode的指令解碼完後未被送出,又被覆蓋,等於消失
- 注意前面說到的execution要停止運算,不然會亂吃亂算
這裡的實現方法是給ID/EX的pipeline的control signal全為0
這樣EX階段的ALU就不會運算,也不會進行記憶體存取、寫入暫存器等
形成一個「安全的bubble」,使不會對系統造成任何影響
總之就是要確保control signal設定在一個「不會對EX/MEM/WB造成影響」的值
因為這樣才不會修改到暫存器、記憶體的值
就可以形成一個「安全的stall」
Example






4-3–6 Branch Hazard


Handling Branch Hazard
- 假設沒有branch,所有指令照常進入各個對應的stage;直到發現要branch了,再把多餘的、不應該進入的指令清掉,也就是清除前三個stage的pipelien register中的資料,並將控制信號設為0,可是這樣相當於讓CPU有3個idle狀態,實在是蠻浪費的。
- 試著提早得知有沒有要branch。可以發現的是,第一個stage-IF,絕對沒辦法做到,因為他還在抓取指令,根本不知道指令實際要幹嘛,要到第二個stage-ID,經過解碼才會知道指令要做的事情,且會抓出暫存器的值→在這裡,可以預先使用XOR判斷兩個暫存器的值是否相等,進一步提早得知是否要branch。這樣就只會有一個stage(IF)有不應該進來的指令需要被清除,並將控制信號設為0,比起第一個方法更好。
- Dynamic branch prediction
- Compiler rescheduling - Delay branch
1、2. Pipeline with Flushing

Example


flushing是一種static的branch prediction
static的意思就是「永遠先猜測不會branch」
等到發現真的要branch的時候才處理(清掉)
這種方法簡單卻不是每次都那麼好用
所以出現了下面的dynamic branch prediction
3. Dynamic Branch Prediction
dynamic運作的機制是會根據當前系統執行的狀況去「猜測、預測」會否branch
簡單來講就是賭博(不以gamble稱呼,改以speculate稱呼,較文雅)
猜對就賺到,可以使CPU全力執行,沒有idle產生;
猜錯頂多做flushing清掉。
Q:如何猜測?
會根據過往的branch狀況建立一個history table
等到發現有branch的指令時,就會根據table預測
稱之為branch prediction
這個prediction的成功率非常重要,影響CPU的效率
事實上,現在的CPU大廠(Intel、AMD)的準確率都高達九成以上
(因為很多程式都會有loop,而loop不可能只執行一次…之類的)
1-Bit Predictor: Shortcoming

這是一張兩層的巢狀迴圈示意圖
假設外面的迴圈的條件都成立,所以進入內部迴圈
內部迴圈第一次猜測沒有要跳(因為預設就是0)結果發現猜錯
所以就跳,並把紅框設成1表示這次跳了,給下次參考
後來幾次內部迴圈執行時,就根據紅框都是1而一直猜會跳
直到最後一次要跳離迴圈時還會猜錯一次,因為要結束了不會跳,table設0
然後回到外面的迴圈,因為預設是0,猜測不會跳,結果又猜錯
此時把table設成1然後跳,回到內部迴圈
尷尬的是,內部迴圈因為剛結束時table設成0,所以又要猜錯一次
並且重複"設成1,跳,猜會跳,真的會跳"的輪迴
直到最後要跳離時再猜錯一次,設成0,並結束
可以發現巢狀回圈的話,外部每進去一次內部都要猜錯兩次
其實蠻糟糕的,所以出現了2-Bit
2-Bit Predictor
用2bit總共會有4個狀態,分別是2個跳&2個不跳
意即,要連續猜錯兩次才會轉換預測結果

(左半邊是strong,右半邊是weak)
則雙層迴圈的運作方式會變成:
Calculating the Branch Target
前面不論是1-bit還是2-bit,都只能決定是否要跳,沒決定跳哪裡
所以還是要有個機制決定跳的位址
一樣是用猜的
把過往曾經跳到過的位址存到history table
如果沒有要branch,PC就直接更新成PC+4
如果要branch,就去查表,猜測要跳哪個位址,把PC指向表中那個位址
4. Delayed Branch
前面都是用硬體的方法解決contorl hazard(透過"增加control circuit"辦到)
但是可以用硬體配合軟體的方法解決,需要compiler幫忙
規定
(硬體方面)branch要在一個cycle過後才可以生效
(本來要跳的話下一個指令PC+4就可以跳了,現在變成PC+8才可以)
(軟體方面)並且compiler要協助挪移一個指令到branch後面
這個指令的條件是:
- 不可以用到branch要判斷的暫存器
- 不可以改到原本在這個指令前面的其他指令用的暫存器
- 不管branch與否都會執行到
滿足以上條件,才可以做好delay branch又不造成任何意外
基本上,現在compiler分析後判斷觸能不能挪移的指令,經過設計大概有50%都可以找到適合的;如果找不到,就只好塞nop在branch後面
這也意味著有50%的機會,CPU可以全速前進,不用因為猜錯而停下來或idle