# 計算機組織 - 劉一宇

> Key word: CPU time, Amdahl's Law, R/I/J Format, Design Principle, Booth's Algorithm

## Basic Inforamtion

- 期末 Project - RISC-V 相關

## Intro

### Computer Architecture

Software 層用來定義高抽象等級的問題並實踐 solution
Hardware 層用來實踐主要的計算功能

- Software Layer
- Application
- Operating System
- Compiler
- Assembler
- Hardware Layer
- Processor / Memory / I/O System
- Datapath & Control
- Digital Design
- Cicuit Design
- Transistors

Software 和 Hardware 之間的溝通使用特定的 Instruction Set Architecture, 例如 x86 / MIPS / ARM

### High Level to Low Level Transofrmation

High Level Language 透過 Compiler 轉換成 Assembly Language, 再透過 Assembler 轉換成 Machine Language

- High Level Language

tmp = v[0];
v[0] = v[1];
v[1] = temp;

- Assembly (by Compiler)

lw $15, 0($2)
lw $16, 4($2)
sw $16, 0($2)
sw $15, 4($2)

- Machine Language (by Assembler)

1000 1100 0100 1111...

### MIPS R3000 ISA (Instruction Set Architecture)

- Instruction 功能
- Load / Store
- Computational
- Jump and Branch
- Floating Point
- coprocessor
- Memory Management
- Special
- Registers
- R0 ~ R31
- PC
- HI
- LO
- Instruction Formats
- OP | rs | rt | rd | sa | funct
- OP | rs | rt | immediate
- OP | jump target

### ISA Examples

從 32 bit 擴展到 32/64 bit

- HP PA-RISC (1986-96)
- Digital Alpha (1992-97)
- Oracle Sparc (1987~2019)
- IBM Power (1990-2020)
- Intel x86 (1978-2019 - 現役)
- CISC - Complex Instruction Set Computer
- MIPS (1985-2014 - 快死了)
- ARM (1985-2024 - 現役)
- RISC-V (2010-2021)

## Chapter 1 - Computer Abstractions and Technology

### Computer

電腦是一種 Programmable 的電子裝置, 用來對資料進行複雜處理

- 第一台電腦 - ENIAC (1943)
- 1947 年電晶體被發明
- UNIVAC (1951) / IBM 701 (1952) 等電腦被發明
- 第一台使用電晶體的電腦 - IBM 1401 (1959)
- 1958 年德州儀器開發了 IC
- 第一個 CPU - Intel 4004 (1971)
- Apple II (1977) / Intel 8088 (1981) 等使用 CPU 的電腦被發明
- 第一個圖形化介面 - Alto (1973)
- 第一個 Application - VisiCalc for Appie II (1979)
- 1980 年 IC 的集成進入 VLSI

### Instruction Count and CPI

- Clock Cycles = Instruction Count (IC) $\times$ Cycles per Instruction
- CPU Time
- Instruction Count (IC) $\times$ CPI $\times$ Clock Cycle Time
- $\frac{Instruction \space Count (IC) \times CPI}{Clock \space Rate}$ (Freq)

- 第 i 個 IC 意思是第 i 個類型的 IC

#### CPI Example


### Amdahl's Law

先區分出可以加速和不能加速的部分
將可以加速的部分加速完成加上不能加速的部分就是進行系統優化

Speedup (加速)
- $\frac{Execution Time w/o E}{Execution Time w/E} = \frac{Performance w/E}{Performance w/o E}$
- $Execution \space Time(w/E) = ((1-F)+\frac{F}{S}) \times Execution \space Time(w/oE)$
- $Speedup(w/E) = \frac{1}{(1-F)+\frac{F}{S}}$

## Chapter 2 - Instruction Set Architecture

### Memory Operation-

在 MIPS 中最高可計算的範圍是 $2^{32}$ (32-bit), 這代表了支援 RAM 容量的最高值，若超過的話則無法進行定址

- 記憶體單位

### MIPS Architecture

* MIPS 架構中用的是 10 進制
* MIPS 架構用的是 Big-Endian

- `{opcode} {unit 1} {unit 2}`
- `$s0` = Base Register
- `$t0` = Temp Register

* 如果 opcode 後面帶一個 i 代表指令中含有常數

- `lw` - Load Word to Register
- `lw $t1, 12($s0)` = `mov eax, [ebx+12]`
- `sw` - Store Word to Location
- `sw $t0, 12($s0)` = `mov [ebx+12], eax`
- `add` - Add Values
- `add $s1, $s2, $t0` = Add `$s2` and `$t0` to `$s1`

## 指令大補帖

### **系統呼叫（syscall）基本指令碼**

| 系統呼叫碼 | 功能 | 輸入暫存器/操作 | 範例程式碼片段 |
| ---------- | --------------------- | ---------------------- | --------------------------------------------------- |
| 1 | 輸出整數 (print int) | 將要輸出的整數存入 $a0 | ```assembly<br>li $v0, 1<br>move $a0, VALUE<br>syscall<br>``` |
| 4 | 輸出字串 (print string) | 將字串位址存入 $a0 | ```assembly<br>li $v0, 4<br>la $a0, string_label<br>syscall<br>``` |
| 5 | 輸入整數 (read int) | 結果會存入 **$v0** | ```assembly<br>li $v0, 5<br>syscall<br># 輸入整數結果在 $v0<br>``` |
| 8 | 輸入字串 (read string) | $a0: 儲存字串的緩衝區位址<br>$a1: 緩衝區大小 | ```assembly<br>li $v0, 8<br>la $a0, buffer<br>li $a1, size<br>syscall<br>``` |
| 10 | 程式結束 (exit) | - | ```assembly<br>li $v0, 10<br>syscall<br>``` |

