# Ch.4-3 Pipeline Processor
###### tags: `Computer Organization`, `計算機組織`
## Outline
1. An overview of pipelining（介紹pipeline是什麼&概念）
2. A pipelined datapath（利用已知的概念推出datapath）
3. Pipelined control（根據datapath做出對應的control）
4. Data hazards and forwarding（用forwarding解決hazards）
5. Data hazards and stalls（用stalls解決hazards）
6. Branch hazards（想辦法令branch hazards對processor的影響降到最低）
## 4-3--1 Pipeline Overview
**KEY POINT**：單位任務的latency沒有縮短，而是throughput提升了
### Laundry Example
```
實現方法：令一個時段不要有閒置的工作單位，可以被物盡其用
以洗衣、烘乾、摺衣服來比喻：
```
```
若像上圖一樣：
一個人要完全做完一個流程才可以換下一個人開始，非常沒有效率
（四個人從6PM洗到12AM）
像下圖一樣：
當機器開始閒置，後面的就可以直接接續著使用，較有效率
（四個人從6PM洗到9:30PM）
```
:::info
但是要注意到一點：因為任務本身有執行次序的問題，剛開始時通常一個工作單位只會做一件事（因偉其他任務還沒進來／在等待）；而所有任務都將完成，工作階段要結束時，也會只剩下一點點任務要做
頭尾兩個時段的throughput會是整個流程中，最少的階段
工作階段剛開始時，等待任務進入的時間稱為**fill time**
工作階段要結束時，任務逐漸完成的時間稱為**drain time**
這兩個時間**非常重要**，因為他們會**直接**影響到pipeline processor的效能
:::
### Compare with Single-Cycle, Multi-Cycle, and Pipeline
1. Single-Cycle
一個cycle中只能有一個指令被執行
可以見圖中的load有完整運用這一個cycle
然而換到store時，卻有一小段wasted
2. Multi-Cycle
將一個指令可能會用到的工作階段分割成多個
每個cycle負責其中一小部分
如此可依照指令的不同，用不同的cycle完成
如圖中load用了5個cycle，store用4個，接著換R-format開始用
3. Pipeline
一個cycle中可以同時做多件事情
主要是提升throughput，使得效能提升
但也會衍生一些問題（hazard）
### Performance between Single-Cycle and Pipeline
1. single-cycle：
因為一個cycle只能完成一個指令，做完才能換下一個
所以若一次有３個load要完成，一個花費時間是800ps
則總花費時長為`3 * 800 = 2400 ps`
2. pipeline：
處理單一指令的概念有點類似multi-cycle，也是切成多工作階段
而使用的datapath的部分則是跟single-cycle類似
重點是**加入了一個cycle可以一次執行多個工作階段的要素**
（同一個工作階段的資源一次還是只有一個任務可以使用）
一樣以一次有３個load要完成的話
假設總共有五個階段，每個花費的時間是200ps
去掉不能重疊的部分（進來要先instruction fetch）有200ps
因為有三個任務，去掉自己不需要算
總花費時長是`5 * 200 + (3-1) * 200 = 1400`
### Why Pipeline？
```
為什麼要用pipeline？
```
:::danger
因為資源就放在那哩，不用很浪費R！
用了可以提升效能，減少花費時間
好資源，不用嗎？
:::
## 4-3--2 Pipeline Datapath
### Designing a Pipelined Processor
1. 找出要做的動作(IF、IF、EX、MEM、WB)
2. 找出對應的硬體資源，以完成指令
3. **注意不能發生資源衝突**(不同指令要用同一個硬體資源)
4. 配置好的control，使得元件能在對的時間做對的事
### Datapath
```
若採用multi-cycle的datapath
（將一個指令要用到的功能切開）
較為直觀，可是可能發生資源衝突
所以結合single-cycle的datapath較好
因為每個硬體元件在一個cycle中最多就被用一次
所以可以有效避免資源衝突、硬體被重複使用的狀況
```
:::info
結合single-cycle的datapath設計
還有multi-cycle切割的概念（別忘了storage element）
**注意** feedback path會造成hazards，須注意
:::
```
圖中的pipeline register就是multi-cycle中storage element的部分
上面的小字A/B表示分割A跟B兩個元件
```
### Example
#### load
```
一個load需要5個cycle才能做完
三個load指令，透過pipeline的話
不需要花費15個cycle，只要7個cycle就好了
因為彼此間幾乎全部重疊，只相差1個cycle
所需cycle：指令個數N + (N-1)
```
```
首先做IF（instruction fetch）
將指令取出來
--實際行為--
指向PC暫存器，取出內容
並將PC暫存器的值更新成PC+4
```
```
然後做ID（instruction decode）跟RF（register fetch）
將指令解碼，才知道要做什麼
以及從對應的暫存器取值
--實際行為--
將暫存器的值存起來
因為是load，所以有immediate
對其做sign extension後左移兩位（變成word）
```
```
進入EX（execution）
執行運算
--實際行為--
將base address跟immediate處理後的值相加
```
```
進入MEM（memory）
到記憶體中找資料
--實際行為--
根據前項算出的地址，在memory中找對應的資料
```
```
最後是WB（write back）
將取出的資料寫回暫存器
--實際行為--
memory中找出的資料傳到register file的write data
再由register file根據write register配給資料
```
:::warning
注意！
register file的write register此時是誰？
因為是pipeline，正常而言已經是後面其他指令指定的寫入暫存器了
所以會直接把"這一次"的load取得的資料送到"當下"的寫入暫存器，但這將是錯的！（一來正確暫存器沒有存到值，二來之後也會洗掉現在暫存器存的）
**所以**！
在最後memory要傳回資料時，應該把指定哪一個write register也傳回（如下圖，橘色線部分，在一開始就把“寫入暫存器”存入pipeline register中並向下遞送，最後要寫回資料時在一併跟著資料傳回去）
:::
#### R-format
```
正常而言，R-format的指令只需要4個cycle
```
```
但若像上圖，同時有R-format與load指令的話
在紅圈處會發生structural hazard
```
:::warning
**Structural Hazard**
因為不同的指令使用不同元件的時間不一樣
（如上面紅圈處，R-format第4個就WB，但load要第五個才WB）
為了解決這樣的問題，令**每個指令使用元件的時間變得一樣**
（如下圖）
:::
```
註：
此中R-format的第四個cycle處理MEM的部分
直接不進行任何動作即可
如此便不會發生structural hazard了！
```
#### store
```
為了解決structural hazard
原本只需要4個cycle的store也增加了WB的部分（粉紅框框）
一樣執行到那個cycle及元件時，不要動作即可
```
#### beq
```
原本只需要3個cycle的beq增加了MEM、WB的部分（粉紅框框）
執行到那個cycle及元件時，不要動作即可
如此便不會發生structural hazard了！
```
### Extra Stage
在上一小段中提到的「為了解決structural hazard而增加的粉紅框框」就是extra stage。
### Graphically Representing Pipelines
```
圖解pipeline有助於理解
```
```
下圖*6是上圖的指令（先lw再sub）實際在pipeline中運作的情形
```
## 4-3--3 Pipeline Control
整體而言，control signal與single-cycle並無不同
只是**多了RegDs**t以及**下控制信號的時機**的不同
```
第一張圖是pipeline實際的datapath
第二張圖是control signal的使用時機
```
```
每個pipeline register要儲存的東西
```
### Example
```
lw $10, 20($1)
sub $11, $2, $3
and $12, $4, $5
or $13, $6, $7
add $14, $8, $9
```
此題範例經過刻意設計，所有指令沒有用到相同的暫存器
但實際上不會這麼順利，若用到一樣的暫存器就會發生hazard
```
首先，預期5個指令會用到9個cycle
[5+(5-1)=9]
下圖*9是實際運作情形
```
### Summary
1. 為什麼設計處理器看起來好像很簡單？
因為採用**MIPS**
MIPS的特性是：指令長度一樣、指令格式少、只有L/S要用到memory
2. Pipeline真簡單
Noooooooooooooooooooooo並沒有！
那是因為還沒討論到特殊狀況
pipeline中最大的問題是「**hazard**」
將在之後的小節中討論
## 4-3--4 Data Hazard and forwarding
### Pipeline Hazards
1. Structural Hazards
超過一個指令要存取相同的硬體資源的狀況
圖中這種狀況是因為同時要寫入跟讀取memory，但是memory只有一個read port跟一個write port，且不能同時運作
所以這種狀況最簡單的解決方式：增加一個記憶體，總共兩個，一個負責data，另一個負責instruction
2. Data Hazards
需要用到某個資料，但那個資料並沒有被產生（在那個當下）
3. Control Hazards
要做決定時，需要某個結果，但是那個結果並沒有被運算出來
(通常是branch才會發生－－需要知道下一個指令是誰，但還不知道到底要不branch)
紅線的部分是feedback path，上面那條可能在`branch`的時候，發生control hazard，下面那條可能在要`load`的時候，發生data hazard
:::info
**最簡單的解決方法：等待**
只要發生hazard，就等到造成hazard的原因消失，再繼續動作
如此很簡單，但是會使得pipeline的整體效能下降
在這個小節中，將會介紹用**forwarding**的方式解決
:::
### Data Hazards
```
像圖中這種狀況，即是典型的data hazard
因為sub要在第5個cycle才能給暫存器$2資料
可是and在第3個cycle、or在第4個cycle就要$2的資料
add在第5個cycle、sw在第6個cycle要$2的資料
如此and跟or勢必拿不到正確的值，add跟sw才有機會拿到
```
### Type of Data Hazards
1. RAW(read after write)
描述一個指令應該"讀取先被寫入的資料"
但是卻先讀取"而還沒被寫入"
（所以是讀取到錯誤的、舊的資料）
2. WAR(write after read)
先有讀取，後面才有寫入的指令
然而寫入的動作卻先行完成，之後才讀取
（所以是讀取到錯誤的、新的資料）
3. WAW(write after write)
有兩個寫入的指令
但是後面的寫入卻比前面的先執行了
原在前面的寫入才真的寫入
（所以最後寫入的會是錯誤的、舊的資料）
:::info
在MIPS中，因為架構簡單，所以**只會有RAW發生**
:::
```
上圖是表示RAW、WAR、WAW的架構
可以發現圖中MEM跟ID異常的長
那是刻意為了呈現出WAR跟WAW而營造出的狀況
但因為MIPS的pipeline，每個狀態都等'ˊ
所以MIPS中不會發生WAR跟WAW
```
### Handling Data Hazards
因為MIPS的簡單，所以我們在這邊只要處理RAW的hazard就好了
要如何處理 hazard呢？我們要**detect and resolve**
先偵測有沒有hazard的情況發生，再來解決
（偵測方法我問號）解決方法如下：
1. Compiler insert NOP (software solution)
當系統偵測到潛在的hazard可能發生時，就在指令後面插入一個NOP，讓他空運轉。
這是軟體的解決方法。
2. Forward (hardware solution)
利用系統偵測，然後**即時**把資料送到需要用的地方。
這樣可以不用停下來。
這是硬體的解決方法。
3. Stall (hardware solution)
如果發現RAW的狀況（要讀取的資料還沒到）就讓後面的指令先停止。
把後面的指令停下來，等前面的先做完並更新暫存器的值，再解鎖後面的指令。
這是硬體的方法。
可以發現1.3兩種方法，都是利用**waiting**的方式解決hazard，雖然waiting肯定是可以解決hazard的，但是這樣會使得pipeline processor的整體效能下降。
#### Compiler insert NOP (software solution)
```
整個系統都被拖慢了RRRR
能在9個cycle做完的事情（雖然會發生hazard導致錯誤）
卻要拖到好幾個cycle之後了
```
#### Forward (hardware solution)
:::info
因為：
1. sub要寫回暫存器的資料其實第3個cycle就生成了
2. and實際要用到$2的資料是在第4個cycle的ALU
3. or實際要用到$2的資料是在第5個cycle的ALU
:::
:::info
所以：
可以直接把已產生的資料，送到有需要的人那裏
ＨＯＷ？
用pipeline register，因為算完後都會存在這裏面
:::
這張是實際的forward pipeline架構圖
圖中的
1. 介於EX跟MEM之間的pipeline register有一條線，會連接到forward unit傳回去給ALU
2. 介於MEM跟WB之間的pipeline register也有一條線，連接到forward unit傳回去給ALU
基於以上狀況，需要新的MUX來做選擇，以便選擇是要用原本的資料還是forwarding的資料
這個時候的control訊號，是觀察前面指令要寫入的暫存器編號是不是跟後面指令當下要用的暫存器編號一樣（比較rs、rt）
注意橘色信號的部分，是表示**暫存器是否真的要寫入**，因為沒有要寫入的話，就不需要forward了
### Detecting Data Hazards
#### Hazard Conditions
1. 當前要讀取的暫存器編號，跟前一個指令寫入的暫存器編號一樣
2. 當前要讀取的暫存器編號，跟前兩個指令寫入的暫存器編號一樣
這兩種情況發生時，就需要forward
不過要注意前面的暫存器是不是真的要寫入，沒寫入的話就不需要forward，且$0暫存器的資料不需要被forward，因為他永遠都是0
:::info
所以實際上要注意的狀況是：
1. 檢查前一個指令是否真的要寫入暫存器，且寫入的暫存器不為$0，並且寫入的暫存器與當前指令要讀取的暫存器一致
2. 檢查前兩個指令是否真的要寫入暫存器，且寫入的暫存器不為$0，並且寫入的暫存器與當前指令要讀取的暫存器一致
上兩個狀況都滿足＝同時都可以forwarding，應選擇較新、較近的狀況（前一個指令產出的資料）
:::
#### Forwarding Logic
### Example
```
這是前面的例子的第三個cycle
可以發現sub, and, or要用的暫存器有重疊
```
```
進到第4個cycle時
and需要用到$2運算，但此時sub還沒將$2寫回暫存器
硬體檢查sub跟and要用的暫存器是否相同，及sub是否會寫
發現兩者都成立，所以透過forward unit跟MUX將pipeline register的資料給ALU
```
```
第5個cycle
or要用到$4跟$2，然而and跟sub分別還沒將$4跟$2寫入暫存器
硬體檢查or和"sub跟and"用的暫存器是否相同，及sub跟and是否會寫
發現兩者都成立，所以透過forward unit跟MUX將pipeline register的資料給ALU
```
```
第6個cycle
add要用到$4，而前面or跟and都有用到$4
硬體檢查add跟"or和and"用的暫存器是否相同，及or和and是否會寫
發現兩者都成立，且因為or和and的暫存器一樣，選擇新的、近的
所以透過forward unit跟MUX將pipeline register中or的結果給ALU
```
## 4-3--5 Data Hazard and stall
專門解決forwarding不能解決的問題
```
簡單介紹運作：
如果新進來的指令導致系統出現hazard，
就將新進的指令強制停止，讓原有的指令做完
做完原有的指令後才讓新進的指令繼續執行
```
```
如上圖這種狀況（data hazard），將無法使用forwarding
因為第4個cycle才會產生出需要的資料
但在下一個指令的第3個cycle就要用到了
沒生出來的東西不能用啊！！
```
:::info
解決方法：
1. 軟體
在lw之後and之前，由compiler插入一個`NOP`
2. 硬體
由系統偵測是否發生無法用forwarding解決的hazard
（術語上，稱呼發生hazard的這個and為「被廢棄掉」）
圖中藍色雲朵處即為發生hazard的地方，這張是以「延後」指令的概念繪製
圖中灰色bubble處是發生hazard的解決方法「原地踏步」
就是把and跟or原本執行到的stage重新再做一次
（注意下一個stage，execution，要另外處理，使他不動作）
不論是哪一張圖，概念都是形成一個類似nop的bubble
只是第二張才比較符合實際上的運作（複製stage使看起來像nop）
:::
### Pipeline with Stalling Unit
左上角的方塊是hazard deetcted unit，用以偵測是否發生hazard
方法是橘色粗線的部分檢查是否為lw指令，並且看lw要用的暫存器是誰
然後再跟左邊黑線所偵測到的暫存器核對是否一致
如果是，代表會發生data hazard，那就要原地踏步
:::warning
方法：
**不要讓「長江後浪推前浪」**
也就是不要讓pipeline register有新的資料進入，那就會送舊資料
運算舊的資料相當於原地踏步一次
1. 令第一個pipeline register的控制信號為0（不要寫入）
這樣經過ID的指令就不會被更新
2. 還要令PC的值不更新，也就是不會fetch新的指令
否則原應decode的指令解碼完後未被送出，又被覆蓋，等於消失
3. 注意前面說到的execution要停止運算，不然會亂吃亂算
這裡的實現方法是**給ID/EX的pipeline的control signal全為0**
這樣EX階段的ALU就不會運算，也不會進行記憶體存取、寫入暫存器等
形成一個「安全的bubble」，使不會對系統造成任何影響
:::
:::danger
總之就是要確保control signal設定在一個「不會對EX/MEM/WB造成影響」的值
因為這樣才不會修改到暫存器、記憶體的值
就可以形成一個「安全的stall」
:::
### Example
```
lw進入第2個cycle，and還在第一個cycle做IF
兩者不衝突，沒事發生
```
```
lw進到第3個cycle，此時and到第2個cycle
系統發現是lw指令，且用到的暫存器跟and一樣是$2
所以要令控制訊號為0生成一個bubble使得and延遲一個cycle
```
```
因為bubble，使得and跟or在原地踏步
此時的lw已經進到存取memory的階段了
bubble則是在EX階段，沒有東西沒有運算沒有影響
```
```
此時and來到第3個cycle，要開始運算，要用到$2
雖然lw還沒將取出來的值存回$2，但是已經算出對應的資料的
所以這時候可以用forwarding將pipeline register的資料取出，給and用
```
```
and走到第4個cycle，or到第3個cycle需要用$4
而and算出$4的資料卻還沒把他存回暫存器
一樣使用forwarding將pipeline register中的資料給or用
```
```
or到第4個cycle算出來但還沒存回暫存器$4的資料
正到第3個cycle的add要用
所以用forwarding取出pipeline register中的資料給add用
```
## 4-3--6 Branch Hazard
```
圖中紅色粗線分別代表control hazard（上）及data hazard（下）
其中，control hazard是由branch衍生的問題
```
```
圖中紅圈處，是真正決定branch與否的關鍵點
他會判斷branch（表示有沒有要跳）跟zero output（條件成立與否）
可以發現他是在第4個cycle才執行
在前面第1.2.3個cycle已經分別有branch的PC+4.PC+8.PC+12的指令進來
如果紅圈and gate判斷的結果是沒有要branch，就沒有關係
但！若and gate判斷的結果是要branch，那後面的指令就不應該進來
否則結果可能會出錯（運算到錯誤的東西）
這就是接下來要處理的control hazard
```
### Handling Branch Hazard
1. 假設沒有branch，所有指令照常進入各個對應的stage；直到發現要branch了，再把多餘的、不應該進入的指令清掉，也就是**清除前三個stage的pipelien register中的資料，並將控制信號設為0**，可是這樣相當於讓CPU有3個idle狀態，實在是蠻浪費的。
2. 試著**提早得知有沒有要branch**。可以發現的是，第一個stage－IF，絕對沒辦法做到，因為他還在抓取指令，根本不知道指令實際要幹嘛，要到第二個stage－ID，經過解碼才會知道指令要做的事情，且會抓出暫存器的值→在這裡，可以預先使用XOR判斷兩個暫存器的值是否相等，進一步提早得知是否要branch。這樣就只會有一個stage（IF）有不應該進來的指令需要被清除，並將控制信號設為0，比起第一個方法更好。
3. Dynamic branch prediction
4. Compiler rescheduling - Delay branch
```
1跟2清除的動作稱為flushing
3跟4都是比較進階的方法
```
### 1、2. Pipeline with Flushing
```
將branch的target address計算從第3個stage移到第2個
並且如果判斷出來要branch的話，就要把IF中"對於branch是PC+4的"那個指令清掉
此時將由control送出flushing信號給第一個pipeline register
並且也會生成一個控制信號皆為0的bubble，使其不影響後面
```
#### Example
```
beq到第2個cycle的時候，計算出了target address是72
並且比較$1跟$3的值是相等的話，就把PC的值更新成72
因為相等就代表要branch
（倘若不相等，就維持原本要更新的PC+4 = 48）
注意：control還會送flushing信號給IF/ID register
藉此清掉不應該進來的and並生成bubble
```
```
因為最後決定要branch，所以清除and變成一個bubble
並且新進來的指令是位址72的lw
```
:::warning
flushing是一種static的branch prediction
static的意思就是「永遠先猜測不會branch」
等到發現真的要branch的時候才處理（清掉）
這種方法簡單卻不是每次都那麼好用
所以出現了下面的dynamic branch prediction
:::
### 3. Dynamic Branch Prediction
dynamic運作的機制是會根據當前系統執行的狀況去「猜測、預測」會否branch
簡單來講就是賭博（不以gamble稱呼，改以speculate稱呼，較文雅）
猜對就賺到，可以使CPU全力執行，沒有idle產生；
猜錯頂多做flushing清掉。
:::info
**Q：如何猜測？**
會根據過往的branch狀況建立一個history table
等到發現有branch的指令時，就會根據table預測
稱之為branch prediction
這個prediction的成功率非常重要，影響CPU的效率
事實上，現在的CPU大廠（Intel、AMD）的準確率都高達九成以上
（因為很多程式都會有loop，而loop不可能只執行一次...之類的）
:::
#### 1-Bit Predictor: Shortcoming
```
在beq的指令前面增加1 bit來儲存跳的狀況當作table（下圖中紅框部分）
如果是0，代表上一次不跳；如果是1，代表上一次有跳
```
:::info
這是一張兩層的巢狀迴圈示意圖
假設外面的迴圈的條件都成立，所以進入內部迴圈
內部迴圈第一次猜測沒有要跳（因為**預設就是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指向表中那個位址
:::danger
！！有可能會猜錯！！
猜錯就清除flushing
:::
### 4. Delayed Branch
前面都是用硬體的方法解決contorl hazard（透過"增加control circuit"辦到）
但是可以用硬體配合軟體的方法解決，需要compiler幫忙
:::info
**規定**
（硬體方面）branch要在一個cycle過後才可以生效
（本來要跳的話下一個指令PC+4就可以跳了，現在變成PC+8才可以）
（軟體方面）並且compiler要協助挪移一個指令到branch後面
這個指令的條件是：
1. 不可以用到branch要判斷的暫存器
2. 不可以改到原本在這個指令前面的**其他**指令用的暫存器
3. 不管branch與否都會執行到
滿足以上條件，才可以做好delay branch又不造成任何意外
基本上，現在compiler分析後判斷觸能不能挪移的指令，經過設計大概有50%都可以找到適合的；如果找不到，就只好塞nop在branch後面
這也意味著有50%的機會，CPU可以全速前進，不用因為猜錯而停下來或idle
:::
Sign in with Wallet
Connect another wallet