111 年 國立中山大學電機工程學系碩士班己組《計算機結構》

核心觀念

本題為計算機結構經典範例（源自 Patterson & Hennessy《Computer Organization and Design》），主要測驗以下三大核心觀念：

1. 高階語言結構轉譯（High-Level to MIPS Assembly）：
   • 雙重迴圈（Nested Loops）條件判斷與分支跳躍結構（slt, slti, beq, bne, j）。
   • 陣列基底位址與索引位移運算：在 32-bit 架構中，整數陣列（int）每個元素佔 4 個位元組（Bytes），陣列元素位址計算公式為：
     $\text{Address}(v[k]) = \text{Base}(v) + (k \times 4)$
     其中乘 4 透過邏輯向左位移 2 位元（sll $reg, $reg, 2）完成。
2. 程序呼叫約定（Procedure Calling Conventions / ABI）：
   • 非葉節點程序（Non-leaf Procedure）：sort 內部會呼叫子程序 swap，故在執行 jal（Jump and Link）前，必須將返回位址暫存器 $ra 及被呼叫者保存暫存器（Callee-saved registers, $s0～$s3）壓入堆疊（Stack）予以保存，返回前再從堆疊回復。
   • 葉節點程序（Leaf Procedure）：swap 不呼叫其他函式，且僅使用暫時暫存器（Caller-saved registers, $t0～$t2），因此不需要存取堆疊，直接透過 jr $ra 返回。
3. 暫存器分配規則：
   • 引數傳遞：$a0（陣列基底位址 $v$）、$a1（陣列大小 $n$ 或元素索引 $k$）。
   • 區域變數保存：$s0（外迴圈變數 $i$）、$s1（內迴圈變數 $j$）、$s2（保存陣列基底位址 $v$）、$s3（保存長度 $n$）。

---

解題方法

本題實作採用經典的插入排序法（Insertion Sort / Bubble-style Sort）。為了維持模組化與高可讀性，切分為兩部分：

1. 子程序 swap(v, k)：交換陣列中相鄰兩元素 $v[k]$ 與 $v[k+1]$。
2. 主排序程序 sort(v, n)：外層迴圈自 $i = 0$ 迭代至 $n - 1$；內層迴圈自 $j = i - 1$ 開始往前檢查，若 $j \ge 0$ 且 $v[j] > v[j+1]$ 則呼叫 swap(v, j)，否則提早終止內層迴圈。

---

(2) 高階程式語言（C 語言）設計理念與實作

設計構想

• 資料結構與介面：定義 sort(int v[], int n)，接收整數陣列指標 v 及元素個數 n。
• 功能模組化：抽離元素交換操作為 swap(int v[], int k)，讓 MIPS 組合語言能具體示範呼叫者（Caller）與被呼叫者（Callee）之間的暫存器保護機制（Stack Spill）。
• 演算法流程：
  1. swap(v, k) 使用暫存變數 temp 暫存 $v[k]$，將 $v[k+1]$ 寫入 $v[k]$，再將 temp 寫入 $v[k+1]$。
  2. sort(v, n) 使用外層迴圈變數 $i$ 逐步擴展已排序區間，內層迴圈變數 $j$ 負責將新加入的元素 $v[j+1]$ 向左移動至正確位置。

C 語言原始碼

// 交換陣列中相鄰兩元素 v[k] 與 v[k + 1]
void swap(int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k + 1];
    v[k + 1] = temp;
}

// 對長度為 n 的陣列 v 進行由小到大遞增排序
void sort(int v[], int n) {
    int i, j;
    for (i = 0; i < n; i += 1) {
        for (j = i - 1; j >= 0 && v[j] > v[j + 1]; j -= 1) {
            swap(v, j);
        }
    }
}

---

(1) MIPS 組合語言實作（含逐行詳細註解）

暫存器映射配置

• $a0：陣列基底位址 $v$
• $a1：陣列長度 $n$（在 swap 中為索引 $k$）
• $s0：外迴圈變數 $i$
• $s1：內迴圈變數 $j$
• $s2：保存的陣列基底位址 $v$
• $s3：保存的陣列大小 $n$

第 2 題詳解

核心觀念

本題考查處理器管線、快取記憶體、浮點數表示法、分支處理，以及半導體記憶體的基本觀念。作答時應包含「定義、運作方式、優缺點與典型應用」。

---