### Register


$v0,$v1 -> 回傳參數
$a0~$a4 -> 傳入參數
$t0~$t7 -> temporary 暫時參數 無須保存
$s0~$s7 -> save 必須在函式內保存與還原
$sp -> stack pointer 堆疊參數
$ra -> 返回位址 (jump)

### Jump

j: jump -> 跳過去就再也不會回來了
jal: jump and link -> 會存 $ra，可以瞬移回來
jr: jump register -> jr $ra, 跳到 $ra 位置

### Branch

- **beq**
**英文名稱：** *Branch if Equal*
**說明：** 若兩個暫存器相等則跳轉。
**記憶簡稱：** BEQ → "Equal"

- **bne**
**英文名稱：** *Branch if Not Equal*
**說明：** 若兩個暫存器不相等則跳轉。
**記憶簡稱：** BNE → "Not Equal"

---

### **Zero-Comparison Branch Instructions**

- **blez**
**英文名稱：** *Branch if Less than or Equal to Zero*
**說明：** 若暫存器值 ≤ 0 則跳轉。

- **bgtz**
**英文名稱：** *Branch if Greater Than Zero*
**說明：** 若暫存器值 > 0 則跳轉。

- **bltz**
**英文名稱：** *Branch if Less Than Zero*
**說明：** 若暫存器值 < 0 則跳轉。

- **bgez**
**英文名稱：** *Branch if Greater than or Equal to Zero*
**說明：** 若暫存器值 ≥ 0 則跳轉。

---

### **Pseudo Branch Instructions (Pseudoinstructions)**

- **blt**
**英文名稱：** *Branch if Less Than*
**說明：** 若第一個暫存器小於第二個則跳轉。

- **bgt**
**英文名稱：** *Branch if Greater Than*
**說明：** 若第一個暫存器大於第二個則跳轉。

- **ble**
**英文名稱：** *Branch if Less Than or Equal*
**說明：** 若第一個暫存器 ≤ 第二個則跳轉。

- **bge**
**英文名稱：** *Branch if Greater Than or Equal*
**說明：** 若第一個暫存器 ≥ 第二個則跳轉。

## R-format


> shift instruction 是 R-Format

## I-format


> Branch 是 I-Format

## J-format


## Branch Addressing

#### **Branch Immediate 指定字位址 (Word Address)**

1. **指令對齊 (Word Aligned):**
- MIPS 指令的位址是**字對齊 (word aligned)**，也就是說，**每條指令的位址都是 4 的倍數**。
- 位址在二進位表示上，會以 **00** 作為結尾（因為 4 在二進位是 `100`）。

2. **位址加法的特性：**
- 因為指令位址總是 4 的倍數，當分支指令要計算跳轉位址時，會使用**字單位 (word)** 來指定。
- **立即值 (immediate)** 是用**字數 (words)** 來表示，而非**位元組數 (bytes)**。

3. **最大分支範圍：**
- MIPS 分支指令可以往**正負 $2^{15}$ 個字 (words)** 跳轉。
- 換算為位元組數：
$$
\pm 2^{15} \times 4 = \pm 2^{17} \text{ bytes} (131072 bytes)
$$
- 這意味著，可以處理**4 倍範圍**的迴圈。

---

#### **Immediate 指定下一個 PC (PCbranch + 4)**

1. **分支基址：**
- MIPS 使用**PC + 4** 作為基址（這是因為 MIPS 在執行指令時，PC 已經自動更新至下一條指令）。

2. **跳轉位址計算：**
- **未跳轉：**
$$
PC_{next} = PC_{branch} + 4
$$
- **跳轉成功：**
$$
PC_{next} = (PC_{branch} + 4) + (immediate \times 4)
$$
- **解釋：**
- 若條件成立，PC 跳轉的位址是：**當前 PC + 4 + (立即值 × 4)**。
- **immediate × 4** 的原因是，立即值是**字單位 (word)**，而非位元組單位。

#### **指令範例：**

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

- **beq $9, $0, End**
- 若 `$9 == $0`，則跳至標籤 `End`。
- **opcode：** 4 (beq 指令)
- **rs：** 9 (第一個運算元)
- **rt：** 0 (第二個運算元)
- **immediate：** 3 (**從當前指令的下一條指令開始計算的位移**，因此中間隔了三條指令)
- 當分支條件成立時，PC 會跳轉到**PC + 4 + (immediate × 4)**。
- 由於指令之間是按**字數 (word)** 計算，因此 Immediate 為 3。

> 考古有出

## Design Principle
* Design Principle 1 : Simplicity favors regularity(簡單有易於規則)
* Design Principle 2 : Smaller is faster(小就是快)
* Design Principle 3 : Make the common case fast
* Design Principle 4 : Good design demands good compromises(好的設計需要好的折衷)

## MIPS Addressing Modes

1. Immediate Addressing (立即位址模式)
`op rs rt immediate`
2. Register Addressing (暫存器位址模式)
`op rs rt rd`
3. Base Addressing (基址位址模式)
`op rt offset(rs)` ($reg + address)

4. PC-Relative Addressing (程式計數器相對位址模式)
`op rs rt offset`
ex: `beq $t0, $t1, Label`

5. Pseudo-Direct Addressing (偽直接位址模式)
`op target`
ex: `j label`

## Compile
> 考古


| 名稱 | 中文 | 主要用途 | 運作時間 |
|------|------|----------|----------|
| **Compiler** | 編譯器 | 將高階語言（如 C/C++）轉成低階的中間碼或組合語言（如 Assembly） | 編譯時 |
| **Assembler** | 組譯器 | 將組合語言轉成機器碼（object file） | 編譯時 |
| **Linker** | 連結器 | 將多個 object files 和函式庫合併成一個可執行檔 | 編譯時 |
| **Loader** | 載入器 | 將可執行檔載入記憶體，並準備執行（分配記憶體、初始化等） | 執行時 |

