# 計算機組織 - 戴碧如
> **維護者：呂思遠**

## 課程資訊
> 考試以課堂簡報為主

> **分數**
> Quizzes 30%
> Exams 70%

## Chapter 1

### 1.1 導論 (Introduction)
- **摩爾定律（Moore’s Law）**：IC（Integrated Circuit）上的電晶體數量每兩年（約18個月）翻倍，驅動計算技術進步。
- Classes of Computers：
- 個人電腦（PC）：通用用途，具成本效能權衡
- 伺服器（Server）：提供網路服務，高容量、高效能、高可靠性
- 超級電腦（Supercomputer）：用於科學計算與工程模擬，市場占比小但效能最高。
- 嵌入式系統（Embedded Computers）：內建於其他系統，受限於功耗、成本與效能需求。
- The Post-PC Era（後 PC 時代）
- 個人行動裝置（PMD, Personal Mobile Device）
- 智慧型手機、平板電腦、智慧眼鏡
- 電池供電，具備網路連接能力
- 雲端運算（Cloud Computing）
- 倉儲級計算機（Warehouse-Scale Computers, WSC）
- SaaS（Software as a Service）
---

### 1.2 電腦架構的七大核心概念 (Seven Great Ideas in Computer Architecture)
* 抽象化（Abstraction）
* 讓常見情境變快（Make the common case fast）
* 透過並行提升效能（Performance via parallelism）
* 透過管線化提高效能（Performance via pipelining）
* 透過預測提高效能（Performance via prediction）
* 記憶體階層設計（Hierarchy of memories）
* 透過冗餘提升可靠性（Dependability via redundancy）
---

### 1.3 程式底層運作 (Below Your Program)
- Application Software：以高階語言（High-Level Language, HLL）撰寫。
- System Software：
- Compiler：將HLL轉換為機器碼（Machine Code）。
- Operating System (OS)：管理I/O、記憶體、排程與資源共享。
- Hardware：
- Processor、Memory、I/O Controllers。
---

### 1.4 電腦的內部組成 (Under the Covers)
- Instruction Set Architecture (ISA)：硬體與軟體的介面。
- Application Binary Interface (ABI)：ISA與系統軟體的接口。
- Implementation：ISA之下的硬體設計細節。
---

### 1.5 Performance (效能衡量)
- Response Time（Execution Time）：執行任務所需時間。

- Throughput（Bandwidth）：單位時間內處理的工作數量。
影響因素：

- Algorithm：決定執行的運算數量。
- Programming Language, Compiler, Architecture：決定每個運算所需的機器指令數量。
- Processor and Memory System：影響指令執行速度。
- I/O System (including OS)：影響I/O操作速度。
- Performance 計算方式：

- Performance 計算方式：
$$Performance = \frac{1}{\text{Execution Time}}$$ 若程式在 $A$ 電腦執行 $10$ 秒，在 $B$ 電腦執行 $15$ 秒，則：
$$
\text{Performance}_A= \frac{\text{ExecutionTime}_B}{\text{ExecutionTime}_A} = \frac{15}{10} = 1.5
$$ 表示 $A$ 比 $B$ 快 $1.5$ 倍。
---

### 1.6 CPU 時脈機制 (CPU Clocking)
- Clock Cycle（時脈週期）：數位硬體運作以固定時脈為基準。
- Clock Frequency（時脈頻率）：
- $\text{Clock Period} = 250 \text{ ps} = 0.25 \text{ ns} = 250 \times 10^{-12} \text{ s}$
- $\text{Clock Frequency} = 4.0 \text{ GHz} = 4000\text{ MHz} = 4.0\times10^{9}\text{ Hz}$
- CPU Time 計算方式：
$$\text{CPU Time}= \text{CPU Clock Cycles}\times\text{Clock Cycle Time} = \frac{\text{Clock Cycles}}{\text{Clock Rate}}$$
---

### 1.7 指令數與每指令週期數 (Instruction Count and CPI)
- Instruction Count（IC）：執行程式所需的指令數量，由程式、ISA 和 Compiler 決定。
- Cycles Per Instruction (CPI)：指令的平均週期數，由 CPU 硬體決定。
- CPI 計算方式：
$$\text{CPU Time}=\text{Instruction Count}\times\text{CPI}\times\frac{1}{\text{Clock Rate}}$$
---