(a) Forwarding（資料轉送／旁路）

核心觀念

Forwarding 是處理器用來解決管線資料相依的方法。當前一條指令已經產生結果，但結果尚未寫回暫存器，後一條指令卻已經需要使用該結果時，處理器可將結果直接從管線暫存器或功能單元輸出端，轉送至後續指令的運算輸入端。

它主要解決 RAW（Read After Write）資料危障：

$$I_1:\ R1 \leftarrow R2+R3$$ $$I_2:\ R4 \leftarrow R1-R5$$

$I_2$ 需要讀取 $I_1$ 產生的 $R1$。若等待 $I_1$ 完成寫回，必須插入停頓；使用 forwarding 後，$I_1$ 在執行階段產生的結果可直接送給 $I_2$ 的 ALU。

解題方法

在典型五級管線中：

1. 前一指令在 EX 階段產生 ALU 結果。
2. 結果先存於 EX/MEM 或 MEM/WB 管線暫存器。
3. 後續指令在 EX 階段需要運算元時，由多工器選擇轉送路徑。
4. 不必等待結果先寫回暫存器檔案。

但 forwarding 無法完全消除所有資料危障。例如：

LW   R1, 0(R2)
ADD  R3, R1, R4

載入指令的資料要到 MEM 階段結束才取得，而下一條 ADD 很快便進入 EX 階段，因此仍需插入一次 stall，之後再透過 forwarding 傳送資料。

解題技巧與陷阱

• 看到「結果尚未寫回，但後續指令已需要」即可聯想到 forwarding。
• Forwarding 主要處理 RAW，不是用來解決分支危障或結構危障。
• load-use hazard 即使有 forwarding，仍常需停頓一個週期。
• Forwarding 也稱為 bypassing，重點是「繞過暫存器寫回階段」。

---

(b) Fully Associative Cache（全相聯快取）

核心觀念

Fully associative cache 是一種快取對映方式，其中主記憶體的任何區塊都可以放入快取中的任何一條 cache line。

若位址共有 $A$ 位元、每個區塊大小為 $2^b$ bytes，則位址欄位為：

• Block offset：$b$ 位元
• Index：$0$ 位元
• Tag：$A-b$ 位元

因為沒有固定的 index，處理器必須將輸入位址的 tag 與快取中所有有效 cache line 的 tag 同時比較。

解題方法

存取流程如下：

1. 以位址中的 block offset 找出區塊內的 byte 或 word。
2. 將位址 tag 與所有 cache line 的 tag 平行比較。
3. 若任一條 cache line 的 tag 相同且 valid bit 為 $1$，即為 cache hit。
4. 若沒有符合者，即為 cache miss。
5. 發生 miss 時，可將資料放入任意一條 cache line，並依照 LRU、FIFO 或 random 等替換政策選擇被淘汰的資料。

優缺點

優點：

• 不存在 direct-mapped cache 的 conflict miss。
• 區塊放置彈性最高。
• 適合小型快取或需要高度彈性的結構。

缺點：

• 每次存取都要比較全部 cache line 的 tag。
• 需要大量平行比較器或 associative search 硬體。
• 面積、功耗與硬體複雜度較高，不適合大型快取。

Fully associative cache 只能消除 conflict miss，仍然會發生 compulsory miss 與 capacity miss。

解題技巧與陷阱

判斷重點是：

全主記憶體區塊均可放入任一 cache line，因此沒有 index 欄位，且所有 tag 必須平行比較。

不要將 fully associative 誤認為「快取容量等於主記憶體容量」。

---

(c) IEEE 754 Standard（IEEE 754 浮點數標準）

核心觀念

IEEE 754 是規範二進位浮點數表示法、浮點運算、捨入方式與特殊值的標準。常見格式如下：

格式	Sign	Exponent	Fraction	Bias
Binary32	1 位元	8 位元	23 位元	127
Binary64	1 位元	11 位元	52 位元	1023

對於一般化的正規化數：

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

其中：

• $S$ 為符號位元，$0$ 表示正數，$1$ 表示負數。
• $E$ 為偏移後的指數欄位。
• $F$ 為 fraction 欄位。
• 正規化數具有隱含的 leading $1$，所以實際有效數字為 $1.F$。

特殊表示

以 Binary32 為例：

1. $E=0$ 且 $F=0$：表示 $+0$ 或 $-0$。
2. $E=0$ 且 $F\ne0$：表示 subnormal number：

