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

contributed by <`PeterTing`>、<`jack81306`>

## 整體作業
- [ ] 背景知識
- [x] 基本指令
- [x] 基本架構
- [x] pipeline 架構
- [ ] Hazard
- [x] 解析 [B09 microarch](https://hackmd.io/s/r1Olsp_og)
- [x] 第一部影片
- [ ] 實作程式碼

## MIPS 背景知識

### 指令介紹

#### R type 指令
* R 型指令是<b>不會使用到記憶體或者是一般常數</b>運算類型的指令.

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

#### I type 指令
* I 型指令是<b>讀寫記憶體或者是包含常數運算</b>的指令.

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

#### J type 指令
* J 型指令是<b>對下一條指令的地址進行跳轉</b>的指令.

* 指令架構如下

* J 型指令,裡儲存地址的 bit 雖然只有26個,卻可以儲存 28 個 bits 的地址,是因為<b>每一條指令都是 4 個 byte ,因此每一條指令地址都是 4 的倍數,也就是說末兩位為 0,所以就可以把它省略掉嚕.</b>
* 而另外四個 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 的大小。

## 參考資料
- [講義](http://www.cs.utexas.edu/users/mckinley/352/lectures/12.pdf)