## Instruction count and CPI are not good performance

> 考古

單獨使用，無法全面反映系統的真實效能：
1. 指令集架構或許不同（RISC, CISC）
2. CPI 取決於指令類型

綜合考量（IC, CPI, Clock Rate）：
$$
CPU \space Time = \frac{IC \times CPI}{Clock \space rate}
$$

## Multiplication in MIPS


mul - 用於有符號整數的乘法運算，結果儲存在一般暫存器中。
mult / multu - 有符號和無符號乘法運算，結果儲存在特殊暫存器 HI 和 LO 中。(32 x 32 位元可能會產生 64位元，因此拆成 hi 和 lo 存放結果)

`mflo, mfli: move from lo/hi`

## Booth's Algorithm

Booth 演算法是一種 **有符號二進位乘法演算法**，用來有效計算兩個補數二進位數字的乘積。該演算法主要用來減少乘法操作次數，特別是處理 **連續 1 或 0** 的情況。

- 將 **乘數 (Multiplier)** 中的 **連續 1** 簡化為加法與減法操作，減少操作次數。
- 使用 **補數表示法**，以方便處理正負數乘法。

### 重點：
- 每次觀察 **乘數的最低兩位元 (Q₀ 和 Q₋₁)**：
- **`01`**：加法操作 (加上被乘數)
- **`10`**：減法操作 (減去被乘數)
- **`00` 或 `11`**：不操作 (右移)
- 重複操作，直到完成所有位元的運算。



---

## Division


## **Signed Division Rules（有號除法規則）整理**

1. **記住符號處理：**
- 執行除法時，先將除數與被除數都視為正數進行除法
- 最後再根據原始的符號決定 **商與餘數的符號**
2. **餘數（Remainder）要跟被除數（Dividend）**有相同符號！
3. **商（Quotient）的符號：**
- 如果被除數與除數 **符號相同** → 商為正
- 如果兩者 **符號相反** → 商為負
4. **例子說明：**

    -7 ÷ 2 = -3，餘數 = -1
    -7 ÷ -2 =  3，餘數 = -1

你會發現餘數仍然是 -1，**跟被除數 -7 同號**
5. **結果要滿足這個恆等式：**
$$
\text{Dividend} = (\text{Quotient} × \text{Divisor}) + \text{Remainder}
$$

✔️ 驗證 `-7 ÷ 2`：
$$
-7 = (-3) × 2 + (-1) = -6 -1 = -7
$$

## 單精度浮點數（Single-Precision Floating-Point）

單精度浮點數是 IEEE 754 標準中常見的一種表示實數的方法，**總共使用 32 個位元（bits）**，分為三個部分：

| 符號位元（Sign） | 指數（Exponent） | 尾數 / 有效數字（Mantissa / Fraction） |
|------------------|------------------|----------------------------------------|
| 1 bit | 8 bits | 23 bits |

### 📐 各部分的意義

#### 1. **符號位元（Sign bit, S）**
- 1 bit 表示正負號
- `0`：正數
- `1`：負數

#### 2. **指數（Exponent, E）**
- 8 bits，表示數字的「大小尺度」
- 使用 **偏移碼（bias）**：`127`，實際指數 = `E - 127`
- 例如 `E = 130` → 實際指數 = `130 - 127 = 3`

#### 3. **尾數（Fraction / Mantissa, M）**
- 23 bits，表示有效數字部分（但實際上是 24 位有效位元，因為有隱藏的前導 1）
- 預設第一位為 `1.`（稱為 **hidden bit** 或 **implicit bit**），除非是特殊情況（如非規格化數）

---

### 🧮 表示方式（數學式）

IEEE 754 單精度浮點數的表示公式如下：

$$
\text{Value} = (-1)^S \times 1.F \times 2^{E - 127}
$$

- `S`：符號位元
- `F`：尾數欄的 23 bits（視為小數點後的二進位）
- `E`：偏移後的指數（8 bits）

---

## 雙精度浮點數（Double-Precision Floating-Point）

雙精度浮點數是 IEEE 754 中的另一種表示法，用 **64 個位元（bits）** 來儲存一個實數，適用於需要更高準確度的計算。

| 符號位元（Sign） | 指數（Exponent） | 尾數 / 有效數字（Mantissa / Fraction） |
|------------------|------------------|----------------------------------------|
| 1 bit | 11 bits | 52 bits |

---

### 📐 各部分說明

#### 1. **符號位元（Sign bit, S）**
- 1 bit，代表數的正負：
- `0` → 正數
- `1` → 負數

#### 2. **指數（Exponent, E）**
- 11 bits，使用偏移表示法（**bias = 1023**）
- 實際指數 = `E - 1023`

#### 3. **尾數（Mantissa / Fraction, F）**
- 52 bits，代表小數點後的有效數字
- 預設有一個隱含的 `1.` 作為開頭（除非是特殊數）

---

### 🧮 數值表示公式

$$
\text{Value} = (-1)^S \times 1.F \times 2^{E - 1023}
$$

## IEEE 754 Standard

### 1. **單精度（Single Precision, 32-bit）**

| 部分 | 位元數 | 偏移值 |
|----------|--------|--------|
| 符號 Sign | 1 bit | 無 |
| 指數 Exponent | 8 bits | Bias = 127 |
| 尾數 Mantissa | 23 bits | 有隱含 1 |

$$
\text{Value} = (-1)^S \times 1.F \times 2^{E - 127}
$$

---

### 2. **雙精度（Double Precision, 64-bit）**

