111 年 國立成功大學電機工程學系碩士班戊組《計算機組織》

核心觀念

本題旨在考驗《計算機組織與結構》中**程式執行效能（Program Execution Performance）**的基本衡量指標、名詞定義與相對效能（Relative Performance）推導計算。相關核心定義與公式如下：

1. CPI 與 IPC 之定義與倒數關係

   • CPI（Cycles Per Instruction）：執行每條指令平均所需的時脈週期數。
   • IPC（Instructions Per Cycle）：每個時脈週期平均可執行的指令數。
   • 兩者互為倒數關係：
     $\text{IPC} = \frac{1}{\text{CPI}}$

2. CPU 時間（CPU Time）與回應時間（Elapsed Time）的區別

   • CPU Time（CPU 執行時間）：僅包含 CPU 專門用於處理該特定任務的時間（可進一步細分為 User CPU Time 與 System CPU Time），不包含 CPU 等待 I/O 或是執行多工排程中其他程式的時間。
   • Elapsed Time（回應時間 / 牆上鐘錶時間）：執行該程式所花費的總時間，包含 CPU 執行時間、I/O 等待時間、作業系統排程開銷以及其他程式佔用 CPU 的時間。

3. 相對效能（Relative Performance / Speedup）公式

   • 效能（Performance）定義為執行時間（Execution Time）的倒數：
     $\text{Performance} = \frac{1}{\text{Execution Time}}$
   • 若稱「電腦 B 比電腦 A 快 $X$ 倍（Computer B is $X$ times faster than Computer A）」，其倍數計算為：
     $X = \frac{\text{Performance}_B}{\text{Performance}_A} = \frac{\text{Execution Time}_A}{\text{Execution Time}_B}$

---

解題方法

本題切入點為逐一審視各選項對於效能名詞定義與效能計算公式的正確性：

1. 檢查 (a) 與 (b) 的英文縮寫全稱與物理意義。
2. 根據系統效能理論，分辨 (c) 描述的時間範疇屬於 CPU Time 還是 Elapsed Time。
3. 利用相對效能公式，導出 (d) 中兩台電腦的執行時間比與效能倍數，驗證其數值是否吻合。

---

選項分析

• (a) 錯誤
  CPI 的英文全稱應為 Cycles Per Instruction（每條指令平均所需的週期數），而非 "Clock Period/Instruction"。

核心觀念

本題考查 C 語言算式轉換為 RISC-V 指令時的：

1. 運算順序與括號結構。
2. 暫存器配置。
3. 暫存器算術指令 add 的使用。
4. 計算結果寫回變數 f。

原始算式為：

$$f=a+(b+(c+d))$$

括號決定由內向外計算：

$$t_1=c+d$$ $$t_2=b+t_1$$ $$f=a+t_2$$

因此共需要三次加法。

解題假設

採用 RV32I RISC-V 指令集，並作以下暫存器配置：

C 變數	RISC-V 暫存器
a	x10（a0）
b	x11（a1）
c	x12（a2）
d	x13（a3）
f	x14（a4）
暫存結果	x5、x6

假設 a、b、c、d 的值已經載入暫存器，且變數型態為 32 位元整數。若變數位於記憶體，需先使用 lw 載入，最後再用 sw 儲存。

解題方法與指令

add x5, x12, x13    # x5 = c + d，先計算最內層括號
add x6, x11, x5     # x6 = b + (c + d)，計算中間層括號
add x14, x10, x6    # x14 = a + (b + (c + d))，計算最外層加法並存入 f

對應關係如下：

$$x5 \leftarrow x12+x13=c+d$$ $$x6 \leftarrow x11+x5=b+(c+d)$$ $$x14 \leftarrow x10+x6=a+(b+(c+d))$$

所以最後：

$$f=x14$$

若按照 ABI 的暫存器名稱表示，同一段程式可寫成：

add t0, a2, a3      # t0 = c + d
add t1, a1, t0      # t1 = b + (c + d)
add a4, a0, t1      # a4 = a + (b + (c + d))，a4 對應 f

若變數位於記憶體

若 a、b、c、d、f 是記憶體中的全域變數，可採用下列假設：

解說

