Computer Organization - Ch4 Processor

Chapter 4   Processor

4.1   Data path and control signal

• MIPS 指令集合實作概觀圖

• 指令格式（複習）

• Decoder — the first-level control unit
• RegDst：1 是寫入[15 : 11]的reg、0是寫入[20 : 16]的reg，只有在把值寫入register裡時才有用
• ALUSrc：1 是用sign-extend 立即值、0是用register的值（ALU source
• MemtoReg：1 是取input讀入的位址的值、0是直接用ALU result 的值，只有在把值寫回register裡時才有用
• Regwrite：1 是將計算結果寫回register
• MemRead：1 唯有Read memory使用 (lw)
• MemWrite：1 唯有Ｗrite memory使用 (sw)
• Branch：1 唯有branch使用 (beq)

• ALU control — the second-level control unit
• 先以兩個bit分類三種類型：load/store , branch , R-type，如果是R-type再以ALU function細分

• 實作jump指令
• upper 4 bit PC+4 [31:28] ．26 bit jump address [27:2]．2’b 00 [0:1]

• single-cycle, multicycle, and pipelined implementations of a computer
• Single Cycle：希望所有指令皆在一個Cycle執行完畢，所以最快指令需等待最慢指令。
• Multi Cycle：為了解決Single Cycle效率不好的情況，讓最快的指令不必去等待最慢的指令。但還是一樣有浪費掉的時間，因為每個步驟所花的時間也是必需一樣的。
• Pipeline：主要的目的是希望在同一個時間內能執行多道指令，增加效能。

4.2   Pipeline

• Pipeline stage

1. IF: 從記憶體擷取指令（fetch）
2. ID: 解碼指令並同時讀取暫存器的值（decode）
3. EX: 執行運作或計算位址（execute)
4. MEM: 存取資料記憶體中的運算元（memory）
5. WB: 將結果寫回暫存器中（write back）

• Pipelined Datapath：由左而右的指令流動有兩個例外

1. 寫回階段：結果儲存回暫存器檔案
2. 下一個PC的選擇：遞增的PC與由MEM階段來分支的位址選擇
• 在每個stage之間需要暫存器把上一個cycle的值保存住，且注意WB for load要把write register的位址傳下去

• Pipelined Control：我們在指令解碼時（ID）產生訊號，因此訊號只有在EX、MEM、WB使用
• EX：RegDst、ALUOp、ALUSrc          
• MEM：Branch、MemRead、MemWrite
• WB：MemtoReg、RegWrite 

4.3   Hazards

• Hazards的分類
• Structure hazards：不同指令同時對某硬體做存取
• Data hazard：當管道因為某一步驟必須等待其他步驟而停滯，起因於兩道指令俱有相依性，例如add,lw...
• 可使用forwarding解決
• load-use data hazard，即使使用forwarding還是要stall一個cycle
• code scheduling 可避免hazard。
• Control hazards：條件分支所造成的等待延遲
• Stall on Branch：假設有足夠額外的記憶體，可以在ID stage測試暫存器、計算位址、更新PC值，此方法無論跳不跳都要stall一個cycle
• Branch Prediction：先做錯了再換

1. Not Taken
2. Static Branch Prediction：根據跳躍類型預測，例如loop猜會往回跳，if猜往前跳
3. Dynamic Branch Prediction：會考量每一個分支指令的特性，程式運作過程中會改變對一道分支的預測，假設之後的Branch會照著「趨勢」走。

• R type Data Hazard
• 放入ALU的暫存器一定是這兩個：ID/EX.RegisterRs , ID/EX.RegisterRt
• 當以下情況發生時，預見了Reg會被改寫(EX)：EX hazard是10、MEM hazard是01
• 1a. EX/MEM.RegisterRd(寫進的) = ID/EX.RegisterRs(要讀的) 
• 1b. EX/MEM.RegisterRd = ID/EX.RegisterRt 
• 2a. MEM/WB.RegisterRd = ID/EX.RegisterRs 
• 2b. MEM/WB.RegisterRd = ID/EX.RegisterRt
• 只有Regwrite (改值) 的時候forwarding：
• EX/MEM.RegWrite, MEM/WB.RegWrite(會寫入而改變值)
• 被寫得不可以是＄zero暫存器
• EX/MEM.RegisterRd ≠ 0, 
• MEM/WB.RegisterRd ≠ 0
• 要把forwarding unit 放在他會用到的stage(EX)以避免傳遞所產生的代價