$$(-1)^S\times(0.F)_2\times2^{1-127}$$

3. $E=255$ 且 $F=0$：表示正無限大或負無限大。
4. $E=255$ 且 $F\ne0$：表示 NaN（Not a Number）。
5. 其他指數欄位：表示正規化浮點數。

IEEE 754 也規定浮點運算的捨入方式，預設方式為「最接近值，遇到中間值取偶數」（round to nearest, ties to even）。

解題方法：表示 $13.25$

先轉為二進位：

$$13.25=(1101.01)_2$$

正規化：

$$(1101.01)_2=(1.10101)_2\times2^3$$

因此 Binary32 的欄位為：

【核心觀念】

本題評量經典 MIPS 五級管線處理器（5-Stage Pipelined Processor: IF, ID, EX, MEM, WB） 的核心微架構設計與冒險（Hazard）處理機制：

1. 管線資料路徑（Datapath）與控制單元：包含五個管線暫存器（$\text{IF/ID}$、$\text{ID/EX}$、$\text{EX/MEM}$、$\text{MEM/WB}$）、轉發單元（Forwarding Unit）及冒險偵測單元（Hazard Detection Unit）。
2. 分支指令（Branch Instruction）的執行與控制冒險：包含分支目標位址計算（Target Address Calculation）、條件比較（Branch Condition Test）提早至 $\text{ID}$ 級執行的硬體修改與管線沖刷（Flush）機制。
3. 資料冒險（Data Hazard / RAW Dependency）與解決方案：分為「可由轉發完全解決的運算冒險」與「需暫停一個週期（Stall/Bubble）加轉發解決的載入使用冒險（Load-Use Data Hazard）」。

---

【各小題完整詳解】

(a) 五級 MIPS 管線處理器資料路徑圖（含 Hazard Detection 與 Forwarding）

在標準 MIPS 五級管線架構中，轉發單元（Forwarding Unit）設於 $\text{EX}$ 級，冒險偵測單元（Hazard Detection Unit）設於 $\text{ID}$ 級；分支決定提早於 $\text{ID}$ 級完成以降低分支延遲（Branch Penalty）。

1. 資料路徑方塊圖（Datapath Diagram）

(a) Direct-mapped Cache (16 one-word blocks)

對於 32-bit 的 Word Address，其位址分割如下：

• Block Offset：$0$ bits（以 Word 為單位定址）
• Index：$\log_2(16) = 4$ bits（Word Address 最右側 4 bits，即 $\text{Word Address} \pmod{16}$）
• Tag：$32 - 4 = 28$ bits（Word Address 除以 16 的商，即 $\lfloor \text{Word Address} / 16 \rfloor$）

各參考記憶體位址之分析如下表（Cache 初始為空）：

Reference (Dec)	32-bit Binary Address (Word)	Tag (Dec)	Index (Dec)	Index (Binary)	Hit / Miss
75	00000000000000000000000001001011	4	11	1011	Miss
33	00000000000000000000000000100001	2	1	0001	Miss
131	00000000000000000000000010000011	8	3	0011	Miss
18	00000000000000000000000000010010	1	2	0010	Miss
217	00000000000000000000000011011001	13	9	1001	Miss
25	00000000000000000000000000011001	1	9	1001	Miss
181	00000000000000000000000010110101	11	5	0101	Miss
21	00000000000000000000000000010101	1	5	0101	Miss
194	00000000000000000000000011000010	12	2	0010	Miss
253	00000000000000000000000011111101	15	13	1101	Miss
1	00000000000000000000000000000001	0	1	0001	Miss
11	00000000000000000000000000001011	0	11	1011	Miss

總存取次數為 12 次，全部皆為 Miss。

【答案】

• 每一筆存取之二進位位址、Tag、Index 與 Hit/Miss 如上表所示。
• Overall Miss Rate：$12 / 12 = 100\%$

---

(b) Cache 設計最佳化比較

總容量皆為 8 words：

• C1：1-word block $\Rightarrow$ 8 個 blocks，Index 為 3 bits（$\text{Word Address} \pmod 8$）。
• C2：2-word block $\Rightarrow$ 4 個 blocks，Index 為 2 bits（$\lfloor \text{Word Address} / 2 \rfloor \pmod 4$）。
• C3：4-word block $\Rightarrow$ 2 個 blocks，Index 為 1 bit（$\lfloor \text{Word Address} / 4 \rfloor \pmod 2$）。