| 部分 | 位元數 | 偏移值 |
|----------|--------|--------|
| 符號 Sign | 1 bit | 無 |
| 指數 Exponent | 11 bits | Bias = 1023 |
| 尾數 Mantissa | 52 bits | 有隱含 1 |

$$
\text{Value} = (-1)^S \times 1.F \times 2^{E - 1023}
$$

---

### 目標：用 IEEE 754 單精度格式表示 $\frac{1}{7}$

#### ✅ 步驟一：取得 $\frac{1}{7}$ 的二進位小數

$$
\frac{1}{7} ≈ 0.142857142857...₂（重複循環）
$$

#### ✅ 步驟二：正規化（Normalized Form）

我們要寫成：

$$
1.xxxxx × 2^e
$$

把 \( 0.001001... \) 左移 3 位可得：

$$
\frac{1}{7} = 1.001001001... × 2^{-3}
$$

#### ✅ 步驟三：計算 Exponent 欄位

實際 exponent = -3
IEEE 754 使用 **bias = 127**

$$
\text{encoded exponent} = -3 + 127 = 124 \Rightarrow 01111100₂
$$

#### ✅ 步驟四：填入 Fraction（取 23 位）

從 `1.001001001...` 中取小數部分：

00100100100100100100100

這是 **循環的 001**

#### ✅ 步驟五：組成 IEEE 754 Binary 格式

- Sign = 0（因為 $\frac{1}{7}$ 是正數）
- Exponent = `01111100`
- Fraction = `00100100100100100100100`

完整 32-bit Binary：

0 01111100 00100100100100100100100

#### ✅ 最終表示：

### 🔢 Binary：

00111110000100100100100100100100

#### 🔡 Hex：
- 分成 4 位元一組轉換：

0011 1110 0001 0010 0100 1001 0010 0100
   → 3    E    1    2    4    9    2    4

✅ **Hex 表示：`0x3E124924`**

#### 📌 驗算公式：

IEEE 754 應滿足：

$$
\frac{1}{7} ≈ (1 + \text{fraction}) × 2^{-3} ≈ 1.142857 × 2^{-3} ≈ 0.142857
$$


## --- 期末考分界線 ---

## Floating Point Addition

### 步驟

#### 1. **比較階數（exponent）**

* 若 A 和 B 的 exponent 不同，需**將小的對齊到大的**。
* 對齊方式是將尾數右移，並調整 exponent。

#### 2. **加法運算**

* 將對齊後的尾數（mantissa）相加（注意符號）
* 若符號不同，就變成減法

#### 3. **規範化（Normalization）**

* 加完可能導致進位或尾數太小
* 將結果左移或右移，使尾數的最高位為 1，並調整 exponent

#### 4. **四捨五入**

* 根據 IEEE 的捨入模式（例如 round to nearest even）進行尾數的截斷

#### 5. **處理特殊情況**

* 包括 overflow、underflow、NaN、無限大（Infinity）等

---

### 📘 範例

A = 1.5 = 0 01111111 10000000000000000000000
B = 2.25 = 0 10000000 00100000000000000000000

* A exponent = 127, B exponent = 128
* 將 A 的尾數右移 1 位對齊 B：變成 0.75（尾數變 010000…）
* 相加尾數：0.75 + 1.125 = 1.875
* 規範化：1.875 = 1.111… → exponent = 128
* 最終結果為 3.75（確認：1.5 + 2.25 = 3.75）


### Associativity

浮點數加減法不具備結合律（位數太小了）


## Datapath








## 一、**整體流程記憶：像水流一樣從左到右流動**

1. **從 PC 開始** ➜ Instruction Memory（抓指令）
2. **Instruction Decode** ➜ 根據指令的不同欄位送到 Registers、控制單元、立即數擴展（Sign Extend）
3. **ALU 計算** ➜ 用來運算位址、計算資料結果
4. **Data Memory 存取** ➜ load/store 指令會用到
5. **寫回 Register（Write Back）**

可用口訣：
👉 **PC ➜ 指令 ➜ 解碼 ➜ ALU ➜ 記憶體 ➜ 寫回**

---

## 二、區塊化記憶（可拆成 5 個模組）

| 區塊名稱 | 功能 | 關鍵元件 |
| -------------------- | ----------- | ------------------------------- |
| PC 與 Instruction | 取指（fetch） | PC, Instruction Memory |
| 解碼（Decode） | 解讀指令與寄存器資料 | Registers, Control, Sign Extend |
| ALU 計算 | 位址運算 / 數值運算 | ALU, ALU control, MUX |
| 存取記憶體 | 記憶體讀取或寫入 | Data Memory, MemRead, MemWrite |
| 寫回（Write Back） | 把結果存回暫存器 | MUX, RegWrite |

---

## 一、主要控制點（Mux Control Points）

1. **寫入暫存器選擇（RegDst）**

* **功能**：決定要寫回的暫存器是 `rt`（I-type）還是 `rd`（R-type）。
* **Mux 位置**：選擇 `Instruction[20–16]`（rt）或 `Instruction[15–11]`（rd）作為 `Write Register` 。

2. **ALU 第二輸入選擇（ALUSrc）**

* **功能**：決定 ALU 第二個操作數是暫存器 `R[rt]`（RegB）還是延伸後的立即數（Imm）。
* **Mux 位置**：在 ALU 輸入 B 與 Immediate 之間切換 。

3. **寫回資料來源選擇（MemtoReg）**

* **功能**：決定寫入暫存器的資料來源是 ALU 運算結果還是 Data Memory 讀出值。
* **Mux 位置**：在 ALUout 與 Memory Data 之間切換 。

4. **下一個 PC 選擇（PCSrc / Branch / Jump）**

* **功能**：