• Saved registers（callee‑saved）：呼叫規則要求子程式在返回前必須還原，因而在呼叫期間保持不變。
• Temporary registers（caller‑saved）：呼叫者在呼叫前若需保留值，必須自行存於堆疊；子程式不負責保存。故在呼叫期間不保證不變。

核心觀念

本題考查 IEEE 754 浮點數標準（IEEE 754 Standard Floating-Point Representation） 的基本結構與編碼規範，涵蓋以下核心觀念：

1. 欄位組成：IEEE 754 浮點數資料格式由三個基本欄位組成：

   • 正負號位元（Sign bit, $S$）：佔 $1$ 位元，$0$ 表示正數，$1$ 表示負數。
   • 階碼／指數欄位（Exponent, $E$）：決定數值的動態範圍（Dynamic Range）與數量級大小。
   • 尾數／小數欄位（Fraction / Mantissa, $F$）：決定數值的有效位數與精度。

2. 數值編碼方式：

   • 指數部分（Exponent）：採用 偏壓表示法（Biased Representation / Excess-$K$ Representation），單精度（Single Precision）偏壓為 $\text{Bias} = 127$；雙精度（Double Precision）偏壓為 $\text{Bias} = 1023$。不採用二補數（2's complement）。
   • 尾數部分（Fraction）：採用 原碼／正負號與絕對值表示法（Sign-Magnitude），配合規格化數值前隱含的前導 $1$（Implicit Leading 1，即 $1.F$）。不採用二補數（2's complement）。

3. 特殊值編碼與非規格化數：

   • 無窮大（Infinity, $\pm\infty$）：$E = E_{\max}$ 且 $F = 0$。
   • 非數值（Not a Number, NaN）：$E = E_{\max}$ 且 $F \neq 0$。
   • 非規格化數（Denormalized / Subnormal Numbers）：當 $E = 0$ 且 $F \neq 0$ 時，代表極接近 $0$ 的微小數值（形如 $0.F \times 2^{1-\text{Bias}}$）。此機制解決了浮點數下溢（Underflow）時數值突降至 $0$ 的問題，實現了漸進下溢（Gradual Underflow）。

4. 相對精度與絕對精度：

   • 絕對精度（Absolute Precision）：相鄰兩浮點數之間的間距（Unit in the Last Place, ULP），大小為 $2^{E - \text{Bias} - p}$（$p$ 為尾數位數），隨指數 $E$ 改變。
   • 相對精度（Relative Precision）：定義為 $\frac{\Delta X}{X} \approx 2^{-p}$（$p$ 為尾數位數），由尾數欄位（Fraction）長度決定，在規格化數的範圍內維持恆定，與指數 $E$ 無關。

---

解題方法

本題為概念分析型多重選擇題，解題切入點如下：

1. 檢視浮點數的資料結構，確認其是否由 Sign、Exponent、Fraction 三個欄位組成。
2. 釐清指數與尾數的實際編碼格式，劃清偏壓表示法、原碼與二補數（2's complement）的界線。
3. 確認 IEEE 754 對於特殊值（$\pm\infty$, NaN）以及非規格化數（Denormalized numbers）的支援度與編碼規範。
4. 區分浮點數的「絕對精度」與「相對精度」，分析影響相對精度的關鍵變數（尾數長度 vs. 指數）。

---

選項分析

• (a) 敘述正確。
  • 說明：IEEE 754 浮點數表達式由三個部分組成：正負號（Sign, $S$）、指數（Exponent, $E$）與尾數（Fraction / Mantissa, $F$）。單精度（32-bit）配置為 $1+8+23$ 位元，雙精度（64-bit）配置為 $1+11+52$ 位元。因此本選項完全正確。

核心觀念

本題考查**流水線（Pipelining）**的基本原理、效能指標及其限制因素。核心定理與定義如下：

1. 吞吐量（Throughput）與延遲（Latency）：
   • 指令延遲（Latency）：單一指令從開始執行到結束所花費的時間。流水線加入流水線暫存器與時脈同步開銷（Overhead），因此單一指令的延遲並不會減少，甚至可能微幅增加。
   • 吞吐量（Throughput）：單位時間內所完成的指令數量（如每週期完成指令數 $\text{IPC}$）。流水線透過重疊（Overlap）執行多筆指令來大幅提升整體吞吐量。
