microarch 相關背景知識、在限制中實做

contributed by <PeterTing>、<jack81306>

整體作業

• 背景知識
  • 基本指令
  • 基本架構
  • pipeline 架構
  • Hazard
• 解析 B09 microarch
• 第一部影片
• 實作程式碼

MIPS 背景知識

指令介紹

R type 指令

• R 型指令是不會使用到記憶體或者是一般常數運算類型的指令.

• 指令架構如下
  

  • op : 全名為 operation code,這六個 bit 是拿來指定處理器內部各個部件的行為,也是拿來辨別這個指令的功能.
  • rs,rt :兩個 register 來源.
  • rd :目的地 register.
  • shamt :shift amount.
  • funct : 一樣是拿來指定處理器內部的行為.

I type 指令

• I 型指令是讀寫記憶體或者是包含常數運算的指令.

• 指令架構如下
  

  • rt,rs: 和 R 型指令不同的是 I 型指令中的 rt 通常是拿來當作目的地,rs 則是來源或者是偏移地止的起點.

J type 指令

• J 型指令是對下一條指令的地址進行跳轉的指令.

• 指令架構如下
  

• J 型指令,裡儲存地址的 bit 雖然只有26個,卻可以儲存 28 個 bits 的地址,是因為每一條指令都是 4 個 byte ,因此每一條指令地址都是 4 的倍數,也就是說末兩位為 0,所以就可以把它省略掉嚕.

• 而另外四個 bits 則是在 program counter 內

MIPS 的抽象架構

• Data 可能來自 ALU 的結果,或者是 Data memory,但是在紅圈1處形成一個交叉,這時就必須加入 multiplexor 來處理資料的流向.

  • multiplexor: 從多個輸入中,根據控制信號來決定輸出.
  • 控制信號被放在指令裡,會根據指令的不同來傳遞不同的信號給各個 multiplexor.

• PC 是指向指令的地址,處理器在運作時,如果這條指令是非 j type 型的指令,則下一條指令的地址就是 PC+4.如果這條指令是 branch 的指令,則下一條指令的地址是 PC+4 再加上偏移地址.這時會在紅圈2產一個交叉,一樣要加入 multiplexor 來處理資料的流向.

CPU 元件介紹

加入 control lines 的 mips 抽象架構

Decoder 介紹 (第一階 control unit)

• Decoder 位於紅圈 1 的地方,Decoder 是根據指令裡的 opcode 來控制各個元件的行為

  • 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)

• 各種指令的 opcode

ALU 介紹

• ALU,即算術邏輯單元,位於紅圈 2,可以根據 ALU Control 送過來的控制訊號,對兩個輸入值做 ADD、SUB、AND、OR、SLT 等基本的運算,然後將運算的結果輸出.

• ALU 放大圖
  

ALU Control 介紹

• ALU Control 位於紅圈 3,負責輸出控制信號給 ALU，它接收了指令中的 Function code 部份及由 Control 送出的 ALUOp 兩個信號輸入，詳細數值如下圖.

分析指令 datapath

R type 指令執行路徑

• 上圖是 R type 指令的 datapath ,可以觀察到 R type 指令並部會使用到整個處理器.
  • 在 1 號位置被截斷的原因在於說,R type 指令把應要寫入的 register 地址存放在 rd (也就是第 11 到 15 bit),而不是第 20 到 16 bit.
  • 2 號位置被截斷的原因是資料是儲存在 register 而不是指令裡,3 號位置同理.
  • R type 指令沒有使用到記憶體(4 號位置).
  • R type 指令不進行跳轉(5 號位置).

Memory access 指令執行路徑

• 上圖是有使用記憶體指令的 datapath.(e.g. lw,rw)
  • 因為 lw 或 rw 是 I type 指令,所以儲存需要寫入或讀取的 register 是放在第 16 到 11 個 bit(1 號位置).
    
  • 2 號位置會根據讀取或寫入指令的不同而截斷其中一個,如果是讀取就不會使用到 write data,反之則不會使用到 read data.
  • Memory access 指令不進行跳轉(3 號位置).