* `PC+4`（順序執行）
* `PC + 4 + (sign_ext(Imm16)≪2)`（分支成功）
* `{PC[31:28], Imm26≪2}`（Jump）
* **Mux 位置**：Branch Mux（判斷是否分支）與 Jump Mux（分支結果 vs. Jump）。

---

## 二、主要控制訊號（Control Signals）

| 訊號名稱 | 說明 | 作用元件 |
| --------------- | ------------------------------------------------------------------ | --------------------------- |
| **RegDst** | 0 = 寫入 `rt`；1 = 寫入 `rd` | RegDst Mux |
| **ALUSrc** | 0 = ALU B 輸入取自 R\[rt]；1 = 取 Immediate | ALUSrc Mux |
| **MemtoReg** | 0 = 寫回 ALU 結果；1 = 寫回 Memory 讀出值 | MemtoReg Mux |
| **RegWrite** | 1 = 啟用暫存器寫入；0 = 禁用 | Register File write-enable |
| **MemRead** | 1 = 啟用記憶體讀取（`lw`）；0 = 禁用 | Data Memory read-enable |
| **MemWrite** | 1 = 啟用記憶體寫入（`sw`）；0 = 禁用 | Data Memory write-enable |
| **Branch** | 1 = 如果 Zero=1 則分支；0 = 不分支 | Branch 比較邏輯 & PCSrc Mux |
| **Jump** | 1 = 跳至 Jump 目標位址；0 = 走分支/順序路徑 | Jump Mux |
| **ALUOp\[1:0]** | 00 = 加法（`lw`/`sw`）<br>01 = 減法（`beq`）<br>10 = R-type（由 `funct` 再解碼） | ALU Control 解碼器 |

---

## 三、控制訊號的產生：主控制器 & ALU 控制器

1. **主控制器（Main Control）**

* 根據指令的 Opcode（`Instruction[31:26]`）產生上述所有主控制訊號（除了 ALU Control），通常用一張真值表或小 PLA 實現 。
2. **ALU 控制器（ALU Control）**

* 接收 `ALUOp[1:0]` 及 R-type 指令的 `funct[5:0]` 欄位，產生 4-bit 的 ALU 操作碼（AND, OR, ADD, SUB, SLT…） 。

---

### 1. R-type: `add $t0, $t1, $t2`

* RegDst = 1（寫入 rd）
* ALUSrc = 0（用暫存器）
* MemtoReg = 0（用 ALU 結果）
* RegWrite = 1
* MemRead = 0, MemWrite = 0, PCSrc = 0

### 2. I-type Load: `lw $t0, 4($t1)`

* RegDst = 0（寫入 rt）
* ALUSrc = 1（立即數）
* MemtoReg = 1（來自記憶體）
* RegWrite = 1
* MemRead = 1, MemWrite = 0, PCSrc = 0

### 3. I-type Store: `sw $t0, 4($t1)`

* RegWrite = 0
* ALUSrc = 1
* MemWrite = 1
* MemRead = 0, PCSrc = 0

| ALUOp | funct | 操作 | ALUctr (二進制) | 說明 |
| :---: | :----: | :--------------: | :----------: | :----------------- |
| 00 | — | add | 0010 | 用於 `lw`/`sw` 的位址計算 |
| 01 | — | sub | 0110 | 用於 `beq` 的相減比較 |
| 10 | 100000 | add | 0010 | `add` |
| 10 | 100010 | sub | 0110 | `sub` |
| 10 | 100100 | AND | 0000 | `and` |
| 10 | 100101 | OR | 0001 | `or` |
| 10 | 101010 | set-on-less-than | 0111 | `slt` |

## ALUctr

ALUctr<3> = 0  

* ALUctr<3> 在所有操作中皆為 0 。

ALUctr<2> = ALUop0 
          + ALUop1 · ¬func2 · func1 · ¬func0  

* 當 ALUOp=01（beq）或 ALUOp=00（lw/sw）時，ALUctr<2>=1；對於 R-type 時，僅在 funct={100100 (AND),100101 (OR),100000 (ADD),100010 (SUB),101010 (SLT)} 中對應子集使能。

ALUctr<1> = ¬ALUop1  
          + ALUop1 · ¬func2 · ¬func0  

* ALUOp=00 (lw/sw) 時，¬ALUop1=1，故 ALUctr<1>=1；對於 R-type，僅在 funct=100000 (ADD) 或 100010 (SUB) 時使能。

ALUctr<0> = ALUop1·¬func3·func2·¬func1·func0  
          + ALUop1· func3·¬func2· func1·¬func0  

* 這兩項分別對應 R-type 中的 `slt` (funct=101010) 及 `or` (funct=100101) 操作。

## Truth Table of Control Signal

| 指令類型 | opcode (6-bit) | RegDst | ALUSrc | MemtoReg | RegWrite | MemRead | MemWrite | Branch | ALUOp |
| ------ | -------------- | :----: | :----: | :------: | :------: | :-----: | :------: | :----: | :---: |
| R-type | 000000 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 10 |
| lw | 100011 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 00 |
| sw | 101011 | x | 1 | x | 0 | 0 | 1 | 0 | 00 |
| beq | 000100 | x | 0 | x | 0 | 0 | 0 | 1 | 01 |
| addi | 001000 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 00 |

若要支援 `j`（jump），需額外一個 Jump 控制訊號，由 opcode = `000010` 解出。

## PLA

$$
\text{RegWrite} = (\overline{op_5}\,\overline{op_4}\,\overline{op_3}\,\overline{op_2}\,\overline{op_1}\,\overline{op_0}) \;+\; (op_5\,\overline{op_4}\,\overline{op_3}\,\overline{op_2}\,op_1\,op_0)
$$

