# 課程資訊
張榮貴的計組 第一章禮拜四之後遠距上課
1-3章 期中考
4-5章 期末考
會偷點名

# 第一章 概論
## Introduction
x86 vs ARM 是不同的CPU處理器架構
* x86在高性能計算和桌面應用中較為突出
* ARM有著低功耗的優點，常見於移動設備、嵌入式系統和物聯網領域

電腦的分類
* 個人電腦: 通常為x86系統
* 嵌入式系統: 給特殊用途電子產品的系統(非x86架構的系統)
* Real-time constraint: 反應時間低
* Low power: 低功耗
* Code density: 空間小
* 伺服器: 提供服務的電腦系統
* Availability: 高可用性，也就是穩定性
* Scalability: 可擴展性
* Throughput: 高吞吐量
## Performance (最重要)
可以從以下幾個面向衡量電腦的Performance
* execution time: 執行一個job所需的時間，有數種衡量方式
* Elapsed Time: 總耗時，含I/O等等
* CPU time: 僅考慮job在CPU上執行時所消耗的時間
* 又可以細分成System CPU time跟User CPU time
* Response Time (latency): 指的是job到達至開始執行所需的時間
* Throughput (bandwidth): 單位時間內能處理的job數量

提升Performance可以從以下方面著手:
* 硬體:
* increase clock rate
* 降低CPI
* 軟體:
* 降低編譯後的指令數

重要概念:
clock cycle time: 執行一次循環所需時間
clock frequency: 電腦的時鐘頻率 (ex: 2 GHz代表每秒有20億次循環)
CPI: 每一條指令需要幾個循環才能完成

clock frequency / CPI 代表每秒可以執行的指令數
### MIPS (必考)
MIPS(Million Instructions Per Second)代表每秒能夠執行的百萬條指令數量，可以用來當作衡量電腦性能的指標之一

MIPS = 指令數 / (執行時間 * 10^6)

觀念釐清: MIPS不能直接代表真正的performance(執行時間)，甚至可能跟performance相反

### Benchmark
* 衡量性能的最好方式是透過執行實際應用程式來確定
* 可以將硬體拿去跑Benchmark(基準測試，可以當作是專門測性能用的application)來衡量Performance
* 例如SPEC(Standard Performance Evaluation Corporation)這家公司便提供了一系列不同類型的基準測試，以進行性能評估

Benchmark可以分成以下幾類:
* Real application: 直接拿實際的應用程式來衡量性能
* modified application: 稍微修改實際的應用程式後拿來衡量性能
* Kernals: 專門用來衡量核心性能的Benchmark
* Toys Benchmark: 用來衡量應用程式的一小部分性能，代表性較差
* synthetic benthmark: 拿模擬實際的應用程式來衡量性能

使用Benchmark測試後，可以根據run time來作為衡量Performance的依據
1. 算術平均
2. 幾何平均...

### Amduhl's law (真必考)
提升性能後的總執行時間 = 沒影響到部分的執行時間 + (受影響部分的執行時間 / 該部分佔整體的比例)

**fraction enhance** = 提升性能部分佔整體的比例

**speedup** = 提升性能前的總執行時間 / 提升性能後的總執行時間

ex: 某程式原執行時間為100秒，其中乘法運算所花的時間為80秒。若要將程式執行速度提升為原先的4倍(speedup = 4)，乘法運算速度需要提升多少倍?

25 = 20 + x
x = 5
所求 = 80 / 5 = 16倍

ex: 假設執行某程式需要40%的CPU time 跟60%的I/O time，換上一顆效率為10倍的CPU後，執行程式的速度能提升多少?

原: 40+60
新: 4+60

speedup = 100/64 = 1.56

### 優化Performace
* 透過升級硬體來增加clock rate
* 透過改善processor organizations來降低CPI
* 透過優化編譯器來降低指令數跟CPI(因為不同類型的指令所需的時間也不同)
## Power wall (電腦的能量消耗)
電腦消耗的能量 = 動態能量消耗(switching，切換01狀態導致的能量消耗) + 短路(short circuit) + 靜態能量消耗(leakege)

## 各種觀念跟謬論
1. (x)只優化某一方面便可以優化整體性能
* 僅改善某一方面對於優化整體性能的幫助可能有限，因為沒有考慮到整體架構，也沒有考慮到該方面占整體的比例
2. (x)單方面的使用某個衡量performace的公式(如MIPS)作為整體性能衡量標準
* 衡量performace的公式可能無法兼顧到全局，故不能直接拿來衡量整體性能
3. (O)MIPS只能拿來衡量相同指令集架構下的Processor，因為不同指令集架構在執行相同任務時所需的指令數可能不同，便會影響到MIPS的衡量結果

# 第二章 組合語言指令
**Computer Architecture**(電腦架構):
由**Instruction Set Architecture**(指令集架構，又稱ISA)跟 **Machine Organization**(硬體架構)所組成
* Instruction set 是硬體跟軟體的溝通橋樑

* ALU 指的是算術邏輯單元
* 圖中架構的效率，越右邊越高

register是由flip-flop實作的，存取速度很快。但空間有限，故需要memory的幫助以儲存大量資料

