109 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《計算機系統（計算機組織）》

核心觀念

本題考查計算機效能評估的核心觀念——CPU 效能方程式（CPU Performance Equation），以及指令混合比例（Instruction Mix）對加權平均每指令週期數（Average Cycles Per Instruction, CPI）的計算影響。

主要使用的公式如下：

1. 加權平均 CPI（Average CPI）：
   當程式包含多種不同類型的指令時，整體平均 CPI 為各類別指令出現比例（Instruction Proportion, $P_i$）與其對應 CPI（$CPI_i$）的加權總和：
   $CPI_{avg} = \sum_{i} (P_i \times CPI_i)$
2. CPU 執行時間方程式（CPU Time Equation）：
   $CPU\_time = I \times CPI \times T_{clock} = \frac{I \times CPI}{f}$
   其中 $I$ 為動態指令數（Dynamic Instruction Count），$CPI$ 為平均每指令週期數，$T_{clock}$ 為時脈週期時間（Clock Cycle Time），$f$ 為時脈頻率（Clock Rate）。
3. 相對變化率推導：
   若指令數變更為 $I' = (1 + \Delta I) \cdot I$，CPI 變更為 $CPI' = (1 + \Delta CPI) \cdot CPI$，且時脈週期時間 $T_{clock}$ 保持不變，則新 CPU 執行時間為：
   $CPU\_time' = I' \times CPI' \times T_{clock} = (1 + \Delta I)(1 + \Delta CPI) \times CPU\_time$

---

解題方法

1. (a) 小題：利用動態指令混合比例分別計算處理器 P1 與 P2 的加權平均 CPI，再計算兩者之比值 $CPI_{P1} / CPI_{P2}$。
2. (b) 小題：利用已知條件（指令數 $I$、執行時間 $CPU\_time$、時脈週期時間 $T_{clock}$）帶入 CPU 效能方程式逆推 CPI。題目給定的參考時間（Reference Time）為計算 SPECratio 所用，與求算 CPI 無關。
3. (c) 小題：利用積的相對變化計算新舊 CPU 執行時間的比值關係，導出 CPU 執行時間的增加百分比與絕對時間增加量。

---

各小題詳細解析

(a) 小題解析

• 給定條件：

  • 指令混合比例：Class A 為 $10\%$、Class B 為 $20\%$、Class C 為 $50\%$、Class D 為 $20\%$。
  • P1 的各類指令 CPI 分別為：$CPI_{A}=1$, $CPI_{B}=2$, $CPI_{C}=3$, $CPI_{D}=3$。
  • P2 的各類指令 CPI 分別為：$CPI_{A}=2$, $CPI_{B}=2$, $CPI_{C}=2$, $CPI_{D}=2$。

• 推導與計算：

  1. 計算 P1 的平均 CPI ($CPI_{P1}$)：
     $CPI_{P1} = (10\% \times 1) + (20\% \times 2) + (50\% \times 3) + (20\% \times 3)$
     $CPI_{P1} = 0.10 + 0.40 + 1.50 + 0.60 = 2.6$

  2. 計算 P2 的平均 CPI ($CPI_{P2}$)：
     $CPI_{P2} = (10\% \times 2) + (20\% \times 2) + (50\% \times 2) + (20\% \times 2) = 2.0$

  3. 計算 P1 與 P2 的 CPI 比值 ($CPI_{P1} / CPI_{P2}$)：
     $\text{Ratio} = \frac{CPI_{P1}}{CPI_{P2}} = \frac{2.6}{2.0} = 1.3$

---

(b) 小題解析

• 給定條件：
  • 動態指令數 $I = 2.5 \times 10^{12}$
  • 執行時間 $CPU\_time = 900\text{ s}$

核心觀念

本題涵蓋計算機系統底層數值表示法與運算機制的三大重點：

1. 8 位元二補數（Two's Complement）表示法與溢位處理：
   • 在 8 位元二補數格式中，最高位（MSB）為符號位（$0$ 代表正數或零，$1$ 代表負數），數值表示範圍為 $[-2^7, 2^7 - 1] = [-128, 127]$。
   • 若以無號十進位數值 $X \in [128, 255]$ 表示一個 8 位元二補數的暫存器內容，其對應的實際帶號值為 $X - 256$。
   • 典型硬體加法器採用模數加法（Modulo $2^8 = 256$ Arithmetic），運算產生之溢出進位（Carry out）在固定寬度下會被截斷（Truncated）。