2. 加速比（Speedup）與氣泡（Bubble）：
   • 理想 $N$ 階段（$N$-stage）單發射（Single-issue）流水線的加速比上限為 $N$ 倍：
     $\text{Speedup} = \frac{\text{CPI}_{\text{non-pipelined}} \times \text{Clock Cycle Time}_{\text{non-pipelined}}}{\text{CPI}_{\text{pipelined}} \times \text{Clock Cycle Time}_{\text{pipelined}}} \approx N$
   • 流水線氣泡（Pipeline Bubble / Stall）：由資料冒險（Data Hazard）、控制冒險（Control Hazard）或結構冒險（Structural Hazard）導致的停頓，會使平均每指令週期數增加（$\text{CPI} > 1$），進而降低整體加速比。
3. 時脈週期（Clock Cycle Time）限制：
   • 流水線的時脈週期長度必須能容納最耗時的階段，因此由**最慢的階段（Slowest Stage）**延遲加上暫存器開銷決定：
     $\text{Clock Cycle Time} \ge \max(\text{Stage Delay}) + \text{Register Overhead}$

---

解題方法

針對題目問及何者為真（TRUE），我們應根據流水線的「延遲 vs. 吞吐量」、「時脈週期與最慢階段」、「理想 IPC」以及「Hazard／Bubble 的影響」切入，逐一檢驗四個選項之陳述是否符合電腦架構基本定理。

---

選項分析

• (a) 錯誤
  • 原文：Pipeline can speed up overall performance due to latency of each instruction is improved
  • 解析：流水線技術提升的是系統整體的吞吐量（Throughput），而非單一指令的延遲（Latency）。

核心觀念

本題考驗快取記憶體架構（Cache Architecture）的核心設計參數——快取容量 (Cache Size)、相聯度 (Associativity) 與 區塊大小 (Block Size) 對快取失誤率 (Miss Rate) 的定性影響，以及 Hill 的 3Cs 失誤模型 (3Cs Miss Model)：

1. 強制失誤 (Compulsory Miss)：資料第一次被存取時發生的失誤。增加 Block Size 利用空間局部性可減少此類失誤。
2. 容量失誤 (Capacity Miss)：當程式執行過程中所需要的資料總量超過 Cache 容量時產生的失誤。增加 Cache Size 可直接降低 Capacity Miss。
3. 衝突失誤 (Conflict Miss)：多個資料區塊映射到同一 Set（組）所產生的競爭失誤。增加 Associativity 可減輕組內的競爭壓力，從而降低 Conflict Miss（在 Fully Associative 快取中，Conflict Miss 為 $0$）。
4. Block Size 與 Miss Rate 的關係（固定 Cache Size 下）：
   • 適度增加 Block Size：能利用空間局部性 (Spatial Locality) 預取相鄰資料，降低失誤率。
   • 過大 (Very Large) 的 Block Size：使快取內的區塊總數急遽減少，未被存取的資料佔用空間（快取污染），且有限的區塊數量導致衝突與容量擠壓加劇，失誤率反而上升。失誤率與 Block Size 的關係呈經典的 U 型曲線。

---

解題方法

根據 3Cs 失誤模型與快取參數的定性關係，分別分析 Cache Size、Associativity 以及 Block Size 對失誤率的作用機制。針對固定 Cache Size 下 Block Size 變動的二階段影響（空間局部性收益 vs. 區塊數量不足懲罰）進行邏輯研判，評估各選項之正確性。

---

選項分析

• (a) Increase cache size may decrease capacity misses.【正確】

  • 說明：容量失誤（Capacity Miss）定義為快取空間不足以容納程式工作集（Working Set）而產生的失誤。當增加快取容量 (Cache Size) 時，快取能同時保存更多資料區塊，從而直接減少因容量限制造成的替換與失誤。因此，增大 Cache Size 可降低 Capacity Miss。

• (b) Increase associativity may increase miss rate due to conflict misses.【錯誤】

  • 說明：衝突失誤（Conflict Miss）是由於多個 Block 競爭同一個 Set 所致。