## Memory Organization
* Memory是一維的陣列，每格大小為1 byte，並分配一個唯一的address
* 對於MIPS架構，每四個byte稱作"words"，存在裡面的資料通常是對齊的

## MIPS 指令種類

一個MIPS指令大小為32 bit(a word)，並分割成多個區域(field)，共有三種分割方式
* R-format instructions (跟register有關的指令)
* I-format instructions (跟immediate value或load、store有關的指令)
* J-format instructions (跟jump有關的指令)

MIPS指令範例
1. 想要的操作
2. 結果
3. 第一參數
4. 第二參數

設計理念: **Keep hardware simple via regularity** (透過規律來簡化硬體設計)

### R-Format Instructions
* opcode: 決定指令的類型(R-Format等等)
* rs: 作為指令第一個參數的register
* rt: 作為指令第二個參數的register
* rd: 存放結果的register
* shamt: 當有shift(左右移)運算時，用來決定要位移幾位；我opcode並非shift類型的指令，則本欄位為0
* funct: 決定該指令的功能

範例(Machine Language Instruction):

### I-format instruction
* opcode: 決定該指令的功能
* rs: 作為指令參數的register
* rt: 存放結果的register
* immediate: 作為輸入參數的常數值，最大可以有$2^{16}$個不同值

範例:

關鍵想法: 格式盡量與R-format相同以簡化
關鍵想法: 好設計需要折衷(compromise)

載入大數(超過16 bits):
MIPS中的一個register有32 bits，但immediate number的大小最多只有16 bits，若想要加上一個32 bits的數，需要拆分成兩步進行

Psudo指令:

addi \$t0,$t0, 0xABABCDCD

真實情況:
* 載入32 bits數字上半部至register at 中，下半部補0
* register at 跟 32 bits數字下半部做 or 運算
* 將at 的值加到 t0 中

### J-format instruction
* opcode: 用查表的方式決定這條是哪種指令
* target address: 要跳到的記憶體位址

例如:
* goto label (無條件)

## 基本 MIPS 語法
重點指令:

其他重要的還有
* li $s0, 0: 相當於 s0=0

### constant
把常數直接編進指令中(Immediate Operands)，如此一來便可節省時間

* 優點: 速度快
* 缺點: 較消耗空間，且能儲存的數有限

規則:
1. MIPS有一顆register專門存常數0，可以使用 $0 當作一顆永遠為0的register
ex:

beq $t0, $0, DONE # 若t0==0 跳至branch DOME

2. 對於其他常數，直接使用其數字，搭配後面有i的指令存取 (這些常數會直接儲存在記憶體中)
ex:

addi $s0, $s0, 4 # 將暫存器$29的值加4

設計理念: **Make the common case fast**

備註: 左右移指令(sll, srl, sra)不需要加i即可使用immediate value

### Load and store instructions
A[12] = h + A[8] 轉成MIPS組合語言:

lw $t0, 32($a0)     # 將A[8]載入到暫存寄存器$t0(假設$a0存放的是指向A陣列頭的指標)
add $t1, $s1, $t0   # 將$h和$t0相加，結果存放在$t1中 (假設變數h的值存在$s1中)
sw $t1, 48($a0)     # 將結果$t1存回A[12]

### Logical operation
and 運算:
* t0 = t0 & 0xFFF

or 運算:
* t0 = t0 | 0xFFF

左右移:
* sll: 左移
* srl: 右移，左邊補0
* sra: 右移，根據most significant bit 決定要補0還是1 (處理負數用)

### Decition instruction
相等判斷
* if(register1 == register2) goto L1

不相等判斷
* if(register1 != register2) goto L1

無條件判斷
* goto label (無條件)

小於判斷
* if(reg2 < reg3) reg1=1
else reg1=0

類似的指令有
* slti: 適用於immediate value
* sltu: 適用於unsigned value

branch instruction的底層

Loop: beq $9 $0 End
add $8,$8,$10
addi $9,$9,-1
j Loop
End:

* opcode= 4 (透過查表得到)
* rs: 9
* rt: 0
* immediate= 3 (代表要跳到下面3+1格的位置)

### Data transfer instruction
負責寫入跟讀取記憶體的操作
* 指令分成sighed 跟 unsighed，差別在於Signed形式中前面會根據正負性而補0或F

* 特性: 當需要儲存的變數多於register的數量時，須把比較不常用的變數放到memory中儲存，這個概念稱為spilling
* 特性: 一條MIPS的arithmetic(算數) instructions最多可以同時讀兩個register中儲存的內容，及寫入另一個register
* 特性: 一條MIPS的Data transfer instruction通常是讀一個register中儲存的內容，並寫入另一個register

註: 以上指令的偏移量是以word為單位計算(非1 byte)

### MIPS register細節
每條指令的參數來源都是register；**在MIPS中，共有32個register($0~$31)，每個register空間大小為32bits**
* $0 永遠是0
* $8 到 $15 = $t0 到 $t7 (用於儲存temp value)
* $16 到 $22 = $s0 到 $s7 (用於儲存數值)
* 除此之外，還包含了HI、LO 和 PC等register

### Procedure Conventions
指的是關於如何呼叫函式，以及如何在函式之間傳遞參數的一種約定或協議

約定包含了
* 函式呼叫
* 參數傳遞
* 寄存器使用
* Stack的使用