2. 飽和運算（Saturating Arithmetic）：
   • 常見於多媒體與數位訊號處理（DSP / SIMD 指令集，如 MMX、SSE、NEON）。
   • 運算結果若超出該資料型態所能表示的最大值或最小值時，不會發生繞回（Wrap-around），而是直接截斷並「飽和」至可表示的極端值。
   • 8 位元無號整數（Unsigned 8-bit Integer）之表示範圍為 $[0, 2^8 - 1] = [0, 255]$，飽和上限為 $255$。
3. IEEE 754 單精準度（Single-Precision）浮點數標準：
   • 總長度為 32 位元，欄位分配為：
     • 符號位元（Sign, $S$）：$1\text{ bit}$（$S=0$ 為正，$S=1$ 為負）。
     • 指數欄位（Exponent, $E$）：$8\text{ bits}$，偏差值（Bias）為 $127$。實際指數為 $e = E - 127$。
     • 小數欄位（Fraction / Mantissa, $F$）：$23\text{ bits}$，正規化（Normalized）數值的有效數（Significand）為 $1.F$。
   • 正規化浮點數之真值公式為：
     $V = (-1)^S \times (1 + F) \times 2^{E - 127}$

---

解題方法與推導

(a) 8-bit 二補數帶號整數加法

1. 解讀暫存器內儲存的數值與二進位樣式：
   • 題目給定以 8 位元儲存之十進位編碼數值：
     • 第一個運算元：$151_{10} = 10010111_2$
       • 帶號解讀：符號位為 $1$（負數），實際值為 $151 - 256 = -105$。
     • 第二個運算元：$214_{10} = 11010110_2$
       • 帶號解讀：符號位為 $1$（負數），實際值為 $214 - 256 = -42$。
2. 進行 8 位元二進位加法：
   $10010111_2 + 11010110_2 = (1)01101101_2$
   • 最前端產生的進位 $1$ 超出 8 位元範圍，硬體自動捨棄（Truncated），保留低 8 位元：$01101101_2$。
3. 將結果轉換為十進位：
   • 結果 $01101101_2$ 的最高位（MSB）為 $0$（正數），其十進位真值為：
     $0 \times 2^7 + 1 \times 2^6 + 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 64 + 32 + 8 + 4 + 1 = 109$
     (註：若題幹敘述中前句假設之 $152$ 與 $213$ 參與計算，因 $152 + 213 = 365 \equiv 109 \pmod{256}$，二進位加法截斷後結果亦同為 $01101101_2 = 109$)。

---

(b) 8-bit 無號整數飽和運算（Saturating Arithmetic）

1. 無號數運算範圍：
   • 8 位元無號整數的數值範圍為 $[0, 255]$。
2. 計算算術總和：
   $151 + 214 = 365$
3. 套用飽和機制：

(a) Block size (words)
Offset 欄位有 6 位 ⇒ 每塊位元組數 = $2^{6}=64\;\text{bytes}$。
1 word = 4 bytes ⇒ block size = $\frac{64}{4}=16\;\text{words}$。

(b) Cache 條目數目
Index 欄位有 8 位 ⇒ 條目數 = $2^{8}=256\;$。

(c) 總位元數 (Kibits)

• Tag 位元 = 18 位
• Valid 位元 = 1 位
• Data 位元 = block size $=64\;\text{bytes}=64\times8=512\;$ 位

單一條目位元 = $18+1+512=531\;$ 位。
全部位元 = $531 \times 256 = 135\,936\;$ 位。

$\frac{135\,936}{1024}=132.75\;\text{Kibits}\approx 133\;\text{Kibits}$

(a) Direct‑mapped、2 word / 8 blocks

參考位址	Block #	Index (mod 8)	Tag	命中/未命中
3	1	1	0	未命中
180	90	2	11	未命中
43	21	5	2	未命中
2	1	1	0	命中
191	95	7	11	未命中
88	44	4	5	未命中
190	95	7	11	命中
14	7	7	0	未命中
181	90	2	11	命中
44	22	6	2	未命中