• Double Data Hazard 

• 這邊是hazard混亂的情形，line 1跟line 2、3都有data dependence。程式碼是依序執行，很明顯的line3當中$1的資料來源是來自於line2的結果，並不是由line1提供，所以line1的$1是不能Forwarding給line3，若Forwarding給line3，line3的結果是一定錯。

• Load-Use Data Hazard

• load用forwarding無法完全解決，因此需要加上stall解決
• Stall the pipeline
• ID/EX裡的暫存器(EX , MEM , WB) 做nop (no operation)
• PC和IF/ID暫存器不做更新 (這樣就會再做一次，達到stall的效果)
• hazard detection unit在stage 2 的原因：越早檢查越好，且在其他stage需要更多硬體

• 各種指令data harazd的解決方法整理
• 在R type之後遇有相依的R type, lw, sw
• 用 forwarding 解決，不會產生stall.
• 在 lw之後遇有相依的R type, lw, sw
• 由於這些指令在ex stage 即需要, 因此來不及 forward, 需要 stall 一個 cycle.
• 在R type之後遇有相依的beq，這些指令有兩種處理方式
1. 我們假設 equality test速度很快，因此只要在該 cycle之後拿到資料就可以 forward 過去，所以在 R type之後的beq不需要 stall.
2. 我們假設 equality test 需要的時間較長,不能在該 cycle 結束前拿到 forward 過來的資料並算完，所以需要 stall 一個 cycle.
• 在 lw之後遇有相依的beq，由於這兩個指令在 id stage 最後時需要 data，有兩種處理方式
1. 我們假設 equality test 速度很快，因此只要stall 一個 cycle 之後拿到 forward 的資料就可以算完,所以在 lw 之後的 beq 與 bne 需要 stall 一個 cycle.
2. 我們假設 equality test 需要的時間較長,不能在 stall 一個 cycle 之後拿到 forward 過來的資料並算完,所以需要 stall 兩個 cycle

• Branch Hazard
• 減少分支延遲：將分支位址加法器從EX移到ID，增加一條IF.Flush讓IF/ID可設為0 (nop)
• 分支預測

1. 假設分支不成立(Branch taken)
2. 一位元預測方法(1-bit prediction scheme)：上一步怎樣，下一步就猜怎樣(猜錯一次就反向)
3. 二位元預測方法(2-bit prediction scheme)：猜錯兩次才反向，強烈偏向發生或不發生的分支，只會猜錯一次

• 分支延遲間隙
• 在分支指令之後的指令，即使在與前一個分支指令流向分歧，依然會被處理器所執行，在加強後的編譯器的處理下，分支所帶來的延遲將顯得不明顯。
• from before 與分枝無關，情況最佳
• from target or fall-through 可能做了白工，但程式仍會正確的執行

• 指令階層平行性 Instruction-Level Parallelism (ILP)
• 多重派發(multiple issue)：多道指令在一個時脈週期中發出的方法
• VLIW(very long instruction word)：同時發出許多指令互為獨立的指令集架構形態
• 超純量(superscalar)：每個時脈週期能選擇多於一道指令給處理器的先進管道化技術
• 動態排程(dynamic pipeline scheduling)：重新安排指令順序以避免停滯的硬體支援
• 亂序執行(out-of-order execution)：pipeline中當一個指令受阻時無需造成後面指令等待的情況
• 猜測(speculation)：編譯器或處理器猜測結果以消除相依性關係的方法
• 重序緩衝器(reorder buffer)：在超純量中，記錄結果直到各結果可安全的被寫回記憶體或暫存器中的緩衝器．
• 暫存器重命名 ：再迴圈展開中(loop rolling)，消除名稱相依性的方法