### 其他觀念
* Alignment and alignment restriction: MIPS要求儲存於memory中的資料是對齊的
* Register spilling: 指的是register大小不夠的時候，需要將資料暫存到memory中，會導致速度下降
* Endianess: MIPS指令屬於big endian

### MIPS Addressing
描述了MIPS如何計算和存取記憶體中的資料

* Register: register即為data 所在
* Immediate: 常數
* Disolacement: R1所指的地方加上偏移量，便是data所在
* Register indirect: R1所指的地方便是data所在

## Translating and starting a program
### Object file
Object file是組合語言經過組譯後的產物，包含了
1. Object file header: 包含了一些檔案的meta data
2. Text segment: 包含了可執行程式
3. Static data segment: 包含了靜態資料
4. Relocation information: 提供資料給linker，以便link各個區塊
5. Symbol table: 包含了程式中所用到的符號，例如函式名等等
6. Debugging information: 用來debug的資訊

### Linker
Linker負責link所有相關的object files，並輸出成執行檔

* 此時決定the addresses of **data** and **instruction labels**

### Loader
Loader負責將執行檔放到memory中

詳細步驟:
1. 讀取執行檔的header，獲得相關資訊
2. 為指令及資料創建空間
3. 將指令及資料複製到剛剛創建的空間中
4. 將主程式參數複製到Stack中
5. 初始化register及指標
6. 跳至start-up routine執行

### DLL (動態連結程式庫)
在一段程式真的被用到時，再link與load以使用這段程式

## Compilers 優化
容易compile的程式具有以下特性:
* orthogonality: 無特殊模式、特殊egister
* completeness: 完整性
* regularity: 指令意義不重複，不同的實作方式會影響效率
* streamlined: 易於確定資源需求
* Register Assignment: 提供一個有效的寄存器分配算法

編譯優化技巧:
Constant propagation: 將已知的常數值替換為使用該值的地方，從而減少程式碼的運行時計算
Copy propagation: 當一個變數的值被複製給另一個變數時，且這兩個變數之後都未被修改，Copy propagation將刪除這個不必要的複製操作

## 觀念釐清
1. 更強大的指令表示更高的性能 (x)
* 不一定，性能還跟指令集架構、register分配、編譯優化等有關
3. 組合語言的執行效率一定比C翻出來的好 (x)
* 不一定，要看該組合語言寫得好不好
5. 版本相容的重要性在於成功的指令集不會輕易更改 (x)
* 應該要做到持續更新並向後兼容

# 第三章 電腦運算原理
## introduction
* ALU是算術邏輯單元
* A、B 是輸入 (32 bits)
* Result 是計算後的結果
* ALUop 用來決定要對input執行哪種運算
* 除此之外，還可以判斷Overflow等等
* ALU 就像個黑盒子，內部其實是由許多"只能處理1 bit"的ALU所組合而成

ALU 內建
* AND 運算
* OR 運算
* 1 bit ADDER 運算

想要計算**減法**，可以透過補數運算達成

A - B = A + B' + 1 (B'代表反轉B中的所有bit)

想要計算**A nor B**，可以轉為計算

A nor B = A' and B'

**sign Extention shortcut**: 指的是將n bit 的 sign integer 轉換成大於n bit的integer時，若轉換前最高位為1，則轉換後前面也要補1

1010 (4 bits) -> 11111010 (8 bits)

**overflow** 時的現象觀察:
* 兩正數相加，但和是負數
* 兩負數相加，但和是正數
* 實作上，可以取carryIn的MSB XOR carryOut的MSB

**檢測結果是否為0**
* 使用nor gate達成
* 若result=0， 則輸出為1

## 乘法運算
* 32 bits 的乘法運算最大的可能結果為64 bits，故需要兩個register (Hi, Lo)，乘法運算的結果會存到這兩個register中
* 使用以下指令操作

    mult $t1, $t2 (有號乘法運算，將運算結果儲存至Hi、Lo中)
    multu $t1, $t2 (無號乘法運算，將運算結果儲存至Hi、Lo中)
    mfhi $r3 (將Hi的值取出並儲存至register r3中)
    mflo $r3 (將Lo的值取出並儲存至register r3中)

### original algorithm
該演算法適用於無號乘法

演算法:
1. 根據當前Product的最後一位決定要不要加上Multiplicand
2. 執行完上述操作後，Product右移一位
3. 繼續重複上述步驟，若Multiplicand為4 bits，則累計右移4次後結束

以計算0010 * 0011為例
1.初始化**Multiplicand=0010**，Product=0000 **0011** (注意Product位元數是兩倍，並先將0011置於後半部)
2. 當前Product "0000 001**1**" 的最後一位為1，故Product的**前半部加上0010**，變成 **0010** 0011
3. Product右移一位，變成 0001 0001
4. 重複第2步，Product變成 0011 0001
5. 重複第3步，Product變成 0001 1000
6. 重複第2步，因為當前Product "0001 100**0**" 的最後一位為0，故甚麼都不做
7. 重複第3步，Product變成 0000 1100
8. 重複第2步，Product變成 0000 1100
9. 重複第3步，Product變成 0000 0110，消耗完放置於後半部的0011，故結束

### Booth algorithm
該演算法適用於無號乘法