未命中次數 = 7，參考次數 = 10

$\text{Miss Rate}= \frac{7}{10}=0.70\;(70\%)$

(b) 總週期數

每個存取的基礎存取時間＝3 cycles，未命中額外延遲＝25 cycles

$\text{Total cycles}=10\times3 + 7\times25 = 30 + 175 = 205\;\text{cycles}$

(c) 三路組合集（2 word / 24 words）

核心觀念

本題考驗計算機系統與作業系統中**虛擬記憶體（Virtual Memory）之分頁機制（Paging System）**的基礎計算與頁表結構特性。核心概念包含：

1. 虛擬位址分割（Virtual Address Partitioning）：
   $32$ 位元的虛擬位址（Virtual Address, VA）在分頁架構下會被劃分為兩部分：

   • 虛擬頁號（Virtual Page Number, VPN）：用於索引分頁表（Page Table）。
   • 頁內位移（Page Offset, PO）：決定頁面內的具體位址，其位元數由**分頁大小（Page Size）**決定。
     $\text{Virtual Address Size} = \text{VPN bits} + \text{Page Offset bits}$

2. 單階分頁表（Single-Level Page Table）之連續陣列特性：
   單階分頁表本質上是一個以 VPN 作為陣列索引（Index）的直接尋址表格。為了使硬體記憶體管理單元（MMU）能夠以 $O(1)$ 時間進行位址轉換，單階頁表必須為虛擬位址空間中的每一個潛在頁面都預留一個分頁表項目（Page Table Entry, PTE），不論該頁面實際上是否被程式分配或使用（未使用的頁面標記為 Invalid）。

3. 行程獨立性（Per-Process Address Space）：
   作業系統中每個獨立運行的應用程式（Application / Process）都擁有自己獨立的虛擬位址空間與專屬的分頁表，以達到行程間記憶體隔離與保護的目的。

---

解題方法

子題 (a) 推導步驟

需求：計算單一單階分頁表佔用的實體記憶體大小。

1. 計算頁內位移（Page Offset）位元數：
   題目給定分頁大小為 $8\text{ KiB}$。
   $8\text{ KiB} = 8 \times 1024\text{ bytes} = 2^3 \times 2^{10}\text{ bytes} = 2^{13}\text{ bytes}$
   因此，頁內位移需要 $13\text{ bits}$。

2. 計算虛擬頁號（VPN）位元數：
   虛擬位址長度為 $32\text{ bits}$。
   $\text{VPN bits} = 32 - 13 = 19\text{ bits}$

3. 計算分頁表項目總數（Total PTEs）：
   $19\text{ bits}$ 的 VPN 代表虛擬位址空間最多可劃分為 $2^{19}$ 個頁面。單階分頁表必須包含 $2^{19}$ 個 PTE。
   $\text{Total PTEs} = 2^{19} = 524,288\text{ 個}$

4. 計算分頁表記憶體容量：
   每個 PTE 大小為 $4\text{ bytes}$。
   $\text{Single Page Table Size} = 2^{19} \times 4\text{ bytes} = 2^{19} \times 2^2\text{ bytes} = 2^{21}\text{ bytes} = 2\text{ MiB}$

---

子題 (b) 推導步驟

需求：計算系統同時執行 6 個應用程式，且每個應用程式僅使用一半虛擬位址空間時，全系統總分頁表大小。

1. 分析單一應用程式的分頁表大小：
   單階分頁表採用靜態陣列結構，MMU 透過 $\text{Base Address} + \text{VPN} \times \text{PTE Size}$ 直接尋址。

核心觀念

本題旨在考驗考生對 MIPS 組合語言翻譯、暫存器呼叫約定（Register Calling Convention）、Stack 堆疊空間管理 以及 多重陣列索引定址計算 的理解。