## Chapter - 4

### Datapath

1. **程式計數器 PC**：儲存下一筆要執行的指令位址。
2. **指令快取／記憶體 Instruction Memory**：取出指令。
3. **暫存器檔 Register File**：執行 ID 時讀取，WB 時寫回。
4. **ALU**：執行 EX 階段的算術／邏輯運算。
5. **資料記憶體 Data Memory**：執行 MEM 階段的讀／寫存取。
6. **立即值延伸器 Sign-Extender**：將立即數從 16-bit 擴展到 32-bit。
7. **多路選擇器（Mux）**：根據控制訊號選擇 ALU 或寫回資料來源。
8. **控制單元 Control Unit**：產生各階段所需的控制訊號，可分為主控（Main Control）和 ALU 控制（ALU Control）。

---

### 典型五態 FSM
1. **IF（Instruction Fetch）**
2. **ID（Instruction Decode / Register Fetch）**
3. **EX（Execute / Address Calculation）**
4. **MEM（Memory Access）**
5. **WB（Write Back）**

---

### 各階段詳細動作

| 階段 | 動作要點 |
| --- | ------------------------------------------------------------------------------------------------------------ |
| IF | - 從 `PC` 讀出指令：`Instr ← IM[PC]`<br/>- `PC ← PC + 4` |
| ID | - 解析指令欄位：`opcode`、`rs`、`rt`、`rd`、`imm`<br/>- 從暫存器檔讀取：`A ← R[rs]`, `B ← R[rt]`<br/>- 對立即數做 sign-extend |
| EX | - R-type：`ALUResult ← A op B`<br/>- Memory：`ALUResult ← A + sign_ext(imm)`<br/>- Branch：計算 `PC+4 + (imm<<2)` |
| MEM | - Load：`MDR ← DM[ALUResult]`<br/>- Store：`DM[ALUResult] ← B`<br/>- 其他指令跳過此階段 |
| WB | - R-type：`R[rd] ← ALUResult`<br/>- Load：`R[rt] ← MDR`<br/>- 不同指令對應不同寫回來源 |

### 範例流程

### 5.1 Load Word (`lw`)

1. IF → 取得指令
2. ID → 讀寄存器 `rs, rt`；立即數 sign-extend
3. EX → 計算目標地址 `A + imm`
4. MEM → 讀取記憶體 `MDR ← DM[Address]`
5. WB → `R[rt] ← MDR`

### 5.2 Store Word (`sw`)

1. IF → 取得指令
2. ID → 讀 `rs, rt`；立即數 sign-extend
3. EX → 計算位址 `A + imm`
4. MEM → `DM[Address] ← B`
5. WB → 無

### 5.3 R-type（算術／邏輯）

1. IF → 取得指令
2. ID → 讀 `rs, rt`
3. EX → `ALUResult ← A op B`
4. MEM → 無
5. WB → `R[rd] ← ALUResult`

### 5.4 Branch (`beq`)

1. IF → 取得指令
2. ID → 讀 `rs, rt`；立即數 sign-extend
3. EX → 比較 `A−B`，且計算分支目標 `PC+4+(imm<<2)`
4. MEM → 無
5. WB → 如果 `A==B`，則 `PC ← target`；否則保留 `PC+4`

### 控制有限狀態機（FSM）


### Pipeline

#### Strutural Hazard

不同指令使用到同一個元件，解決方法：固定所有指令長度（idle）


#### Pipeline Hazards

##### 結構衝突 (Structural Hazard)

* **定義**：當兩條或多條指令同一個週期需使用相同硬體資源，而該資源在此週期僅能一次性服務時，就會發生結構衝突。
* **範例**：IF 階段要從記憶體讀取指令 (Instruction Fetch)，同一週期 MEM 階段又要做資料存取 (`lw`/`sw`)，若只配置單一埠記憶體即會衝突。
* **解法**：
1. **哈佛架構** (Harvard)：指令與資料分別使用不同記憶體／快取，讓 IF 與 MEM 可並行存取。
2. **多埠記憶體**：設計多埠快取或複製關鍵硬體單元，支援多重存取。
3. **插入停頓** (Stall)：硬體偵測到衝突時，凍結後續階段，直到資源釋放為止，雖保證正確，卻犧牲效能。

---

##### 資料衝突 (Data Hazard)

* **定義**：指令之間存在資料相依，其中一條尚未完成寫回，後一條就嘗試讀取該結果，導致讀到「舊值」或無效資料。
* **主要類型**：
* **RAW (Read After Write)**：後一指令讀取的操作數，尚未被前一指令寫回寄存器。
* **WAR (Write After Read)** 與 **WAW (Write After Write)**，在五階段 MIPS 流水線中較少發生。
* **解法**：
1. **前推 (Forwarding / Bypassing)**：直接將 EX/MEM 或 MEM/WB 階段的 ALU 結果，經 bypass network 送回 EX 階段輸入，繞過寫回→讀取延遲。
2. **插入停頓 (Stall / Bubble)**：對於 load–use hazard（LW 後立即使用其讀出資料之情況），即使有 forwarding 也無法解決，須由 Hazard Detection Unit 插入 NOP 週期，延後後續指令執行。

---

##### 控制衝突 (Control Hazard)

* **定義**：分支或跳轉指令 (如 BEQ、J) 需要先判斷分支結果或目標位址，才能正確決定下一條要取的指令，否則可能在錯誤路徑上繼續抓指。
* **解法**：
1. **Always-Not-Taken**：預設不跳轉，若分支成立才 flush（清空）錯路指令。
2. **Early Branch**：在 ID 階段就完成比較 (compare)，減少必須 flush 的指令數量。
3. **分支預測 (Branch Prediction)**：採用靜態或動態預測（如 1-bit / 2-bit predictor），在硬體層面決定是否跳轉，並在預測錯誤時 flush 錯誤指令，減少停頓開銷。
4. **延遲分支 (Delayed Branch)**：編譯器將有效指令插入分支延遲槽 (delay slot)，利用這些槽位填滿流水線空閒。



