# Ch4：The Processor
本章節將介紹 Processor 的硬體結構

## 4-1 Introduction
- **Instruction Count**：由 ISA 決定
- **CPI and cycle time**：由 CPU 決定

### Instruction Execution
:::warning
**PC（Program Counter）**：用來記錄下一個要執行的 instruction 的 memory address
:::
1. **Fetch**：藉由 PC 從 Instruction memory 中 fetch instruction
2. **Decode**：根據 instruction 中的 register number，從 register file read 對應的 register
3. **Execute**：
- 根據不同的 instruction types：I-types, R-types, J-types 會有不同行為
- 使用 **ALU** 做計算
4. **Memory access**：如果是 load/store 指令，就要 access/write data memory
5. **Write-back/PC update**：跳躍 address（J-types）或 PC + 4

### CPU overview

### Control

## 4-2 Logic Design Conventions
### Combinational Elements
### Sequential Element
- **D flip-flop**：
- 用來當作儲存 data 的方法
- 只有在 clk 上升時，D 的值才會傳到 Q
- **Write**：
- 只有在 clk 上升 + `write = 1` 時，D 才會寫入 Q

### Clocking Methodology
因為只有 clk 上升時才會更新資料，把兩次 clk 上升之間的時間稱為 clock cycle

## 4-3 Building a Datapath
### Instruction Fetch

### R-Format Instructions
- read 2 register operands
- 進行**算術運算**與**邏輯運算**
- 把結果寫進指定的 register

### Load/Store Instruction

### Branch instructions
1. 取出 register 的兩個值
2. ALU 相減 → 檢查是否為 0（Zero）
3. 若為 0（或符合條件）：
- 將 offset 符號延伸並左移兩位
- 加到 PC + 4
- 更新 PC = 新位址（跳躍）
4. 否則就繼續執行下一條（PC + 4）

### R-type/Load/Store Datapath
- 綠色：R-type
- 黃色：Load
- 粉色：Store

### Full Datapath

## 4-4 A Simple Implementation Scheme
### ALU control
ALU 的用途如下：
- Load/Store：`F = add`
- Branch：`F = subtract`
- R-type：依據 function field 來判定

| ALU control | Function | 功能說明 |
| ----------- | ---------------- | ------------------------------------ |
| `0000` | AND | 執行邏輯與（AND） |
| `0001` | OR | 執行邏輯或（OR） |
| `0010` | add | 執行加法（通常用於加總或 load/store 位址） |
| `0110` | subtract | 執行減法（常用於比較分支） |
| `0111` | set-on-less-than | 若 op1 < op2，結果為 1，否則為 0（用於 `slt` 指令） |
| `1100` | NOR | 執行邏輯 NOR（NOT OR） |

### Main control unit

### Datapath with Control

### R-type Instruction
通過路徑：PC -> I-mem -> Mux -> Registers -> Mux -> ALU -> Mux -> Register

### Load Instruction
通過路徑：PC -> I-mem -> Mux -> Registers -> Mux -> ALU -> D-mem -> Mux -> Register

### Branch on equal instruction
通過路徑：PC -> I-mem -> Mux -> Registers -> Mux -> ALU

### J-types

## 4-5 An Overview of Pipelining
### MIPS pipeline
- **IF**：Instruction fetch
- **ID**：Instruction decode
- **EX**：Execute an operation or calculate a address
- **MEM**：Access memory operand
- **WB**：write a result back tp register

### Pipeliin performance

### Hazard
- **Structure hazard**：
- **定義**：當兩條指令在同一個 cycle 內需要同一個硬體資源，而該資源無法同時供應。
- **例子**：同時有一條指令在讀指令記憶體，另一條指令也需要用到相同的記憶體（例如資料記憶體未分離時）。
- **解法**：複製資源（如分開的 instruction/data memory），或加上 pipeline stall。

- **Data hazard**：
- **定義**：當一條指令依賴於**前一條指令的運算結果**，但這個結果尚未寫回暫存器。
- **例如**：

    add $t0, $t0, $t1   ; 第 1 條指令
    sub $t2, $t0, $t3   ; 第 2 條指令依賴 $t0

- **解法**：forwarding 或 pipeline stall
- **Control hazard**：
- **定義**：發生在分支指令（如 beq、jmp），下一條指令的執行流程取決於跳躍結果。
- **例子**：

    beq $t0, $t1, label

- **解法**：branch prediction, delay slot, pipeline stall

### Forwarding
讓下一條式子可以提早用到資料，不用等資料寫入 data memory
:::warning
Forwarding 僅適用於結果在 EX 後即可知道的 instruction，像 load 的結果必須在 MEM 之後才知道
:::

### code scheduling
透過調整 instruction 的順序來避免 **data hazard**

### control hazard
- `bne`, `beq` 等 instruction 會影響下一步要執行的 instruction 是哪一個
- 然而，結果必須要到 EX 之後才會知道 -> control hazard
- **stall on Branch**：

### Branch Prediction
- 可以先與預測哪一個 instruction 會執行
- 只有猜錯才需要 stall
- **Static branch prediction**：
- 概念：根據「典型分支行為」來預設判斷，在編譯時或固定規則下做出預測。
- 常見規則：
- **Backward branches**（通常是 loop 結尾）→ 預測會跳（taken）
- **Forward branches**（例如 if-else 分支）→ 預測不跳（not taken）
- **優點**：簡單、硬體成本低
- **缺點**：不考慮實際執行狀況 → 準確率有限
- **Dynamic branch prediction**：
- 概念：由**硬體根據實際執行結果記錄**分支歷史行為，動態做出預測
- 做法：
- 例如：用 **1-bit 或 2-bit predictor** 來記住某分支最近是 taken 還是 not taken
- 假設未來行為會延續過去趨勢（Assume future behavior will continue）
- 當預測錯誤時：
- **pipeline 會 stall（暫停）**
- **重抓正確指令**，同時**更新歷史記錄**

| 項目 | Static branch prediction | Dynamic branch prediction |
| ---- | ----- | ------- |
| 預測依據 | 編譯時規則 | 執行時行為 |
| 精確度 | 中等 | 高（根據歷史） |
| 成本 | 低 | 高（需要硬體） |
| 常見場景 | 精簡處理器 | 高效能 CPU |

## 4-6 Pipelined Datapath and Control
### Pipeline Register
在每個 stage 之間加入 register，用來記錄前一個 **cycle** 的資料

### Multi-cycle pipeline diagram

## 4-7 Data Hazards: Forwarding versus Stalling
## 4-8 Control Hazards
## 4-9 Exceptions
## 4-10 Parallelism via Instructions