Branch 指令執行路徑

• Branch 指令為依照比較結果來決定是否要跳轉.(e.g. beq,bne)

  • 比較不需要進行寫入(1,2 號位置).
  • 也不需要使用到記憶體(3 號位置).

• Branch 計算跳轉地址的方式是把 pc+4 和偏移地止進行相加.
  

J type 指令執行路徑

• j type 指令是直接跳轉到該地址,因此只會使用到上半部的元件.
  • 地址的組成方式是取 pc+4 前面 4 個 bit 再加上指令內儲存的偏移地址(一樣要 shift 2 bit).
    

Pipeline 介紹

• Pipeline:多道指令以重疊（overlapped）方式執行，可增加一個程式單位時間內可完成的指令，但無法減少每個指令的執行時間。下圖以一個洗衣房的流程講解.

• 來講解以上以上那張圖的概念，現在我們有四件事情要做，分別為洗衣服，烘乾衣服，摺衣服，和放進衣櫃。當沒有 pipeline 時我們需要等四件事情全部都做完，才能進行下一個輪迴，若現在可以進行 pipeline ， 則可以在別人烘衣服的時候使用洗衣機，在別人摺衣服的時候使用烘衣機，讓道程序都不會空下來，可以有效地進行利用，這樣將可以提升設備使用率.

• 再 mips 裡,instruction 可以分成五個步驟來執行.

  • IF : 指令抓取 (Instruction fetch)
  • ID : 指令解碼 (Instruction Decode)
  • EX : 執行 (Execution)
  • MEM : 記憶體存取 (Memory Acess)
  • WB : 寫回運算結果或是記憶體中的資料 (Write Back)

MIPS Pipeline Datapath with Control

• Pipeline register(位於紅圈處):用來分開每一個pipeline stage，以便儲存它所對應stage所產生的資料，也可以用來緩衝各stage間運算速度之不一致,而在指令解碼時（ID）產生的訊號，並不是直接送到各元件,而是送到 pipeline register,一階一階往後送.

Hazard 介紹

Hazard 有三種

• Stucture Hazard : 需要的硬體正在被其他的指令使用。

• Data Hazard ： 兩道指令具有相依性，即下一道指令需要上一道指令的運算結果。

  • 例如：有兩條指令，相加和相減，而相減指令的其中一個數值需要相加後的結果，相減的指令就會需要等待相加的指令。
    

    
    

  • 圖中有兩行 bubble ，即代表要 stall 兩個 cycles

• Control Hazard ： 條件分支造成等待延遲

  • 下一條指令的位置取決於條件分支之運算結果

解決方案

• Structure Hazard : 在 mips 裡,將指令和資料放在不同的記憶體中.
  

• Data Hazard

  • Forwarding : 不要等資料存到 register 中,直接把資料送進 ALU 的其中一個來源.
    

    • 需要多一條 wire

  • load-use data hazard : 即使使用 forwarding ，還是會 stall 一個 cycle

    • 

  • Code Scheduling : 重新安排程式碼之間的順序.

    • 

• Control Hazard

  • Stall : 先等分支結果出來再抓取下一條指令
  • Predict ： 只有猜錯時會造成 pipeline stall
    • untaken
    • static Branch Prediction : 根據跳躍類型預測，ex : loop 猜往回跳，if 猜往前跳
    • Dynamic Branch Prediction : 根據硬體內所存之最近預測結果，來猜測最有可能之結果。

題目解析

1.Stuck at 0 left of cut

做了 1: Stuck at 0 left of cut 的修改，sw

$s1,0($s2) 能否運作？這樣的修改會使得哪些程式無法運作，請列出至少兩項組合語言列表

• 截斷的這條線路是傳送 regwrite 訊號的線路,因此無法告訴 register 要把資料存進去,這樣會使要存資料進 register 的指令通通失效.
• e.g.

add $t0,$t1,$t2
lw $t0,0($t1)

2