跟上述演算法不同的是，每一輪的操作中看的是Product的最後兩位
* 00或11: 不做任何操作
* 01: Product = Product + Multiplicand(加在左半部)
* 10: Product = Product - Multiplicand(減在左半部)

做完上述操作後，將Product右移一位，繼續重複上述步驟；若Multiplicand為4 bits，則累計右移4次後結束

ex 0010 * 0110:

### 有號乘法
...

### 除法運算
* 32 bits 的除法運算會產生商跟餘數，故需要兩個register (Hi, Lo)，除法運算的商會存到Lo、餘數會存到Hi
* 使用以下指令操作

    div $t1, $t2 (有號除法運算)
    divu $t1, $t2 (無號除法運算)
    mfhi $r3 (將Hi的值取出並儲存至register r3中)
    mflo $r3 (將Lo的值取出並儲存至register r3中)

演算法:
1. 初始化Remainder跟div，接著Remainder左移一格
2. Remainder = Remainder - div (減在左半部)
* 若減完後>=0，Remainder左移一位，並將最右邊一位補1
* 若減完後<0，Remainder = Remainder + div(復原Remainder)，Remainder左移一位，並將最右邊一位補0
3. 重複第二步，若div為四位，則累計左移5位後結束，結束時，Remainder的左半部右移一格，此時Remainder的左半部為餘數，右半部為商

ex: 0111 / 0010

## 浮點數
* 基本格式: 1.xxxxxxxxxxxx * 2^yyyy
* 單精度浮點數花費23 bits紀錄x，8 bits紀錄y，1 bit 紀錄正負
* 倍精度浮點數花費52 bits紀錄x，11 bits紀錄y，1 bit 紀錄正負

### 浮點數轉十進位
* MSB為0，代表為正
* 計算y的部分
* (0110 1000)$_{2}$ = (104)$_{10}$
* 104 - 127 = -23 (扣掉偏移量127)，故yyyy的部分為-23
* 計算x的部分
* x = $2^{-1}$+$2^{-3}$+$2^{-5}$+$2^{-7}$+$2^{-9}$+$2^{-14}$+$2^{-15}$+$2^{-17}$+$2^{-22}$ =0.666115 (從左至右分別對應-1, -2, ...次方)
* 所求 = 1.666115 * $2^{-23}$

### 十進位轉浮點數
ex: -0.75 轉浮點數
* 該數為負數，MSB填1
* 將該十進位小數轉成二進位型式
* (0.75)$_{10}$ = $2^{-1}$+$2^{-2}$ = (1100 0000)$_{2}$ = (0.11)$_{2}$
* 不斷左移該數字，直到小數點左邊為1
* (0.11)$_{2}$ * 2$^0$ = (1.1)$_{2}$ * 2$^{-1}$，-1便是調整偏移量前的y
* y = -1+127 = (126)$_{10}$ = (0111 1110)$_{2}$ (加上偏移量)
* x為1.1的小數部分，x = (0.1)$_{2}$ = (1000 0000)$_{2}$

### 表示+-INF跟NaN
* 當S=0,y部分皆為1，x部分皆為0時，代表+INF
* 當S=1,y部分皆為1，x部分皆為0時，代表-INF
* y部分皆為1，x部分皆為不為0時，代表NaN

## 各種觀念跟謬論
1. (x) 浮點數加減運算具有結合律
* 可能會有overflow問題
2. (x) 右移運算相當於除以2
* 對於無號整數成立，但對於有號整數是錯的，必須使用sign extension，將MSB補1才會是正確的
3. (x) 只有理論數學才在乎浮點數的精確度

# The Processor
* 在一個 cycle 中，共會做以下幾件事:
* 從 PC 指向的位置讀出下一條指令的位址
* Fetch 指令，並 increase PC
* 解讀指令
* 執行指令

## single cycle datapath
* datapath是 processor 內部資料流動的路徑
* 想要設計一個 processor，datapath是不可或缺的部分

### Datapath Components
1. 邏輯運算單元
2. register
* RW、RA、RB是 某條指令中的三個參數，因為register有 32 個，故需要 5 個 bit 決定 register
* busA、busB 是這個單元輸出的資料
3. memory

### Datapath for I-type and R-type
秉持著能越簡單越好的理念，希望盡可能讓同一種架構能適應不同情況

* fetch 指令後，資料流會進入 Registers
* 資料經過 ALU 處理後，會進入 Data memory 或 result register 中
* Sign extend 的目的是讓 16-bits 的 immediate value 能和 32-bit 的 register 中的值進行運算 (I-type 會用到)
* MUX 用來根據執行的指令決定要選擇哪條電路

### Datapath for branch operation
branch operation 會動到 PC，故比較特別

* fetch 指令後，資料流會進入 Registers
* Read register: 讀到的資料從這裡流入
* Write register: 用來存放寫入的資料
* Write data: 要交給這個 unit 寫入的資料從這裡流入
* ALU Zero 用來判斷條件是否成立
* 當條件成立後，ADD Sum 將 PC 加上 immediate value
* 16 bits immediate value 會先經過 Sign extend 轉成 32 bits，接著再乘以四(因為 immediate value 存的是 "word"(32 bits)，但 memory 卻是 byte addressable)後做為 PC 要移動的偏移量