## Chapter - 5

### Memory Hierarchy

#### 基礎知識

| 技術 | 存取時間 | 成本 |
| --- | ------- | --- |
| SRAM | 0.5 ~ 5 ns | $2000 ~ $5000 |
| DRAM | 50 ~ 70 ns | $20 ~ $75 |
| Magnetic Disk | 5 ~ 20 ms | $0.2 ~ $2 |

- 根據時代的演進
- Size 巨大成長
- Access Time 小幅度成長

為了解決存取時間問題而發明了 Memory Hierarchy 技術

* 記憶體分級
* Upper Level - 空間小 速度快
* Lower Level - 空間大 速度慢

#### 記憶體架構

| 階層 | 技術 | 容量範圍 | 讀取延遲 | 單位容量成本 | 位置 |
| -------------- | ---------- | ---------- | ----------- | ------ | ---------- |
| **寄存器** | Register | 幾十至上百字元 | \~0.1ns | 最高 | CPU 內部 |
| **快取 (L1)** | SRAM Cache | 16–64 KB | \~1–4 ns | 高 | CPU 內部 |
| **快取 (L2/L3)** | SRAM Cache | 幾百 KB–幾 MB | \~5–20 ns | 中 | CPU 晶片或封裝中 |
| **主記憶體** | DRAM | 幾 GB–數十 GB | \~50–100 ns | 低 | 記憶體插槽 |
| **次級儲存** | SSD / HDD | 幾百 GB–數 TB | \~0.1–10 ms | 非常低 | 機殼內儲存裝置 |
| **離線儲存** | 磁帶、光碟 | TB 以上 | 秒級以上 | 最低 | 外部、備份 |

---

### 效能衡量與最佳化

* **命中率 (Hit Rate)**：在快取中找到所需資料的比例；
* **缺失率 (Miss Rate)**：未命中時需往下層存取，導致額外延遲；
* **有效平均存取時間 (AMAT)**：

$$
\text{AMAT} = T_\text{hit} + R_\text{miss} \times T_\text{miss\_penalty}
$$

其中 $T_\text{hit}$ 為快取命中延遲，$R_\text{miss}$ 為缺失率，$T_\text{miss\_penalty}$ 為未命中處理的懲罰時間（包括向下層存取與填回快取所需時間）。

透過增加快取容量、提升關聯度 (associativity)、調整區塊大小 (block size) 及採用先進的替換策略，可有效提升命中率並降低 AMAT。

---

從 Access Time 從上到下排列 / 越上面空間越小

- Registers
- Cache
- Memory
- Disk
- Tape

可以透過 Cache Controller (Hardware) 把資料從 Memory 搬到 Cache 來加快 Performance

- 只在**相鄰兩層之間**搬資料 - Ex : Cache -> Memory

* Principle of Locality（局部性原理）
* **Temporal Locality**：近期使用的資料將再次被使用
* **Spatial Locality**：附近的記憶體位址將很快被使用

-----

### Cache 機制

如果 Cache 裡面沒有 CPU 要的資料就會去 Memory 撈，這種情況稱為 Cache Miss

- Hit Rate - 資料 Access 到的機率是多少
- Miss Rate - $1 - \text{Hit Rate}$
- Hit Time - Access Cache 的時間
- Miss Penalty - Cache Miss 以後去撈的時間
- Hit Time < Miss Penalty

#### Hierarchy 基本問題

把記憶單位區分成一塊一塊的 Block 分別存於 Cache 和 Memory

1. Block Placement - 要把 Memory Block 放在更上層的哪裡
2. Block Identification - 要怎麼識別這個 Block 是誰
3. Block Replacement - 要怎麼替換掉沒在用的 Block
4. Write Strategy - 如果資料被更新要怎麼寫入

#### Block Placement

像是 Hash Table 一樣用 Mod 的方式來找到放到更上層的位置


#### Block Identification & Block Replacement

- Block Identification
可以使用 Tag 來標示，除了用來識別以外也可標示其他資訊如 Valid Bit ( 1 才是有效的 )
- Block Replacement
在 Tag 重複的時候把舊的資料重新 Overwrite 成新的 Block



#### Write Strategy

- 如果 Write Block 是 Hit
- Write Through
在更新到 Cache 的時候順便寫到 Memory，但 Performance 差
- Write Buffer
在更新 Cache 的同時寫到 Write Buffer 來慢慢寫入，但 Buffer 滿了會會慢
- Write Back
先更新 Cache 並標示 Dirty Bit，1 為更改過 / 0 為沒被更改
如果 Dirty Block 要被 Replace 的時候再使用 Write Buffer
- 如果 Write Block 是 Miss
- Allocate on Miss - 把 Memory 撈進 Cache 再進行後續操作 (適合 Write Back)
- Write Around - 直接寫回 Memory (適合 Write Through)

| | **Write-Allocate** | **No-Write-Allocate** |
| ----------------------- | ------------------------------------------------------------------- | -------------------------------- |
| **Write-Back** | 先將寫入地址的資料行（cache line）載入快取，再在快取中更新；最終只在該行被汙損（dirty）且被逐出時，一次性寫回主記憶體。 | 寫入不先載入快取；直接在主記憶體執行寫入操作（通常搭配寫直通）。 |
| **Write-Through** | 先將寫入地址的資料行載入快取，再在快取與主記憶體同時更新；每次快取更新都同步寫入主記憶體。 | 不載入快取，寫入時直接送往主記憶體；快取中不保持該資料行。 |