核心觀念

Pipeline hazard（管線危障）是指多條指令重疊執行時，因為硬體資源、資料相依性或控制流程的不確定性，使下一個時脈週期無法安全地讓指令繼續前進。

計算機組織中，管線危障分為三大類：

1. Structural hazard（結構危障）
2. Data hazard（資料危障）
3. Control hazard（控制危障）

---

解題方法

題目要求寫出三種管線危障的名稱與成因，因此依照「硬體資源、資料相依、控制流程」三個角度逐一判斷即可。

1. Structural hazard（結構危障）

成因

當同一個時脈週期中，有兩條以上的指令需要使用同一項硬體資源，但該資源不足以同時服務所有指令，就會發生結構危障。

例如，處理器只有一個共享記憶體，而某個時脈週期同時發生：

• 一條指令要進行 instruction fetch；
• 另一條指令要進行 data access。

兩者同時需要存取同一個記憶體，因此產生資源衝突。

例子

若管線階段為：

$$IF \rightarrow ID \rightarrow EX \rightarrow MEM \rightarrow WB$$

當一條指令位於 MEM 階段讀取資料記憶體時，另一條指令可能同時位於 IF 階段讀取指令。若指令與資料共用單一記憶體，便會發生衝突。

常見處理方式

• 增加硬體資源；
• 使用分離的 instruction memory 與 data memory；
• 暫停管線，插入 stall 或 bubble。

---

2. Data hazard（資料危障）

成因

當後續指令需要使用前一條或前幾條指令所產生的資料，但該資料尚未完成產生或寫回，就會發生資料危障。

例如：

ADD R1, R2, R3
SUB R4, R1, R5

第二條 SUB 需要讀取 R1，但 R1 是第一條 ADD 的計算結果。若 SUB 讀取時，ADD 尚未將結果寫回，就會產生資料相依衝突。

資料危障常依相依方向分為：

• RAW（Read After Write）：寫入後讀取
  後指令要讀取前指令尚未寫入完成的資料，稱為真正資料相依，也是一般順序管線最常見的資料危障。

• WAR（Write After Read）：讀取後寫入
  後指令過早寫入某個暫存器，可能破壞前指令尚未讀取的資料，常見於亂序執行。

• WAW（Write After Write）：寫入後再寫入
  兩條指令寫入相同目的地，若後指令先完成，可能造成錯誤的寫回順序，也常見於亂序執行。

核心觀念

1. 動態分支預測（Dynamic Branch Prediction）
   在 CPU 執行期（Runtime）根據分支指令過去的執行紀錄，動態預測當前分支是否發生（Taken, T）或未發生（Not Taken, NT），藉此降低管線化（Pipelining）中的控制雜訊（Control Hazard / Branch Penalty）。

2. 1-bit 分支預測機制（1-bit Prediction Scheme / 1-bit Branch History Table）
   每個分支指令在分支預測表中僅使用 1 個位元記錄最近一次的執行結果：

   • 位元值 $1$（Taken）：預測下一次分支會發生。
   • 位元值 $0$（Not Taken）：預測下一次分支不會發生。
   • 狀態轉移規則：只要當前實際執行結果與預測不符，該位元便會立即翻轉（Flip）。

3. 雙重迴圈（Nested Loop）的分支行為特徵

   • 迴圈分支在連續重複執行時，前 $N-1$ 次實際結果皆為 Taken（跳回迴圈開頭），第 $N$ 次（迴圈結束）實際結果為 Not Taken（跳出迴圈）。
   • 1-bit 預測器缺乏「記憶滯後（Hysteresis）」能力，在面對迴圈結構時會產生固定的預測錯誤模式。

---

解題方法

本題給定一個包含內層迴圈與外層迴圈的雙重迴圈程式結構。我們將兩條分支指令分別標記如下：

• 內層分支 $B_{\text{inner}}$：beq ..., ..., inner（控制內層迴圈是否繼續）
• 外層分支 $B_{\text{outer}}$：beq ..., ..., outer（控制外層迴圈是否繼續）