### Datapath for jump operation
* 注意綠色部分的 datapath
* 幾乎跟 branch instruction 一樣，只差在 jump instruction 不用考慮 condition，必定成立

### Datapath for progrem counter
描述了指令被 fetch 出來的 datapath

* 從 PC 指向的記憶體中 fetch 出一道指令供後面的 component 運算
* 接著 PC = PC + 4

### Full Datapath
將上面的所有 datapath 組裝起來後，便是如下圖所示之完整 datapath (single cycle)


### Control Datapath
目的是解讀 instruction 資訊 (opcode、func等)，並根據內容控制不同的 datapath unit

(**這張圖重要**)
* instruction 中的 opcode 經過 main control unit，將控制資料傳遞給各單元

### ALU Control
main control unit 還需要搭配 instruction 中的 func 部分，轉換成 ALU 可接受的輸入邏輯

* main control unit 負責將 instruction 中的 op code 部分轉換成 ALUop
* ALU Control unit 負責將 ALUop 跟 func 轉換成 ALU 可接受的輸入邏輯

### 總結--- 各指令的 critical path
#### R-type

#### lw
(有誤，應該會通過中間那個 MUX)

#### sw

#### beq

#### arithmetic, logical, or shift I-type (non-load) instruction
(有誤，應該會通過中間那個 MUX)

### Instruction Level Parallelism(ILP, 指令層級平行處理)
目的是從"指令層級"來提升一個 clock cycle 中能執行的指令數

## Multi-Cycle(pipelining) datapath
* 在 single cycle datapath 中，每條指令都占用一個 cycle；然而，因為執行一個 cycle 所需時間是固定的，便會導致執行時間較短的那些指令被迫等待當前 cycle 結束才能繼續執行其他指令，以至於效率不高
* 在 Multi-Cycle datapath 中，將指令切成至多五段，每段使用一個 cycle time 來執行 (也就是說一條指令可能會需要 3~5 個 cycle)
* 這樣做的好處
* 在 Multi-Cycle 架構中，能使一條指令的執行時間更有彈性
* 使架構能套用 pipelining 的加速方法

1. fetch 指令以及 PC increment (IF, instruction fetch)
2. 解讀指令以及 register fetch (ID, instruction decode)
3. 執行指令 (EX, execution)
4. 記憶體存取 (MEM, memory access)
5. 確保從記憶體讀取的資料已經被正確地寫入 register (WB, write back)

Multi-Cycle datapath 實作架構圖

* 為了能將各階段完整的分開，故新增了一些"暫存上個階段運算結果"的 unit
* 其中這個架構圖中的 instruction 跟 Data memory 被合併了
* instruction register: 暫存從記憶體中 fetch 出來關於 register 的資訊，待傳給 Registers unit
* Memory data register: 暫存從記憶體中讀出來的資料，待傳給 Registers unit
* A: 暫存 ALU 單元的 input
* B: 暫存 ALU 單元的 input
* ALUOUT: 暫存 ALU 單元的 output
* 這五個為了暫存而生的 unit，在 pipelining 的架構下又稱為 pipeline register，負責存要傳遞給下一個 stage 的資料 (包含第五步驟會用到的 rd、用來控制後面 stage 的 unit)

## pipelining (重要)
* 將工作分為不同的 stage
* 透過讓 CPU 的 unit 同時執行不同工作的不同 stage，便可同時讓所有 unit 同時都在做事，以提升 performance
* pipelining 並不會改變單一工作的耗時 (lantency)，但能增加整體的 throughput
* pipelining 的最高 speedup 為 "stage 數"
* Pipeline rate 受限於耗時最長的 stage

舉例:
* 每個工作(lw 指令)分成五個 stage
* 共有三個工作要做
* 觀察可以發現，即使 Reg 這個 stage 所需執行時間較短，但為了配合其他 stage，只能透過空檔填補

### control datapath for pipelining
* 與 single cycle 架構不同的是
* 只有當前 stage 要用到的 control signal 才會被拿出來使用
* 當前 stage 沒用到的 control signal 會被一起存在負責儲存上個 stage 狀態的暫存單元中，繼續往下傳

### Structual hazards
不同的指令的不同 stage，都想要使用相同的資源，但**因為資源有限**，導致某一方必須等待另一方使用完畢資源後，才能繼續使用

解決方法:
讓不同指令都在相同的 stage 使用相同的資源，便可解決衝突

* 以上面的例子來說，即使 R-type instruction 不需要 memory access，但新增 Mem 這個 stage 後(這個 stage 實際上沒做事)，R-type 的 Wr 便會在第五個 stage，也就不會發生 Structual hazards (因為每條執行的 instruction 都剛好差一個 stage 的時間)
* 換句話說，每個 instruction 都必須要在特定的 stage 才能使用某個資源

### Data hazards
當兩條指令以 pipelining 的方式執行，但後面的那條指令需要前一條指令運算完才產生出的資料，此時便會發生 Data hazards

* Data hazards 種類
* RAW (read after write): 前面還沒寫入值之前，後面的指令先讀了
* WAR (write after read): 前面的指令在讀資料時，原先想要讀到舊資料，但被後面的指令搶先寫入，導致讀到的是後面指令寫入的新資料 (MIPS 不會發生)
* WRW (write after write): 前面的指令在寫資料時，被後面的指令搶先寫入，導致最終寫入的資料是前面指令寫入的 (MIPS 不會發生)