做了 2 的修改後，以下程式能否運作？解釋並提出可運作的版本

add $s1, $s1, $s1
add $s1, $t0, $t1

• 截斷這條線路,會讓 rs 的 forward 失效,但是在這支程式裡,並不需要 forward data,因此這支程式可以運作.

3

做了 3 的修改後，以下程式能否運作？

addi $s2, $zero, 2
addi $s1, $zero, 2
beq $s2, $s1, exit

• 這條線路是把偏移地址和 pc+4 相加的線路,如果截斷這條線路的話,就不能執行 condition branch(e.g. beq,bne),所以上述程式無法運作.
• 但是仍然可以使用 j type 指令.可以修改成

cmp:
slt $t0,$s1,$s2
slt $t1,$s2,$s1
xor $t0,$t0,$t1
sll $t0,$t0,2
add $ra,$ra,$t0
jr $ra

addi $s2, $zero, 2
addi $s1, $zero, 2
jal cmp
j exit
...

• 利用了 jal 會記錄當前位置的特性,如果兩者相等就跳回 pc+4,不相等就跳到 pc+8,而 pc+4 則會在跳到 exit.

MIPS 主要缺陷

• 分支延遲

  • 在所有的 MIPS 處理器中,跟在分支指令之後的指令,即使在與前一個分支 指令流向分歧之後,依然會被處理器所執行,因此在之後的 MIPSII體系中,加 入了 Branch-likely 指令,在處理類似的狀況時,在分支指令其後的指令只 有在前一個分支被接受時,才會被執行,不過除非自行指定分之後的指令,在 加強後的編譯器的處理下,分支所帶來的延遲將顯得不明顯。

• 載入延遲

  • 在 MIPS I指令集中,load 指令將無法再次載入才剛被 load 指令本身所載 入的資料,若是有需要再度載入,那麼必須在兩個 load 流程之間,使用其他 指令來區隔,甚至是使用空指令來空轉一週,以便讓 load 指令可再度進行載 入。

• 浮點運算單元的問題

  • 由於浮點運算需要耗費多個處理器時脈週期來進行,因此在 MIPS 處理器架 構中,大多會有獨立的浮點運算處理管線,構成內部的輔助處理器架構,由於浮 點運算單元可以與其後的指令並行處理,因此當並行處理的指令要去存取尚未計 算完成的浮點運算結果暫存器時,處理器便會停止執行,因此這部份的處理也需 要大量的編譯器最佳化。

架構比較

Pipeline

• MIPS
  最簡單的體系結構之一,體積小、耗能比低。但MIPS有"分支延遲" 以及"載入延遲"兩個明顯的缺點,MIPS 使用編譯器来解决上面的兩個問題。因为 MIPS 最初的設計思想是使用簡單的 RISC 及其他軟體技術,来達成 RISC 的完整概念。
• ARM’s Shifter
  shifter 是 ARM 中很重要的概念,他可以提高運算邏輯的速度,跟同樣功能的 adder/shift register 相比,效率更高,但是也占用更多的芯片面積

指令結構

MIPS 有 32bit 及 64bit architecture,但是 ARM 只有 32bit architecture (ARM11 局部 64 位)
MIPS 是開放式的架構,可在開發的內核中建立自己的指令,而 ARM 是在每個指令結構以 4bit 的 condition code 決定。

Register

由於 MIPS 內核中有 32 個 register,相對於 ARM 只有 16 個,設計天生上的優勢使得同等性能下, MIPS 的芯片面積及功耗比較小。ARM 有一组特殊用途 register cp0-cp15,可以使用 MCR,MRC 等指令控制;相對應的, MIPS 也有 cp0-cp30,使用 mfc0,mtc0 指令控制。

地址空間

MIPS 起始地址是 0xbfc00000,會有 4Mbyte 的大小限制,但一般 MIPS 芯 片都會採取一些方法解决這個問題。而 ARM 没有這種問題。在新版的 MIPS24K 起始地址往後移,有了 16byte 的大小。

參考資料

• 講義