1. 暫存器呼叫約定（Calling Convention）：

   • Callee-saved Registers（$s0–$s7）：被呼叫函式（Callee）若欲寫入或修改這些暫存器，必須在進入函式時（Prologue）先將其舊值壓入堆疊（Stack）備份，並在離開函式前（Epilogue）將其還原，以確保呼叫者（Caller）的資料不受破壞。
   • Caller-saved / Temporary Registers（$t0–$t9）：暫存用暫存器，被呼叫函式可自由使用與覆寫，無須在 Stack 中保留其值。
   • Return Value Register（$v0）：依據 MIPS ABI 規範，函式回傳值應置於 $v0（或包含 $v1）。
   • Return Address Register（$ra）：儲存返回呼叫者的位址。本題函式為葉函式（Leaf Function），未再呼叫其他子函式，因此 $ra 不會被覆蓋，無須備份至 Stack。

2. 記憶體定址與陣列索引（Array Indexing & Address Calculation）：

   • C 語言中 int 資料型態占 4 個位元組（4 bytes / 32-bit word）。
   • 記憶體位址以 Byte 為單位定址，故陣列索引 $k$ 對應之位元組偏移量（Byte Offset）為 $k \times 4$。
   • 在 MIPS 中，乘以 4 可直接透過邏輯左移指令 sll rd, rs, 2（移位 2 位元，$2^2 = 4$）以更高的效能達成。
   • 陣列 $B[g]$ 之記憶體位址公式：
     $\text{Address of } B[g] = \text{Base Address of } B + (g \times 4)$
   • 巢狀陣列 $A[B[g] + 1]$ 之記憶體位址公式：
     $\text{Address of } A[B[g] + 1] = \text{Base Address of } A + \left((B[g] + 1) \times 4\right)$

---

解題方法

將 C 語言程式碼拆解為五個主要步驟進行推導：

步驟一：處理 Stack Pointer 與暫存器備份（Prologue）

題目指定變數 $f$ 分配於暫存器 $s0。由於 $s0 屬於 Callee-saved 暫存器，且在本函式中將會進行指派寫入（$f = \dots$），因此必須在 Stack 上配置 4 位元組空間，並將舊的 $s0 值備份：

addi $sp, $sp, -4    # 將 Stack Pointer 向低位址移動 4 bytes
sw   $s0, 0($sp)     # 將呼叫者的舊 $s0 值寫入 0($sp) 保留

步驟二：計算並載入 $B[g]$

• 變數 $g$ 位於 $s1$，陣列 $B$ 的基底位址位於 $s7$。
• 計算 $g \times 4$ 取得偏移量：sll $t0, $s1, 2
• 計算 $B[g]$ 的記憶體位址：add $t0, $s7, $t0
• 從記憶體取出 $B[g]$ 的值：lw $t0, 0($t0)

步驟三：計算索引 $B[g] + 1$ 並載入 $A[B[g] + 1]$

• 將取得的 $B[g]$ 值加 1 得到新索引：addi $t0, $t0, 1
• 計算 $(B[g] + 1) \times 4$ 取得陣列 $A$ 的位元組偏移量：sll $t0, $t0, 2
• 計算 $A[B[g] + 1]$ 的記憶體位址（陣列 $A$ 的基底位址位於 $s6$）：add $t0, $s6, $t0
• 從記憶體取出 $A[B[g] + 1]$ 的值：lw $t1, 0($t0)

步驟四：執行算術運算與結果賦值

• 計算 $(A[B[g] + 1] + h)$，其中 $h$ 位於 $s2$：add $t1, $t1, $s2
• 計算 $(i + j)$，其中 $i, j$ 分別位於 $s3, $s4$：add $t2, $s3, $s4
• 執行減法並將結果存回 $f$（即 $s0$）：sub $s0, $t1, $t2
• 將回傳值寫入回傳暫存器 $v0$：move $v0, $s0

步驟五：還原 Stack 與返回（Epilogue）

在函式結束離開前，還原原本的 $s0 並歸還 Stack 空間，最後跳轉回 Caller：

lw   $s0, 0($sp)     # 還原舊的 $s0 值
addi $sp, $sp, 4     # 釋放 Stack 4 bytes 空間
jr   $ra             # 返回呼叫者

---

暫存器與 Stack 保存策略分析

為了完整驗證編譯邏輯，針對各暫存器於本題中是否需要壓入 Stack 保存進行逐一分析：