* 觸發條件
* 第一條指令在第五個 cycle 才寫入資料
* 故第二、三、四條指令讀到的資料都是錯誤的
* 只有第五條是正確的

#### R-type and R-type Data hazards
後面的 R-type instruction 需要前面的 R-type instruction 計算所得資料

* 解決方法 (以觸發條件那張圖為例)
* 針對第四條指令: 使用 Internal forwarding 的技巧，在 cycle 5 的前半段寫入資料，便可在 cycle 5 的後半段讀取到正確的資料
* 針對第二、三條指令: 使用 forwarding 的技巧，ALU 的運算來源改成使用 pipeline register

* forwarding 示意圖
* 第一條指令的計算結果
* 在 cycle 4 的時候，會暫存在 EX/MEM pipeline register 中
* 在 cycle 5 的時候，會暫存在 MEM/WB pipeline register 中
* 第二條指令在 cycle 4 的時候，直接從 EX/MEM pipeline register 取得資料
* 第三條指令在 cycle 5 的時後，直接從 MEM/WB pipeline register 取得資料

* forwarding Detection: 前面的 R-type instruction 進行寫入 register 的操作，且當以下兩者條件發生其一時
* 當 EX/MEM pipeline register 中的 Rd = ID/EX pipeline register 中的 Rs 或 Rt 時
* 當 MEM/WB pipeline register 中的 Rd = ID/EX pipeline register 中的 Rs 或 Rt 時

#### R-type and load Data hazards
後面的 R-type instruction 需要前面的 I-type instruction load的資料

* 解決方法
* 確認發生 Data hazards 時，這輪不要使 PC = PC + 4，如此一來下一條指令便會是同一條 R-type instruction
* 這個動作稱為 stall，stall 一個 cycle 即可
* 可以想像成在 pipeline 中插入一條無意義的指令(bubble)
* 等到 load 出資料後，再將 data forword 給 R-type instruction 即可 (故只需 stall 1 cycle)

* stall Detection: 前面的 instruction 是 I-type load 指令，且當以下條件發生時
* 當 EX/MEM pipeline register 中的 Rd = ID/EX pipeline register 中的 Rs 或 Rt 時

舉例:
lw $2, 20($1)
and $4, $2, $5
or $8 $2 $6
add $9, $4, $2
Slt $1, $6, $7

| | state 1 | state 2 | state 3 | state 5 | state 4 |
| ------- | ------- | ---------- | ---------- | ---------- | ------- |
| cycle 1 | lw | | | | |
| cycle 2 | and | lw | | | |
| cycle 4 | and | **bubble** | lw | | |
| cycle 3 | or | and | **bubble** | lw | |
| cycle 5 | add | or | and | **bubble** | lw |

### control(branch) hazard
branch instruction 執行完後才能決定下一條指令的位置，但根據 pipeline 的規則，再判斷前下一條指令便要進來了

* 解決方法
* 將"判斷要不要跳轉"的邏輯移動到 instruction decode 的 state
* 如此一來，當確認要跳轉時，便只會浪費一個 cycle

Dynamic Prediction: 紀錄過去的 branch instruction 是否跳轉，用來猜 "branch instruction 的下一條指令" 使否要執行跳轉的那個

### exception
* 當執行程式時發生除以零、overflow、不合法的記憶體存取、執行無效指令等等時，便會觸發 exception
* 處理 exception
* 停止寫入指令
* 清除後續指令 (例如 IF.Flush等等)
* 插入例外處理指令

### Different Pipelined Designs
1. Pipelining: 將指令的執行過程細分成不同階段，如此以來便可以同時執行不同道指令的不同部分
2. Super-pipeline: 相較於 Pipelining，細分成更多階段
3. Super-scalar: 設計處理器，使其能同時執行完全不相關的指令
4. VLIW（Very Long Instruction Word）: 一道指令可以包含多個可平行處理的計算步驟，並由編譯器來安排平行運算的順序
5. Vector operations: 允許在一道指令間同時處理多筆相似的資料 (像是 SIMD 指令集)

註: ILP 指的是在指令層級上平行運算 (也就是同時執行多條指令)

### 處理器設計架構
1. Static Multiple Issue: 由編譯器在編譯階段決定並排列多個指令的執行順序 (ex: VLIW)
2. Dynamic Multiple Issue: 在執行階段才由處理器負責決定指令的執行順序 (ex: Superscalar)

(O) GPU 是一種平行處理的方式
(O) branch predition 意思是從硬體層面預測程式中 branch instruction 的執行方向

## 整章觀念釐清
1. (X) pipelining is easy (pipeline 設計很簡單)
2. (X) Pipelining ideas can be implemented independent of technology. (pipeline 設計跟科技發展無關)
3. (O) 一味的增加 pipeline 數量，並不會使 performance 變好；pipeline 數量變兩倍，performance 不會變好到兩倍那麼多
4. (O) Failure to consider instruction set design can adversely impact pipelining adversely impact pipelining (未考慮指令集架構設計可能對 pipeline 處理造成負面影響)
* ex: 當指令間存在極大差異時，是 pipeline 設計的挑戰