對 12 次存取進行追蹤：

• C1：存取的 Index 依序為 3, 1, 3, 2, 1, 1, 5, 5, 2, 5, 1, 3。每次存取的 Tag 皆不相同且發生衝突取代，故全部 12 次皆 Miss（Miss Rate = $100\%$）。
• C2： Block Address ($\lfloor W/2 \rfloor$) 依序為 37, 16, 65, 9, 108, 12, 90, 10, 97, 126, 0, 5。Index (Block Address $\pmod 4$) 依序為 1, 0, 1, 1, 0, 0, 2, 2, 1, 2, 0, 1。每次皆未命中同一 Block，全部 12 次皆 Miss（Miss Rate = $100\%$）。
• C3： Block Address ($\lfloor W/4 \rfloor$) 依序為 18, 8, 32, 4, 54, 6, 45, 5, 48, 63, 0, 2。Index (Block Address $\pmod 2$) 依序為 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0。每次皆未命中同一 Block，全部 12 次皆 Miss（Miss Rate = $100\%$）。

I. Miss Rate 比較
三種設計的 Miss Rate 皆為 $100\%$（12/12），故三者表現相同。

II. 平均存取時間（AMAT）比較
公式：$\text{AMAT} = \text{Access Time} + \text{Miss Rate} \times \text{Miss Stall Time}$

• C1：$2 + 100\% \times 25 = 27 \text{ cycles}$
• C2：$3 + 100\% \times 25 = 28 \text{ cycles}$
• C3：$5 + 100\% \times 25 = 30 \text{ cycles}$

【答案】
I. 三者 Miss Rate 皆為 $100\%$（並列最佳）。
II. C1 最佳（平均存取時間最短，為 27 cycles）。

---

(c) 3-Way Set Associative Cache (2-word blocks, Total 24 words)

參數計算：

• 總 Block 數 $= 24 / 2 = 12$ blocks
• Set 數量 $= 12 / 3 = 4$ sets (Set 0 ~ Set 3)
• Block Offset：$\log_2(2) = 1$ bit
• Index：$\log_2(4) = 2$ bits
• Tag：$32 - 1 - 2 = 29$ bits

(a) 快取控制器狀態圖（State Diagram）

本設計採用標準四狀態（4-State）有限狀態機（FSM）實現 Direct-Mapped、Write-Back 搭配 Write-Allocate 之快取控制器。

控制訊號與狀態符號定義

• CPU 介面訊號：
  • $\text{Valid}_\text{cpu}$：處理器發送之請求有效訊號。
  • $\text{R/W}$：讀寫控制訊號（$0 = \text{Read}$, $1 = \text{Write}$）。
  • $\text{Ready}$：快取完成請求並回傳給處理器之通知訊號。
• 內部狀態訊號：
  • $V$：快取區塊有效位元（Valid bit）。
  • $D$：快取區塊髒位元（Dirty bit）。
  • $\text{Hit}$：Hit 判定訊號，$\text{Hit} = V \land (\text{CPU Tag} == \text{Cache Tag})$。
• 記憶體介面訊號：
  • $\text{MemRead} / \text{MemWrite}$：向主記憶體發出之讀寫請求訊號。
  • $\text{MemReady}$：主記憶體完成區塊傳輸之回應訊號。

stateDiagram-v2
    [*] --> Idle
    
    Idle --> CompareTag : Valid_cpu = 1
    Idle --> Idle : Valid_cpu = 0
    
    CompareTag --> Idle : Hit = 1 / Ready = 1
    CompareTag --> WriteBack : Hit = 0 and D = 1
    CompareTag --> Allocate : Hit = 0 and D = 0
    
    WriteBack --> Allocate : MemReady = 1
    WriteBack --> WriteBack : MemReady = 0
    
    Allocate --> CompareTag : MemReady = 1
    Allocate --> Allocate : MemReady = 0

---

(b) 各狀態功能與轉移細節說明

1. Idle（閒置狀態）

• 功能：等待處理器發出快取存取請求。
• 狀態轉移：
  • 若 $\text{Valid}_\text{cpu} = 0$：保持在 Idle 狀態。
  • 若 $\text{Valid}_\text{cpu} = 1$：轉移至 Compare Tag 狀態。