假設內層迴圈每次執行 $N_{\text{inner}}$ 次迭代（$N_{\text{inner}} \ge 2$），外層迴圈執行 $N_{\text{outer}}$ 次迭代（$N_{\text{outer}} \ge 2$）。以下詳細推導預測錯誤（Mispredictions）發生的時機與原因：

1. 內層分支 $B_{\text{inner}}$ 的預測錯誤分析

• 錯誤時機一：內層迴圈結束跳出時（Loop Exit Misprediction）

  • 原因：內層迴圈在第 $1$ 至第 $N_{\text{inner}}-1$ 次迭代時，分支實際結果皆為 Taken，此時 1-bit 預測器被更新並保持為 $1$（Taken）。當執行到第 $N_{\text{inner}}$ 次迭代結束時，內層條件不滿足，實際結果為 Not Taken。預測器根據歷史紀錄預測為 Taken，因而產生預測錯誤。
  • 結果：預測器狀態被強制寫入並翻轉為 $0$（Not Taken）。

• 錯誤時機二：外層迴圈進入下一輪、再次開始執行內層迴圈時（Loop Re-entry Misprediction）

  • 原因：當外層迴圈進入下一輪迭代時，程式重新進入內層迴圈。在內層迴圈的第 $1$ 次迭代時，分支實際結果為 Taken（繼續迴圈）。然而，此時預測器狀態仍留存上一輪內層迴圈跳出時寫入的 $0$（Not Taken），導致預測器預測 Not Taken，再次產生預測錯誤。
  • 結果：預測器狀態被改回 $1$（Taken），使得內層迴圈隨後的第 $2$ 到 $N_{\text{inner}}-1$ 次迭代能正確預測。

• 小結：除了全程式第一次進入內層迴圈可能受預設初始狀態影響外，每次外層迴圈重複執行內層迴圈時，內層分支 $B_{\text{inner}}$ 固定會產生 2 次預測錯誤。

2. 外層分支 $B_{\text{outer}}$ 的預測錯誤分析

• 錯誤時機一：外層迴圈第一次迭代結束時（Initial Misprediction）

  • 原因：若預測器初始狀態預設為 $0$（Not Taken），則外層迴圈第 $1$ 次迭代結束跳回 Outer（實際為 Taken）時會發生預測錯誤，隨後將預測器更新為 $1$（Taken）。（若初始狀態預設為 Taken 則此次預測正確）。

• 錯誤時機二：整體外層迴圈結束跳出時（Outer Loop Exit Misprediction）

核心觀念

1. 快取記憶體位址拆解（Cache Address Decomposition）：
   在標準 32 位元位元組定址（Byte-addressed）系統中，主記憶體位址會拆分為三個主要欄位：

   • Tag（標籤位元）：用於與快取中的標籤進行比對，確認資料是否命中（Hit）。
   • Index（索引位元）：用於選擇快取中的特定區塊列（Block entry / Cache line）。
   • Offset（偏移位元）：用於定位區塊內部特定的資料位元組（Byte Offset）或字組（Word Offset）。

2. 快取規格計算公式：

   • 快取總區塊數（Number of blocks）$= 2^{\text{Index bits}}$
   • 快取區塊容量（Block size in bytes）$= 2^{\text{Offset bits}}$ 位元組
   • 快取區塊容量（Block size in words）$= \frac{2^{\text{Offset bits}}}{\text{Bytes per word}}$

---

解題方法

根據題目給定之位址切割圖：

• 位址總長度為 $32$ 位元（Bit 31 至 Bit 0）。
• Tag 欄位：Bit 31 至 Bit 10，共 $31 - 10 + 1 = 22$ 位元。
• Index 欄位：Bit 9 至 Bit 4，共 $9 - 4 + 1 = 6$ 位元。
• Offset 欄位：Bit 3 至 Bit 0，共 $3 - 0 + 1 = 4$ 位元。

1. 計算快取區塊數量（Number of Blocks）
快取採用直接對映（Direct-mapped）架構，Index 位元數決定了快取的總區塊數：
$\text{Number of blocks} = 2^{\text{Index bits}} = 2^6 = 64 \text{ blocks}$

2. 計算快取區塊大小（Cache Block Size in Words）