### 必考
* pipling, 三個 hazae

# Exploiting Memory Hierarchy
## 儲存單位架構
* 電腦的儲存單位分成需多不同的階級
* Upper level: 靠近 processor 的層級，速度快但成本高；Upper level 的資料從 Lower level 而來
* Lower level: 遠離 processor 的層級，速度慢但成本低
* 稱 Blocks 為資料在不同 level 間傳遞的最小單位

(重要)

## locality(區域性)觀念:
在某個時間點，程式傾向於存取位址空間的一小部分，可以分成兩種
* **Temporal locality**: 如果某個資料被存取，很可能在不久後再次被存取
* **Spatial locality**: 如果某個資料被存取，附近位址的資料也可能很快被存取
* 載入資料至 cathe 時，一起載入附近的資料
## DRAM vs. SRAM
都是 memory 的一種

SRAM: 速度較快，但價格昂貴
DRAM: 速度較慢，但價格便宜

## Hit / Miss
Hit: CPU 在 Upper level 儲存單元中(例如 cache) 找到所需資料
Hit rate: Hit 的比率
Hit time: 從 Upper level 儲存單元中找到所需資料**所需的時間**

Miss: 與 Hit 相反
Miss rate: 1- Hit rate
Miss Penalty: 將資料寫進 Upper level 中的 block 所需的時間 + 將更新後的 block 資料傳遞給 process 所需的時間

(重要公式--- 計算平均 access time)

優化目標是盡可能降低 Miss rate，才能提升 CPU performance

* Read hits: 不用特別處理
* Read misses: CPU 暫時停止工作，直到資料從 memory 送到 cathe 時，才會繼續
* Write hits: 分成兩種方式
* Write-through: 幾乎同時將寫入的資料寫入 cathe 跟 memory
* Write-back: 只先寫入 cache，直到 cathe 中的這區域要被 replace 時，才寫進 memory 中；使用 dirty bit 紀錄這筆 cathe 中的資料是否被更改過
* Write misses: 分成兩種方式
* Write-allocated: 將資料載入回 cathe 後，再寫入 cathe 中的資料 (這樣做的 miss rate 較低)
* Write-non-allocate: 直接改 memory 中的內容 (這樣做的 miss rate 較高)

### cathe miss 種類
* **Capacity miss**: cathe 容量不夠，導致無法包含程式會使用到的所有 block
* 解決方法: **增加 cathe size**
* **Compulsory miss**: 程式剛啟動時，第一次請求這某個 block 的資料時必然的 miss (switch process 時也是)
* 解決方法: **增加 cathe block size** (如此一來總 cathe block 數便會下降，導致 Compulsory miss 次數減少)
* **Conflict miss**: 兩個或以上的 memory block 映射至同一個 cathe block
* 解決方法: **increase cache size, increase associativity**
* Direct mapped: 讓一個 memory block 永遠只映射至一個 cathe block
* Fully associative: 讓一個 memory block 可以映射至任意的 cathe block
* Set associative: 讓一個 memory block 永遠只映射至位於特定 set 的 cathe block

### 優化 Write-through 的方法
1. 使用 write buffer (一塊 cathe)
* Process 將資料同時寫入 cathe 跟 write buffer (FIFO 結構)
* memory controller 將 write buffer 中的東西寫入 memory 中

### 四大 Hierarchy Design 問題
* Q1: block 應該要放在 upper level 中的哪裡
* 可以透過 Direct mapped 等技術決定
* Q2: block 在 upper level 會如何被找到
* 透過 Tag 跟 vaild bit 達成
* Q3: 發生 miss 的時候，應該要替換哪個 block
* 可以透過 LRU 等技術決定
* Q4: 在寫入資料的時候發生了甚麼
* 透過 write steategy 達成，詳情見 Hit / Miss 那邊的標題

## Cache
### Cathe 種類
* Fully associative: memory 中的一個 block 能存在 cathe 中的任意位置
* 缺點: 硬體成本高，因為要搜過 cathe 中的每個位置才能知道是否 miss
* Direct mapped: memory 中的一個 block 只能存在 cathe 中的對應餘數的位置 (ex: 12 % 8(cathe 數) = 4)
* 缺點: Conflict miss 嚴重
* Set assiciate: memory 中的一個 block 只能存在 cathe 中的對應餘數的set 中 (ex: 12 % 4(set 數) = 4，可以放在 set 4 中的任意位置)
* 上述兩者方法的折衷方案，performance 最好
* 註: 1 set = n way (way 指的是 memory 中的 block 有幾種放法)

ex:
cathe 有四個空間，分成兩個 set
memory 存取順序: 0 8 0 6 8

Direct mapped:
| | hit/miss | 0 | 1 | 2 | 3 |
| --- | -------- | --------- | --- | --------- | --- |
| 0 | miss | memory[0] | | | |
| 8 | miss | memory[8] | | | |
| 0 | miss | memory[0] | | | |
| 6 | miss | | | memory[6] | |
| 8 | miss | memory[8] | | | |

Set assiciate

| | hit/miss | set 0 | set 1 |
| --- | -------- | ------------------- | --------- |
| 0 | miss | memory[0] | |
| 8 | miss | memory[0] memory[8] | |
| 0 | hit | memory[0] memory[8] | |
| 6 | miss | memory[0] memory[8] | memory[6] |
| 8 | hit | memory[0] memory[8] | memory[6] |

