# 利用管線增加效能 ## 重點一 管線範例 ### Pipeline * 不會改善單一工作的latency，因為單一指令執行時間還是一樣，但會增進整體工作的throughput * **藉由讓多個工作同時在管線中使用不同的資源來提升硬體使用率** * pipeline是由single cycle machine改的，因此硬體也不可共用 * 理想情況下，獲得的加速約等於stage數 * 實際上因為下列情況無法達到理想加速 1. stage分割不平衡 2. pipeline register有延遲時間 3. data hazard和control hazard 4. 填滿和清空管線的這段時間硬體使用率不到100% :::success :bulb: 優點: pipeline can overlap the execution of multiple instructions to improve performance(throughput) ::: :::info :warning: 缺點: 實作難、硬體成本高 ::: ### 專為管線化設計的指令集--MIPS 1. **所有MIPS指令都有相同的長度** * 這個規定可以讓管線的IF、ID變得簡單 2. **只有少數幾種指令格式，且每個指令的來源暫存器都在相同的位置** * 這個規定讓我們可以在ID階段對指令進行解碼的同時讀取暫存器檔案 3. **MIPS中只有載入指令或儲存指令會存取記憶體** * 可以在EXE階段計算記憶體位置，並在MEM階段存取記憶體 * 若非如此，則這兩階段必須合併 4. **運算元必須在記憶體中對齊** ### 理想管線的執行時間 * 假設有S個stage N個指令，則需要S+(N-1)個clock cycle通過管線 * 第一個指令在第S個clock執行完畢，而之後每一個clock都有一個指令完成，故N個指令要S+(N-1)個clock cycle * <font color="red">pipeline的理想CPI = 1</font> ## 重點二 管線資料路徑 ### 管線資料路徑的設計 * 和multicycle machine相似 * 盡量平衡各步驟的執行時間 * 限制一個stage只能使用一個主要功能單元 * 加入管線暫存器，儲存上一個階段的結果以供下一個階段使用 ### 五個stage * IF: 指令擷取 * ID: 指令解碼與讀取暫存器 * EXE: 執行運算或計算記憶體的位址 * MEM: 資料記憶體存取 * WB: 寫回 ### 管線的效能 * <font color="red">減少最長stage時間才能改善pipeline的效能</font> * <font color="red">管線化只改善了throughput，不能減少個別指令的執行時間</font> ## 重點三 管線控制單元 * RegFile被設計成在前半周期寫入(WB)，後半周期讀取(ID)，這樣讀取到的才會是最新的值，避免同步問題 * control signal 在 ID 階段產生 * <font color="red">把RegDst移到EXE stage</font>，這樣前兩個stage就可以完全不使用control signal * EXE stage * **RegDst** * ALUop1 * ALUop2 * ALUsrc * MEM stage * MemWrite * MemRead * Branch * WB stage * MemtoReg * RegWrite :::info 在single/multi cycle machine中，需要edge triggered 因為在一個cycle time中，記憶體位址和要寫入的資料可能發生改變 讓data memory edge triggered可以避免一筆資料寫入兩個不同的位址 ::: :::info 在pipeline中data memory可以不用edge triggered，因為pipeline register會將資訊存好，下一個clock來的時候只有一個記憶體位址和要寫入的資料可以進到data memory ::: :::info PCsrc會在MEM stage生成，決定branch要不要跳 事實上可以移到EXE stage就生成 **好處是**: 當發生control hazard時可以少暫停一個cycle **壞處是**: 把生成PCsrc 的 AND gate 移到 EXE stage時可能會增加EXE stage的時間，進而增加clock cycle time而影響效能 ::: ## 重點四 Hazard * structural hazards * 硬體資源不夠多，導致在同一時間內要執行多個指令卻無法執行 * data hazards * 管線中某一指令需要用到前面指令尚未產生的結果(data dependency)，也就是執行的指令所需要的資料還無法取得 * control hazards * 當分支指令還沒決定要不要跳的時候，後續的指令已進入管線中。 ## 重點五 Structural hazards ### 解決方法 1. 加入足夠多的硬體使得在任一clock cycle中，不會有不同指令使用相同階段的硬體資源 2. Stall * 讓會發生structural hazard的指令錯開，以避免在同一個clock cycle使用相同硬體資源 ## 重點六 Data hazards ### 軟體方式解決 * 利用compiler插入足夠多的nop指令 * 讓有data hazard的兩個指令距離大於2 * 利用compiler重排指令順序 * 讓有data hazard的兩個指令距離大於2 * compiler不一定能在不影響程式的正確性下，找的到可以消除data hazard的指令順序，最後還是要靠插入nop解決 ### 硬體方式解決 * 不是load-use的data hazard可用forwarding來解決 * <font color="red">load-use data hazard只能用stall 1 cycle + forwarding來解決</font> :::info RegFile前半周做寫、後半周做讀也可以消除可能的data hazard ::: ### hazard detection(硬體方式) * 引入forwarding unit (combination circuit) :::info hazard detection unit在ID stage forwarding unit在EX stage ::: **偵測步驟** 1. 偵測目前指令是否要寫入暫存器 2. 偵測目前指令的rd與他之後指令的rs、rt是否相同 * EX hazard (偵測目前指令與下一個指令是否有data hazard) ```MIPS sub $s2, $s1, $s3 (MEM) and $s12, $s5, $s2 (EX) ``` ```clike=1 //目前指令與下一個指令有data hazard if(EX/MEM.RegWrite && EX/MEM.Rd != 0 && EX/MEM.Rd==ID/EX.Rs) Forward A = 10 //MEM時從EX/MEM送給下一個指令的Rs if(EX/MEM.RegWrite && EX/MEM.Rd != 0 && EX/MEM.Rd==ID/EX.Rt) Forward B = 10 //MEM時從EX/MEM送給下一個指令的Rt ``` * MEM hazard (偵測目前指令與下下一個指令是否有data hazard) ```MIPS sub $s2, $s1, $s3 (WB) and $s12, $s2, $s5 (MEM) or $s13, $s2, $s6 (EX) ``` ``` clike=1 //目前指令與下下一個指令有data hazard if(MEM/WB.RegWrite && MEM/WB.Rd != 0 && MEM/WB.Rd==ID/EX.Rs) Forward A = 01 //WB時從MEM/WB送給下下一個指令的Rs if(MEM/WB.RegWrite && MEM/WB.Rd != 0 && MEM/WB.Rd==ID/EX.Rt) Forward B = 01 //WB時從MEM/WB送給下下一個指令的Rt ``` * **上面的MEM hazard detection code會有問題** * 當MEM階段和EX階段沒有data hazard，WB階段才和EX階段有data hazard * MEM和EX有，WB和EX就沒有，因為EX需要最新資料應該要來自MEM <font color="red">修正如下</font> ``` clike=1 //目前指令(WB)與下下一個指令(EX)有data hazard //則下一個指令(MEM)和下下一個指令(EX)不能有data hazard if(MEM/WB.RegWrite && MEM/WB.Rd != 0 && NOT(EX/MEM.RegWrite && EX/MEM.Rd != 0 && EX/MEM.Rd==ID/EX.Rs) && MEM/WB.Rd==ID/EX.Rs) Forward A = 01 //WB時從MEM/WB送給下下一個指令的Rs if(MEM/WB.RegWrite && MEM/WB.Rd != 0 && NOT(EX/MEM.RegWrite && EX/MEM.Rd != 0 && EX/MEM.Rd==ID/EX.Rt) && MEM/WB.Rd==ID/EX.Rt) Forward B = 01 //WB時從MEM/WB送給下下一個指令的Rt ``` :::warning :warning: :warning: :warning: :warning: :warning: :warning: 如果沒有要求rd != 0則會發生錯誤 ``` MIPS sub $0, $3, $4 ($3=500 $4=200) add $2, $1, $0 ``` 1. R-type指令，會寫入暫存器 2. EX/MEM.rd==ID/EX.rt 3. ForwardB = 10 在MEM stage從EX/MEM送給rt 在上面的情況會把 300 forward到add的$0 但$0只能是constant 0 所以會發生錯誤 ::: ### load-use data hazard * 引入hazard detection unit in ID stage * <font color="red">會在EX和ID階段偵測</font>連續指令是否存在有load-use data hazard * 如果有的話會暫停IF ID兩個stage的指令更新 * 暫停實際上是將該stage的**控制信號清成0(flush)**，並且**暫停更新PC** (IF保留)**和IF/ID** (ID保留) **的內容** **偵測步驟** 1. MemRead = 1? (lw?) 2. **EX stage中的rt是否和ID中的rs rt相同** (lw要看rt) * lw在ID stage結束後，結果存到ID/EX，下一個clock cycle走到EX後hazard detection unit偵測到load-use ``` MIPS lw $2, 20($1) and $4, $2, $5 or $8, $2, $6 ``` ```clike=1 if(ID/EX.MemRead && (ID/EX.Rt==IF/ID.rs)or(ID/EX.Rt==IF/ID.rt)) stall pipeline ``` :::info 若沒有forwarding unit，則load-use要暫停2個clock ::: ### Full Forwarding Path 1. EX/MEM - ALU 2. MEM/WB - ALU 3. MEM/WB - Data Memory * lw後面接著sw，使用相同的rt欄位 4. EX/MEM - RegFile(後方的XOR) * 用來比較兩暫存器是否相等 ## 重點七 資料相依 ### RAW (True dependency) Read After Write: 讀在寫之後，先寫再讀 ``` MIPS add s0, s1, s2 sub t1, s0, t2 ``` > 這裡sub要讀的s0暫存器要等前一個指令add寫入，讀到的才會是正確的值。 ### WAR (Anti-dependency) Write After Read: 寫在讀之後，先讀再寫 ```MIPS add s0, s1, s2 sub s1, t1, t2 ``` ### WAW (Output dependency) Write After Write: 寫在寫之後，先寫再寫 ```MIPS ``` :::success 在MIPS 5 stage pipeline只有RAW(Read After Write)會有data hazard ::: 可以透過重排指令來避免load-use的stall，進而增加管線效能，但前提是指令間必須沒有data dependency ## 重點八 Control hazards ### 解決control hazard的方法 1. stall(硬體) / 插nop(軟體) 2. branch prediction (硬體) 3. delay slot (軟體) 4. Predict (軟體) **<只能減少>** * 只能減少部分由高階語言轉成組合語言所產生的branch指令(讓branch數量變少) ex: if-then else * for/while loop產生的branch指令無法消除 5. 提早到ID決定branch要不要跳 **<只能減少>** ### 減少分支延遲 * MIPS將決定branch會不會跳移到ID stage * 將原本在EX stage用來計算跳躍目的位址的adder移到ID stage * 在RegFile後面加上XOR來比較兩個來源暫存器是否相等 * 為了清除IF階段的指令，還要在main control上加一條IF.flush的控制信號線 * 再加一條forwarding path，可以從EX/MEM送到ID stage供branch比較暫存器是否相等 :::info 移到ID stage決定要不要跳反而會多出R-type+branch這種要stall 1次的情形 而lw+branch從stall 1次變成了要stall 2次，但好處是猜錯的時候penalty變小 (flush 3 stage -> 1 stage) ::: ### Dynamic brench prediction * Branch Prediction Buffer(Branch History Table) * 由分支指令位址較低的部分作為索引的小型記憶體 * 這個記憶體包含一個位元來檢查目前這個branch上次有沒有跳(每個beq會有各自的紀錄) * 可以幫助預測branch會不會跳 * 放在ID stage * 猜錯的時候才會更新 * Branch Target Buffer * 會把之前跳過的**目的位址**或**目的位址的指令**存起來(類似cache) * 可以幫助預測跳躍目的位址 * 放在IF stage * 1-bit prediction * 2-bit prediction * steady state下準確率會比 1-bit prediction好 * correlating predictor * 同時使用**現在這個branch和其他所有的branch**的執行資訊來判斷 * tourment predictor * 在每個branch使用多個預測器，看哪個效果好就用哪個的結果 ### delay branch * software base solution * 由compiler和assembler達成 * 將不論分支是否成立都會執行到的指令放到delay branch slot中而延後執行後面的指令 ::: info 不論分支條件是否成立都會執行到的指令稱為安全指令，並且必須確保多執行到安全指令不會影響程式的正確性 ::: #### 安排安全指令到delay slot的三個方法 1. from before * 分支指令以上都是找安全指令的範圍 2. form target (往上跳的branch) * 若from before找不到，且<font color="red">分支經常發生</font> * 分支指令到分支跳躍目的位址之間都是找安全指令的範圍 * <font color="red">複製</font>安全指令到delay slot 3. from fall through (往下跳的branch) * 若from before找不到，且<font color="red">分支不常發生</font> * 分支指令到分支跳躍目的位址之間都是找安全指令的範圍 * <font color="red">移動</font>安全指令到delay slot :::info delay branch是一個簡單而有效率的方法 隨著pipeline stage數增加及每個周期分發的指令數增加，branch的delay越來越長 單一個delay slot已經不夠使用，取而代之的是代價更高但更具彈性的動態方案(branch prediction) ::: ## 重點九 進階的管線 ### Multiple Issue 透過複製pipeline元件，讓一個clock cycle執行多個指令，增加平行度 4-way multiple-issue -> CPI = 0.25 / IPC = 4 ### Static (compiler) * compiler配對沒有資料相依的指令，配成issue slot * 重排指令 ### Dynamic (CPU) CPU在runtime判斷指令流，解決hazard 把執行完的指令先存下來，確定沒有問題再寫入，有問題的話移除計算結果 ### Speculation 猜指令是否沒有相依 * sw -> lw (runtime才能計算) * beq是否跳 ### Loop unrolling 把迴圈解開，增加平行度 Register renaming: a[i] = a[i] + 1 實際上每一個a[i]都是獨立的 ### Super pipeline * increase the depth of pipeline to increase clock rate ### VLIW (Very Long Instruction Word) * 一種指令集，可以將多個彼此獨立的指令打包成一個長指令(VLIW) * static multiple issue ### Superscalar * 進階的管線，可以讓處理器在一個cycle time執行多個指令 * dynamic multiple issue ## 重點十 管線資料路徑例外的處理 ### 例外(exception)和中斷(interrupt) * exception: 從<font color="red">處理器外部</font>發生了非預期的事件而擾了程式的執行 * interrupt: 從<font color="red">處理器內部</font>發生了非預期的事件而擾了程式的執行 ### 如何處理例外 * 當exception產生時，機器會將引發exception的指令存到EPC(Exception Program Counter)中，然後將控制權轉到位於特定記憶體位址的OS中 * 完成excption的處理後，OS可以選擇 * 利用EPC得知原程式應該從何處繼續執行下去 * 終止原程式 ### 如何得知例外原因 1. MIPS用原因暫存器(cause register)來儲存資料並透過暫存器的欄位來指出發出exception的原因 2. vectored interrupt，控制權轉換的位址是由exception的原因決定，OS透過被觸發的位址來得知exception的原因 ### pipeline例外處理的步驟 1. Flush IF ID EXE 2. 盡可能的讓造成例外之前的指令執行完畢 3. 將造成例外的指令的記憶體位址(PC+4)存到EPC中 * 因為IF階段取得指令後是把PC+4沿著管線往後傳 4. 呼叫OS來處理 5. 返回使用者程式碼 ::: info 在EX stage加入cause register和EPC EPC是存放PC+4，所以要取得真正造成exception的指令要先 -4 ::: ### 非精確中斷