• $s0（變數 $f$）：需保存。`

核心觀念

本題主要測驗 MIPS 組合語言的控制流程（Control Flow）、指令執行計數（Instruction Count）以及組合語言與 C 語言的結構轉換：

1. 比較與條件分支指令：
   • slt rd, rs, rt（Set on Less Than）：若 $\text{rs} < \text{rt}$ 則 $\text{rd} = 1$，否則 $\text{rd} = 0$。
   • beq rs, rt, label（Branch on Equal）：若 $\text{rs} == \text{rt}$ 則跳躍至指定標籤。
2. 基本迴圈結構：
   • 迴圈體（Loop Body）包含條件測試（Test）、迴圈本體運算（Loop Payload）與無條件跳躍（j LOOP）。
   • 計算指令執行總數時，必須區分「進入迴圈成功執行的次數」與「最後一次條件不成立跳出迴圈所消耗的指令數」。

---

解題方法與詳細推導

組合語言邏輯分析

分析 LOOP 內部的指令行為：

• slt $t2, $0, $t1：檢查 $$0 <$$$t1$（即 $$t1 > 0$ 是否成立）。若成立則 $$t2 = 1$，否則 $$t2 = 0$。
• beq $t2, $0, DONE：若 $$t2 == 0$（即 $$t1 \le 0$），條件不滿足，跳出迴圈至 DONE。
• subi $t1, $t1, 1：$$t1 =$$$t1 - 1$（遞減計數器）。
• addi $s2, $s2, 2：$$s2 =$$$s2 + 2$（累加變數）。
• j LOOP：無條件跳回迴圈開頭繼續執行。

---

(a) 求暫存器 $s2 最終的值

1. 初始狀態：

   • $$t1 = 10$
   • $$s2 = 0$

2. 迴圈執行過程：

   • 第 1 次迭代：$$t1 = 10 > 0 \implies$$$t1$ 變為 $9$，$$s2$ 變為 $0 + 2 = 2$
   • 第 2 次迭代：$$t1 = 9 > 0 \implies$$$t1$ 變為 $8$，$$s2$ 變為 $2 + 2 = 4$
   • $\dots$
   • 第 10 次迭代：$$t1 = 1 > 0 \implies$$$t1$ 變為 $0$，$$s2$ 變為 $18 + 2 = 20$
   • 第 11 次測試：$$t1 = 0$，slt 設定 $$t2 = 0$，beq 成立直接跳至 DONE。

3. 結論：
   迴圈共完整執行 10 次，暫存器 `

(a)
5 階段 $\text{IF}=200\text{ps},\ \text{ID}=120\text{ps},\ \text{EX}=150\text{ps},\ \text{MEM}=190\text{ps},\ \text{WB}=100\text{ps}$。
時鐘週期取最長階段，即 $T_{\text{clk}}=200\text{ps}$。

因為唯一記憶體同時服務 IF 與 MEM，若有指令在 MEM 時另一指令正於 IF，必須讓 IF 停止。
在本序列中

• 第 1 條 sw 在第 4 週期使用 MEM，第 4 週期的 IF 會衝突 → 必須插入 1 個泡沫。
• 第 2 條 lw 在第 5 週期使用 MEM，第 5 週期的 IF 也衝突 → 再插入 1 個泡沫。

加入兩個結構性停頓後的週期表 (省略暫停週期的空格) 為 11 週期：

$$\text{Cycles}=11\qquad \text{Total time}=11\times200\text{ps}=2200\text{ps}$$

可以在每條 load/store 後插入一條 nop，使其在 MEM 週期時後面的指令不會同時取指，等效於上述兩個泡沫。因此 可以 用 nop 消除結構性危險，但仍會多耗兩個週期。

【答案】 總執行時間 2200 ps；結構危險可透過在每個 memory 指令後插入 nop 解除，仍需兩個額外週期。

---

(b)
ISA 改為 load/store 只需寄存器位址，故不使用 EX，MEM 與 EX 合併成一個階段，流水線變為 4 階段 $\text{IF},\text{ID},\text{MEM/EX},\text{WB}$。
改寫程式碼（去除位移）：