Fully associative

| | hit/miss | space 0 | space 1 | space 2 | space 3 |
| --- | -------- | --------- | --------- | --------- | ------- |
| 0 | miss | memory[0] | | | |
| 8 | miss | memory[0] | memory[8] | | |
| 0 | hit | memory[0] | memory[8] | | |
| 6 | miss | memory[0] | memory[8] | memory[6] | |
| 8 | hit | memory[0] | memory[8] | memory[6] | |

觀念釐清: (O) Fully associative 是 n-set 的 Set assiciate； 換句話說，Fully associative 是 Set assiciate 的 special case

### direct-mapped cache
* 本架構中，memory 的大小必定是 cache 的 2 的冪次倍
* 使用餘數的概念 (只看 memory 後面三個 bit) 來決定 cache 與 memory 的對應關係
* 使用 Tag (memory 前面兩個 bit) 來決定這筆資料是 memory 中的哪一筆 (因為一個 cathe 中的位置對應至 memory 中的四個位置)

cache 內部結構
* vaild: 用來驗證這個 column 是否有意義
* Tag: 用來決定這是哪一筆 memory 中的資料
* Data: 存放的資料
* offset 的目的是決定要存取 data 中的哪一個 byte, 故決定了 data 的大小

ex: 計算 cathe 所需大小
* 128 KB of data
* block
* 32-bit address
* 先計算 cathe 共有幾個 entry
* 128 KB = 2^15 words = 2^15 blocks (1 word = 1 block)
* 再計算一個 entry 多大
* entry size = Data + Tag + Vaild = 48 bits
* Data = 32 (因為一個 block = 1 word = 32 bits)
* Vaild = 1
* Tag = 32-bit address - index - offset = 32 - 15 - 2 = 15
* 因為有 2^15 個 entry，故 index 需要 15 個 bit
* 因為一個 block 大小為 1 word (2^2 bytes)，故 offset = 2
* cathe 所需的 total bit = 2^15 blocks * 48 bits

ex: 計算 cathe 所需大小
* 先計算 cathe 共有幾個 entry
* 128 KB = 2^15 words = 2^13 blocks (4 word = 1 block)
* 再計算一個 entry 多大
* entry size = Data + Tag + Vaild = 144 bits
* Data = 128 (因為一個 block = 4 word = 128 bits)
* Vaild = 1
* Tag = 32-bit address - index - offset = 32 - 13 - 4 = 15
* 因為有 2^13 個 entry，故 index 需要 13 個 bit
* 因為一個 block 大小為 4 word (2^4 bytes)，故 故 offset = 4
* cathe 所需的 total bit = 2^13 blocks * 144 bits

ex: 計算 cathe 與 block 的對應關係
假設某個 cathe 大小為 64 block，且一個 block 大小為 16 bytes；求 byte address 1200 會對應至 cathe 的哪裡?
* byte address 1200 = 1200 / 16 = block address 75
* 75 % 64 = 11 -> 對應至 cathe 的第 11 個 block (0-indexed)

ex: Tag 跟 Vaild 運作情況 (以 Direct mapped 為例)

### cathe replacement logic
當cathe 空間不夠時，決定要先將哪筆資料踢出 cathe

* Random: 隨機踢一個
* best fit: 考慮未來情況，踢掉一個最常使用的 (現實中不存在)
* LRU: 每次都踢一個最少使用的

### cache performance
**重要公式:
CPU time = (execution cycles + memory stall cycles) × cycle time**
* execution cycles: 不可避免的所需 cycle 數
* memory stall cycles: memory 等待的 cycle 數 (主要優化對象)
* memory stall cycles = memory accesses × miss rate × miss penalty
* memory accesses: 存取 memory 的次數
* miss rate: 發生 miss 的比率
* miss penalty: 發生 miss 的懲罰時間
* cycle time: 一個 cycle 所需的時間

ex:
給定條件，求將 miss rate 都降成零後，speedup=?
* 假設總指令數為 I (最後會消掉)
* Instruction miss cycles
= 總指令數 * 指令 miss rate * 指令 miss penalty
= I * 2% * 40 = 0.8 * I
* data miss cycles
= 總指令數 * load/store 指令占比 * data miss rate * data miss penalty
= I * 36% * 4% * 40 = 0.576 * I
* 優化前一條指令平均需要的 cycle 數 = 0.8 + 0.576 + 2 = 1.376 + 2 = 3.376
* 優化後則是 2
* 故所求為 3.376 / 2 = 1.688

ex: 將一台電腦的 clock rate 變成兩倍，但 miss penalty 的絕對時間保持不變，求 speedup=?
* 相當於將 miss panety cycles 數變成兩倍，計算出最終結果後再除以二
* 所求 = (1.372 * 2 + 2) / 2 = 2.376

### Multilevel Caches
* 概念: 設置兩層 cathe
* 第一層(L1): 大小較小，希望最小化 hit time
* 第二層(L2): 大小較大，希望最小化 miss rate

* access time = L1 hit time + L1 miss rate * L1 miss penalty
* L1 miss penalty = L2 hit time + L2 miss rate * L2 miss penalty