### 1.8 CPI Example (CPI 計算範例)
- 若兩台電腦執行相同 ISA，且：
- $\text{Computer A：Cycle Teme} =250 \text{ ps，CPI} = 2.0$
- $\text{Computer B：Cycle Teme} =500 \text{ ps，CPI} = 1.2$
- 計算CPU時間：
$$\text{CPU Time}_A=\text{IC}\times2.0\times250\text{ ps} = \text{I}\times\text{500 ps}$$
$$\text{CPU Time}_B=\text{IC}\times1.2\times500\text{ ps} = \text{I}\times\text{600 ps}$$
$$\frac{\text{CPU Time}_B}{\text{CPU Time}_A} = \frac{\text{I}\times 600\text{ ps}}{\text{I}\times 500\text{ ps}} = 1.2$$
---

### 1.9 CPI in More Detail(多個CPI)
- 當不同類型的指令需要不同的時鐘週期（Clock Cycles）時，總時鐘週期可表示為：
$$\text{Clock Cycles}=\sum_{i=1}^{n}(\text{CPI}_i\times\text{Instruction Count}_i)$$
- Weighted average CPI
$$\text{CPI} = \frac{\text{Clock Cycles}}{\text{Instruction Count}}
= \sum_{i=1}^{n} \left( \text{CPI}_i \times \frac{\text{Instruction Count}_i}{\text{Instruction Count}} \right)$$

- **CPI Example**
- **不同的編譯方式可能導致不同的指令序列**
- 以 **A、B、C 三類指令** 為例：

| **Class** | **A** | **B** | **C** |
|------------|------|------|------|
| **CPI for class** | 1 | 2 | 3 |
| **IC in sequence 1** | 2 | 1 | 2 |
| **IC in sequence 2** | 4 | 1 | 1 |

**Sequence 1 計算：** **Instruction Count (IC) = 5**
- **Clock Cycles 計算**：
$1 \times 2 + 2 \times 1 + 3 \times 2 = 10$
- **平均 CPI**： $10/5 = 2.0$

**Sequence 2 計算：** **Instruction Count (IC) = 6**
- **Clock Cycles 計算**：
$1 \times 4 + 2 \times 1 + 3 \times 1 = 9$
- **平均 CPI**： $9/6 = 1.5$

---
### 1.10 Pitfall: Amdahl's Law
- 公式
$$ \text{T}_{\text{improved}} = \frac{\text{T}_{\text{affected}}}{\text{improvement factor}} + \text{T}_{\text{unaffected}} $$

- $\text{T}_{\text{affected}} + \text{T}_{\text{unaffected}} = 100\%$
---

### 1.11 Performance Summary (效能總結)
- Performance 受以下因素影響：
- Algorithm：影響 Instruction Count (IC) 和 CPI。
- Programming Language & Compiler：影響 IC 和 CPI。
- Instruction Set Architecture (ISA)：影響 IC、CPI 和 Clock Cycle Time。
$$\text{CPU Time = Instruction Count}\times\text{CPI}\times\text{Clock Cycle Time}$$

---
## Chapter 2

### [✨組合語言指令大禮包✨](https://hackmd.io/@Left-owo/HkhghCr3yg)
---

### 2.1 指令集（Instruction Set）
- 電腦能執行的所有「基本操作」的集合。
- 不同電腦架構有不同的指令集，但邏輯架構相似。
- MIPS 是本章範例架構，屬於簡潔的 RISC 架構，指令格式統一。
---

### 2.2 運算指令（Arithmetic Operations）
- 格式範例：`add $s0, $s1, $s2`(`$s0 = $s1 + $s2`)
- 三個暫存器為運算基礎：兩個來源、一個目的。

Example：

C code：f = (g + h) - (i + j)
$s0	f
$s1	g
$s2	h
$s3	i
$s4	j

MIPS：
add $t0, $s1, $s2   # $t0 = g + h
add $t1, $s3, $s4   # $t1 = i + j
sub $s0, $t0, $t1   # $s0 = $t0 - $t1
即 f = (g + h) - (i + j) 

---

### 2.3記憶體操作（Memory Operands）
- MIPS 使用 load/store 架構
- `lw`：從記憶體載入 → 暫存器
- `sw`：從暫存器存回 → 記憶體
- 記憶體是以 位元組（byte）為單位編址，32-bit 稱 word（4 位元組）。
- Big Endian：高位元組存在低位址
- 在 MIPS 架構中，MIPS 採用 Load/Store 架構，不允許直接對記憶體資料做運算。

Example：

c code：A[12] = h + A[8]
$s2	h（來源之一）
$s3	A（陣列基底位址）
$t0	暫存計算結果