sw   r16, r6
lw   r16, r16
beq  r5, r4, Label
add  r5, r1, r4
slt  r5, r15, r4

在 4 階段流水線中理想週期為 $N+3 = 8$。
仍有相同的結構危險 (在 MEM/EX 週期與 IF 同時使用記憶體)，每條 memory 指令仍需插入 1 個停頓 → 再加 2 個泡沫，總週期 10。

時鐘週期仍為 200 ps（最長仍是 IF），故

$T_{\text{new}} = 10\times200\text{ps}=2000\text{ps}$

$\text{Speedup}= \frac{2200}{2000}=1.10$

【答案】 重新編寫如上，執行時間 2000 ps，速度提升 10 %。

---

核心觀念

本題考查多處理器系統（Multiprocessor Systems）效能評估的兩大核心指標：

1. 阿姆達爾定律（Amdahl's Law）與平行化瓶頸：

   • 用於評估改善系統某一部分（如增加處理器數量）對整體系統所能帶來的極限加速比（Speedup）。
   • 阿姆達爾定律公式：
     $S = \frac{1}{s + \frac{1 - s}{N}}$
     其中 $S$ 為整體加速比、$N$ 為處理器數量、$s$ 為無法平行化的串行運算比例（Sequential Fraction）、$1 - s$ 為可完全平行化的運算比例。

2. 遠端記憶體存取開銷（Remote Access Overhead）對平均 CPI 的影響：

   • 在多處理器系統（如 NUMA 架構）中，存取遠端處理器記憶體會產生額外的通訊延遲。
   • 考量遠端存取停頓（Stall）時的有效每指令週期數（Effective CPI）：
     $\text{CPI}_{\text{effective}} = \text{Base CPI} + \text{Stall CPI}$
     $\text{Stall CPI} = \text{遠端存取發生率} \times \text{每次遠端存取停頓週期數}$
   • 每次遠端存取的停頓週期數計算方式：
     $\text{Stall Cycles} = \frac{\text{遠端存取時間}}{\text{時脈週期}}$

---

解題方法

(a) 小題：

1. 已知處理器數量 $N = 100$、目標加速比 $S = 80$。
2. 代入阿姆達爾定律公式 $S = \frac{1}{s + \frac{1 - s}{N}}$。
3. 透過代數移項求出串行比例 $s$。

(b) 小題：

1. 計算單次遠端存取的處理器停頓週期數（Stall Cycles）：
   $\text{Stall Cycles} = \frac{200\text{ ns}}{0.3\text{ ns}} = \frac{2000}{3} \text{ 週期}$
2. 計算有 0.2% 遠端存取時的實際 CPI（$\text{CPI}_{\text{remote}}$）：
   $\text{CPI}_{\text{remote}} = \text{Base CPI} + (0.2\% \times \text{Stall Cycles})$
3. 完全無遠端存取的理想 CPI 即為 Base CPI（$\text{CPI}_{\text{no remote}} = 0.5$）。
4. 求無遠端存取相較於有遠端存取時的加速倍數：
   $\text{Speedup} = \frac{\text{CPI}_{\text{remote}}}{\text{CPI}_{\text{no remote}}}$

---

題目解析與推導

(a) 求解串行比例 $s$

將 $N = 100$ 與 $S = 80$ 代入阿姆達爾定律：
$80 = \frac{1}{s + \frac{1 - s}{100}}$

兩邊同乘以分母：
$80 \times \left( s + \frac{1 - s}{100} \right) = 1$

通分簡化：
$80 \times \left( \frac{100s + 1 - s}{100} \right) = 1$
$0.8 \times (99s + 1) = 1$
$99s + 1 = \frac{1}{0.8} = 1.25$
$99s = 0.25$

求得串行比例 $s$：
$s = \frac{0.25}{99} = \frac{1}{396} \approx 0.002525 \quad (0.2525\%)$

---

(b) 求解遠端存取對效能的影響

1. 計算每次遠端存取之停頓週期數：
   • 時脈週期（Clock Period）$= 0.3\text{ ns}$
   • 遠端存取延遲（Remote Access Time）$= 200\text{ ns}$