---

### Cache Performance

- 增強 Cache Performance
- 設計更好的 Cache
- 增加 Clock Rate
- 減少 Base CPI
- 減少 Miss Rate
- 減少 Hit Time
- 減少 Miss Penalty

#### Memory Stall Cycle

= $\frac{\text{Memory Access}}{\text{Program}} \times \text{Miss Rate} \times \text{Miss Penalty}$

= $\frac{\text{Instructions}}{\text{Program}} \times \frac{\text{Misses}}{\text{Instruction}} \times \text{Miss Penalty}$

**Example**

- Given
- I-Cache (Instruction) Miss Rate = 2%
- D-Cache (Data) Miss Rate = 4%
- Miss Penalty = 100 Cycles
- Base CPI = 2
- Load & Stores are 36% of Instructions
- Miss Cycles Per Instruction
- I-Cache
1 **(All Instructions)** $\times$ 0.02 **(Miss Rate)** $\times$ 100 **(Miss Penalty)** = 2
- D-Cache
0.36 **(36% Instructions)** $\times$ 0.04 **(Miss Rate)** $\times$ 100 **(Miss Penalty)** = 1.44
- Actual CPI = 2 **(Base)** + 2 **(I-Cache)** + 1.44 **(D-Cache)** = 5.44

#### AMAT - Average Memory Access Time

- **Hit Time + Miss Rate $\times$ Miss Penalty**

**Example**

- Given
- CPU Clock = 1ns
- Hit Time = 1 Cycle
- Miss Penalty = 20 Cycles
- I-Cache Miss Rate = 5%
- AMAT
- 1 + 0.05 $\times$ 20 = 2ns
- 2 Cycles Per Instruction

#### 改善 Cache Performance

- Block Size 變大
把 Cache 的 Block Size 增加可以減少 Miss Rate 但加太大會爛
- Block 數量減少
- 可能增加沒用的資料 (Cache Pollution)
- 增加 Miss Penalty
- Direct Mapped (One-Way Set Associative)
一個位置 Hash 完對一個，沒有任何解釋空間
- Fully Associative
把所有的 Block 可以的位置都放
- Performance 會炸開，因為要把所有 Block 都檢查過一次
- n-way Set Associative
把資料擺在 n 個位置，如果一個不行就算下一個直到 n
- 不需要翻過所有全部的 Block


Direct Mapped Cache 的時候在拿到 Tag 的同時也拿到值，可以直接先做事再做 Tag Compare 來增強 Performance，但 n-way Set Associative 不行

- Replacement 技術
Random - 隨機踢掉一個資料來拿空間
LRU - 把最舊沒被用到的資料踢掉
Pseudo LRU - 俄羅斯輪盤 有人進來就指下一個人，滿了就把指到的人送去古拉格💀

#### Multi Level Cache

分為不同 Level 的 Cache 來增強 Cache 總體的 Performance
- Primary Cache - 讓 Hit Time 越短越好
- L-2 Cache - 容量更大 讓 Primary Cache 能更快在這邊找到東西

**Example**

* Given
* CPI Base CPI = 1
* Clock Rate = 4GHz
* Miss Rate = 2%
* Main Memory Access Time = 100ns

Compute

- Primary Cache Only
- Miss Penalty = 100ns / 0.25 ns (4GHz 的倒數) = 400 Cycles
- **Effect CPI = 1 + 0.02 $\times$ 400 = 9**
- Primary & L-2 Cache
- Access Time = 5ns
- Global Miss Rate to Main Memory = 0.5%
- Primary Miss with L-2 Hit
- Penalty = 5ns / 0.25ns = 20 Cycles
- Primary Miss with L-2 Miss
- Extra Penalty = 400 Cycles
- CPI = 1 + 0.02 $\times$ 20 + 0.005 $\times$ 400 = 3.4
- Performance Ration = 9/3.4 = **2.6**

#### 發生 Cache Miss 的原因

- Compulsory
絕對不可避免的情況，在開機時不可能有資料的那種
- Conflict
一堆人在搶同一個位置的情況
- 增加 Cache Size
- 增加 Associativity
- Capacity
Cache 容量不夠的問題

-----

### Virtual Memory

#### 基本知識

- 每個程式都有自己的獨立記憶體空間
- 提供比實體記憶體更大的 Virtual Space
- 一個 Block 被稱為 Page (Virtual) 或是 Frame (Physical)
- Page Fault - Virtual Address 無對應 Physical Page
- Page Fault 會透過 Trap 來對 OS 發出 IRQ
- 用查表方式來拿對應的 Physical Address
- 前 31~12 bit 是 Virtual Page Number
- 經過 Translation 變成 Physical Frame Number
- Physical Frame Number + offset = Physical Address


- Virtual Address 會透過 Translation 的機制取得 Physical Address
- CPU 會先用 Physical Address 從 Cache 撈資料，Page Fault 再去更深的地方撈
- Page Table
- Dirty Bit / 最後一次被 Access 的時間 / ... 等資訊

### Address Tanslation Example

- Virtual Memory Size = $2^{20}$ Bytes
- Page Size = $2^{10}$ Bytes
- Virtual Address = 7414
- 把 Virtual Address 轉成 Index
- 從 Page Table 裡面撈 Frame Address
- 取 Page Offset -> 7414 % 1024 ($2^{10}$) = 246
- Physical Address = Page Offset + Frame Address


### Two-Level Page Tables

- 前面切一半分成兩個 Table 的 Index


### TLB

TLB = Page Table Cache

jalr

func main():

jalr meow()

func meow():

mov $ra, [rsp]

jr $ra
return -> PC <- $ra