• 由 Offset 欄位共 $4$ 位元，可求得每個區塊以位元組為單位的容量：
  $\text{Block size in bytes} = 2^{\text{Offset bits}} = 2^4 = 16 \text{ bytes}$

核心觀念

本題考查計算機架構中**硬體多執行緒（Hardware Multithreading）**的兩大基本實現技術：細粒度多執行緒（Fine-grained Multithreading）與粗粒度多執行緒（Coarse-grained Multithreading）。重點在於理解兩者的切換粒度（Switching Granularity）、對流水線停頓（Pipeline Stalls）的隱藏能力、單執行緒延遲（Single-thread Latency）與系統吞吐量（System Throughput）之間的權衡（Trade-off），以及硬體設計開銷。

---

解題方法

本題為 10 分的觀念申論題，解題切入點應涵蓋三個核心面向：

1. 核心差異（Difference）：說明執行緒切換的時機與觸發機制（週期性切換 vs. 事件驅動切換）。
2. 細粒度多執行緒之優缺點（Pros & Cons of Fine-grained）：分析其對短延遲與長延遲的隱藏效果、單執行緒執行時間拉長的問題與硬體負擔。
3. 粗粒度多執行緒之優缺點（Pros & Cons of Coarse-grained）：分析其對重大停頓事件的處理、流水線清空（Pipeline Flush）開銷與對單執行緒效能的保護。

答題時先說明兩者機制的本質差異，再以條列式文字與對比表格呈現 Pros 與 Cons，能讓論述嚴謹、結構一目了然。

---

選項分析

（本題為申論問答題，針對題目要求的「Fine-grained Multithreading」與「Coarse-grained Multithreading」兩大主題及其「差異、優點、缺點」進行深入剖析）：

1. 核心差異 (Difference)

• Fine-grained Multithreading（細粒度多執行緒）：
  • 切換時機：在每一個時脈週期（Clock Cycle）之間以輪詢（Round-robin）方式交錯切換不同執行緒的指令發送（Instruction Issue）。
  • 切換觸發：屬於週期性交錯（Interleaved）切換，無論當前執行緒是否發生 Stall，下一個 Cycle 都會強制換下一個活躍的執行緒執行。
• Coarse-grained Multithreading（粗粒度多執行緒）：
  • 切換時機：單一執行緒會持續連續執行，直到遇到高延遲事件（High-latency Event）（如 L2/L3 Cache Miss 或主要記憶體存取）時，才切換至另一個執行緒。
  • 切換觸發：屬於事件驅動（Event-driven）切換，在沒有發生高延遲 Stall 時不會進行執行緒切換。

2. 細粒度多執行緒（Fine-grained Multithreading）之優缺點分析

• 優點 (Pros)：
  1. 完全隱藏各類流水線停頓（Hide Both Short and Long Stalls）：由於每個 Cycle 切換不同執行緒，若某個執行緒因資料相依（Data Hazard）、分支預測錯誤或 Cache Miss 而停頓，可直接繞過該執行緒並由其他獨立執行緒填充 Cycle，能徹底消除流水線氣泡（Pipeline Bubbles）。
  2. 高流水線利用率與吞吐量（High Pipeline Utilization & Throughput）：只要活躍的執行緒數量足夠，即可讓流水線始終保持滿載，最大化系統整體指令吞吐量。
• 缺點 (Cons)：
  1. 拉長單一執行緒的延遲（Slow Down Single-Thread Execution / High Latency）：即使其他執行緒沒有阻礙，單一執行緒也必須等待其他執行緒輪流執行完後才能獲取下一個 Cycle，導致單一任務的回應時間（Response Time）明顯增加。
  2. 硬體開銷較高（Higher Hardware Complexity）：硬體必須支援在單一週期內無縫切換執行緒內脈（Context Switching），代表每個執行緒都必須具備獨立的 PC（程式計數器）、暫存器檔案（Register File），且切換邏輯需極為迅速。

3. 粗粒度多執行緒（Coarse-grained Multithreading）之優缺點分析

• 優點 (Pros)：
  1. 保護單一執行緒效能（No Single-Thread Latency Penalty）：當系統沒有發生高延遲 Stall 時，單一執行緒以全速連續執行，不會被無故中斷或拖慢。