MIPS：
lw  $t0, 32($s3)    # $t0 = A[8]
add $t0, $s2, $t0   # $t0 = h + A[8]
sw  $t0, 48($s3)    # A[12] = $t0，12 × 4 = 48

位移量計算方式：MIPS 的 word 是 4 bytes，因此 A[n] 的實際偏移量為 n × 4。

---

### 2.4即時值（Immediate Operands）
- 指令中可以直接給常數：
`addi $s2, $s1, 1（$s2 = $s1 + 1）`
- 常數避免再去記憶體抓資料，效率更高。
- 減法運算: `addi $s2, $s1, -1`
- 零(constant zero)：$zero
---

### 2.5整數表示（Integer Representations）
* 無號整數（unsigned）：0 ~ 2ⁿ - 1
* 有號整數（2’s Complement）：-2ⁿ⁻¹ ~ 2ⁿ⁻¹ - 1
* 負數表示法：補數＋1
* 擴位（Sign Extension）：延伸時保留正負號
---

### 2.6指令格式（Instruction Formats）
* 所有指令用 32位元二進位 表示。
* 常見格式：
* R-type：register-register（e.g., add, sub）
* I-type：immediate / memory（e.g., addi, lw, sw）
* op (6 bits)、rs、rt、rd、shamt、funct、immediate … 等欄位固定長度。

Example：

op      rs    rt    rd   shamt  func
000000 10001 10010 01000 00000 100000
R-type  17    18    8      0    add

add $t0, $s1, $s2

---

### 2.7邏輯運算（Logical Operations）
* 位元操作：AND、OR、NOR、NOT、SHIFT
* sll(shift left logical) 可達到 x2 效果（僅限 unsigned）
* srl(shift right logical) 可達到 ÷2 效果（僅限 unsigned）
---
### 2.8條件與跳躍（Conditional & Branching）
* beq, bne：根據條件跳轉
* j L1：無條件跳轉
* slt, slti：比較小於 → 設為 1 or 0
* 使用組合語法模擬 if, while 等高階語法

Example:

C code:
if (a == b) {
    x = 1;
} else {
    x = 2;
}

MIPS：
    beq  $s0, $s1, L1   # 如果 a == b，跳轉到 L1
    li   $t0, 2         # x = 2
    j    L2             # 跳過 L1
L1:
    li   $t0, 1         # x = 1
L2:

---

### 2.9 程序呼叫（Procedure Calling）
* 使用：
* $a0-$a3：參數（最多 4 個）
* $v0-$v1：回傳值（最多 2 個）
* $ra：返回位址
* jal 跳到副程式，jr $ra 回主程式。
* 使用堆疊（stack）保存暫存器值，防止資料遺失。

Example：

C code:
int add(int x, int y) {
    return x + y;
}

int main() {
    int a = 5, b = 7;
    int result = add(a, b);
}

MIPS：
    li  $a0, 5       # 參數 a = 5
    li  $a1, 7       # 參數 b = 7
    jal add_function # 跳到副程式
    move $t0, $v0    # 把回傳值存入 $t0（result）
    # 主程式繼續執行...
add_function:
    add $v0, $a0, $a1  # v0 = a0 + a1
    jr  $ra            # 返回主程式

---

### 2.10 字元與字串操作（Character & String）
* 字元使用 ASCII 編碼。
* 支援 lb, lbu, lh, lhu, sb, sh 操作 byte 與 halfword。
* 以 null-terminated 字串為主（\0 表結尾）
---

### 2.11 Byte/Halfword Operation
| 指令 | 資料大小 | 操作類型 | 是否符號延伸 | 說明 |
|-------|-----------|--------------|----------------------|-------------------------------------------|
| `lb` | 8 位元 | 載入（load） | 是（sign-extend） | 將 byte 視為帶符號整數，延伸成 32-bit |
| `lbu` | 8 位元 | 載入（load） | 否（zero-extend） | 將 byte 視為無號整數，補 0 成 32-bit |
| `lh` | 16 位元 | 載入（load） | 是（sign-extend） | 將 halfword 視為帶符號整數，延伸成 32-bit |
| `lhu` | 16 位元 | 載入（load） | 否（zero-extend） | 將 halfword 視為無號整數，補 0 成 32-bit |
| `sb` | 8 位元 | 儲存（store）| 無 | 僅將暫存器的最低 8 位元儲存到記憶體 |
| `sh` | 16 位元 | 儲存（store）| 無 | 僅將暫存器的最低 16 位元儲存到記憶體 |

---