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

核心觀念

本題的核心觀念為 MIPS 組合語言與高階語言（C 語言）控制結構的對應轉換 以及 編譯器迴圈最佳化技術（Loop Inversion / While 轉 Do-While）：

1. 陣列位址計算（Array Addressing）：在 MIPS 架構中，字組（Word）大小為 4 位元組（4 bytes）。陣列元素 $A[i]$ 的位址計算方式為：
   $\text{位址} = \text{Base Address of } A + (i \times 4)$
   在組合語言中透過左移兩位元 sll $t1, $s3, 2 實現 $i \times 4$，再以 add $t1, $t1, $s6 加上陣列基底位址。
2. 條件判斷與迴圈對應：
   • 序列 (I) 採用標準的 while 迴圈翻譯模式：在迴圈開頭進行條件測試，若不符合條件則跳出，迴圈結尾使用無條件跳躍 j Loop。
   • 序列 (II) 採用**迴圈反轉（Loop Inversion）**最佳化：先在迴圈外進行一次進場檢查，將迴圈主體改為 do-while 形式，使得迴圈內部僅需一次條件分支指令即可完成跳回，省去無條件跳躍指令。

---

解題方法

1. (a) 小題：
   • 逐行追蹤 Sequence (I) 與 Sequence (II) 的暫存器變化與控制流向。
   • 分別還原兩段組合語言所對應的 C 語言語句，驗證其邏輯等價性。
2. (b) 小題：
   • 設迴圈迭代次數（即符合條件 $A[i] == k$ 的次數）為 $N$。
   • 分別計算兩段程式碼在執行 $N$ 次迭代時所需要的動態指令執行總數（Dynamic Instruction Count）。
   • 比較兩者的執行指令數並從計算機結構與編譯器最佳化的角度分析效能差異。

---

題目詳解

(a) 驗證兩段 MIPS 程式碼對應的 C 語言敘述相同

1. 分析 Sequence (I)：

Loop: sll  $t1, $s3, 2      # $t1 = i * 4 (計算 byte offset)
      add  $t1, $t1, $s6    # $t1 = &A[i] (計算元素 A[i] 的記憶體位址)
      lw   $t0, 0($t1)      # $t0 = A[i] (載入 A[i] 的值)
      bne  $t0, $s5, Exit   # if (A[i] != k) goto Exit (若條件不成立則離開)
      addi $s3, $s3, 1      # i = i + 1
      j    Loop             # goto Loop (跳回開頭重新測試)
Exit:

• 控制流程：每次迴圈開始時，先檢查 $A[i]$ 是否等於 $k$。若相等，則將索引 $i$ 加 1 並跳回開頭重複檢查；若不相等，則立即跳出迴圈。
• 對應的 C 語言敘述：

  while (A[i] == k)
      i += 1;
  

---

2. 分析 Sequence (II)：

      sll  $t1, $s3, 2      # $t1 = i * 4
      add  $t1, $t1, $s6    # $t1 = &A[i]
      lw   $t0, 0($t1)      # $t0 = A[i]
      bne  $t0, $s5, Exit   # if (A[i] != k) goto Exit (初始進場檢查)
Loop: addi $s3, $s3, 1      # i = i + 1
      sll  $t1, $s3, 2      # $t1 = i * 4
      add  $t1, $t1, $s6    # $t1 = &A[i]
      lw   $t0, 0($t1)      # $t0 = A[i]
      beq  $t0, $s5, Loop   # if (A[i] == k) goto Loop (符合條件則繼續迴圈)
Exit:

• 控制流程：
  1. 進入迴圈前，先執行一次初始檢查：若一開始 $A[i] \neq k$，直接分支至 Exit，迴圈一次都不執行。
  2. 若初始 $A[i] == k$，則進入 Loop：先將 $i$ 加 1（i = i + 1），接著載入更新後的 $A[i]$，並以 beq $t0, $s5, Loop 判斷新元素是否仍滿足 $A[i] == k

參考書等級：資工系必讀（《Computer Architecture: A Quantitative Approach》第1章）

---

(a) 執行時間

每類指令週期數

$$\begin{aligned} \text{Arithmetic} &: 500\text{M}\times1 = 500\text{M} \\ \text{Load/Store} &: 300\text{M}\times10 = 3{,}000\text{M} \\ \text{Branch} &: 100\text{M}\times4 = 400\text{M} \end{aligned}$$

總週期數

$\text{Cycles}_{\text{total}} = 500\text{M}+3{,}000\text{M}+400\text{M}=3{,}900\text{M}=3.9\times10^{9}$

時脈頻率 $f=5\text{ GHz}=5\times10^{9}\,\text{Hz}$，時脈週期 $T=\frac1f=0.2\text{ ns}=2\times10^{-10}\,\text{s}$

$$\text{Execution Time}= \text{Cycles}_{\text{total}}\times T =3.9\times10^{9}\times2\times10^{-10}=0.78\ \text{s}$$

【答案】 執行時間 $0.78\,$秒。

---

核心觀念

本題考查 MIPS 五級管線中的：

• 資料危障（data hazard）
• 資料轉送（forwarding）
• 多個相同目的暫存器造成的轉送優先權
• 最近產生的結果必須優先於較早產生的結果

五級管線通常分為：

$$\text{IF} \rightarrow \text{ID} \rightarrow \text{EX} \rightarrow \text{MEM} \rightarrow \text{WB}$$

對目前位於 EX stage 的指令而言：

• EX/MEM 暫存器中的結果，來自「前一條」指令，較新，應具有較高優先權。
• MEM/WB 暫存器中的結果，來自「前兩條」指令，較舊，優先權較低。

因此，當兩個管線暫存器都要轉送到同一個運算元時，必須選擇 EX/MEM 的結果。

控制訊號定義如下：

• ForwardA = 10：ALU 的第一個輸入來自 EX/MEM
• ForwardA = 01：ALU 的第一個輸入來自 MEM/WB
• ForwardB = 10：ALU 的第二個輸入來自 EX/MEM
• ForwardB = 01：ALU 的第二個輸入來自 MEM/WB
• ForwardA = 00、ForwardB = 00：使用暫存器檔案讀出的值

解題方法

原本的 MEM hazard 條件只檢查 MEM/WB 是否要寫入相同暫存器，未檢查是否已有更近的 EX/MEM 結果。

因此，MEM hazard 必須增加「不存在同一運算元的 EX hazard」條件。

第一個 ALU 輸入

原本條件為：

$$\text{MEM/WB.RegWrite} \land (\text{MEM/WB.RegisterRd} \ne 0) \land (\text{MEM/WB.RegisterRd} = \text{ID/EX.RegisterRs})$$

修正後：

$$\begin{aligned} &\text{MEM/WB.RegWrite} \\ &\land (\text{MEM/WB.RegisterRd} \ne 0) \\ &\land (\text{MEM/WB.RegisterRd} = \text{ID/EX.RegisterRs}) \\ &\land \neg\big[ \text{EX/MEM.RegWrite} \land (\text{EX/MEM.RegisterRd} \ne 0) \\ &\qquad\qquad\land (\text{EX/MEM.RegisterRd} = \text{ID/EX.RegisterRs}) \big] \end{aligned}$$

若修正後條件成立：

$$\text{ForwardA} = 01$$

其意義是：只有在 EX/MEM 沒有針對 ID/EX.RegisterRs 提供更新結果時，才允許 MEM/WB 進行轉送。

第二個 ALU 輸入

原本條件為：

$$\text{MEM/WB.RegWrite} \land (\text{MEM/WB.RegisterRd} \ne 0) \land (\text{MEM/WB.RegisterRd} = \text{ID/EX.RegisterRt})$$

修正後：

$$\begin{aligned} &\text{MEM/WB.RegWrite} \\ &\land (\text{MEM/WB.RegisterRd} \ne 0) \\ &\land (\text{MEM/WB.RegisterRd} = \text{ID/EX.RegisterRt}) \\ &\land \neg\big[ \text{EX/MEM.RegWrite} \land (\text{EX/MEM.RegisterRd} \ne 0) \\ &\qquad\qquad\land (\text{EX/MEM.RegisterRd} = \text{ID/EX.RegisterRt}) \big] \end{aligned}$$

若修正後條件成立：

$$\text{ForwardB} = 01$$

套用至題目中的指令序列

考慮：

add $s1, $s1, $s2
add $s1, $s1, $s3
add $s1, $s1, $s4

第三條指令執行 EX stage 時：

• 第二條指令位於 MEM stage，結果位於 EX/MEM
• 第一條指令位於 WB stage，結果位於 MEM/WB
• 第三條指令的 ID/EX.RegisterRs = $s1
• 兩個管線暫存器的目的暫存器皆為 `

考慮 5 階段 pipeline，分支在 EX 階段解算，錯誤預測需 2 個空白週期 (IF、ID 被洗掉)。基礎 CPI 為 1，其他指令皆無資料危險。

(a) always‑taken 靜態預測器

• 只針對條件分支 beq (佔 15%) 產生預測。
• 正確率 40% ⇒ 錯誤率 60%。
• 錯誤分支比例 = $0.15 \times 0.60 = 0.09$。
• 額外 CPI = $0.09 \times 2 = \mathbf{0.18}$

(b) 2‑bit 動態預測器

• 正確率 80% ⇒ 錯誤率 20%。
• 錯誤分支比例 = $0.15 \times 0.20 = 0.03$。
• 額外 CPI = $0.03 \times 2 = \mathbf{0.06}$

(c) 將一半分支改寫成兩條 ALU 指令 (仍使用 2‑bit 預測)

• 原分支總比例 = $15\% + 10\% = 25\%$。
• 轉換比例 50% ⇒ 12.5% 仍保留分支，12.5% 變為 2 條 ALU。
• 指令總量變為

參考書：Hennessy & Patterson，《Computer Architecture: A Quantitative Approach》（第 5 版），第 3 章（Amdahl 定律）。

---

(a) 10 vs 40 核心，負載完全平衡

• 總工作量

  • 標量加總：$10$ 次
  • 矩陣加總 (10 × 10)：$100$ 次
  • $W_{\text{total}} = 10 + 100 = 110$

• 串行部分 $S = 10$，可平行部分 $P = 100$。

• 並行執行時間（$N$ 核心）

$T(N)=S+\frac{P}{N}=10+\frac{100}{N}$

• 速度提升

$\text{Speedup}(N)=\frac{W_{\text{total}}}{T(N)}=\frac{110}{10+100/N}$

核心數 $N$	$T(N)$	Speedup
10	$10+10=20$	$110/20 = 5.5$
40	$10+2.5=12.5$	$110/12.5 = 8.8$

核心觀念

本題考驗計算機效能評估中的經典 CPU 效能方程式（CPU Performance Equation）、加權平均 CPI（Average CPI）計算以及效能變動比例分析。

主要公式如下：

1. CPU 執行時間公式：
   $T_{\text{CPU}} = IC \times CPI \times \tau = \frac{IC \times CPI}{f}$
   其中：

   • $T_{\text{CPU}}$：CPU 執行時間（CPU Execution Time / CPU Time）
   • $IC$：動態指令總數（Instruction Count）
   • $CPI$：每指令平均時脈週期數（Cycles Per Instruction）
   • $\tau$：時脈週期時間（Clock Cycle Time）
   • $f$：時脈頻率（Clock Rate / Clock Frequency），且 $\tau = \frac{1}{f}$

2. 加權平均 CPI 公式：
   當程式包含多種不同類型的指令時，整體平均 $CPI$ 為各類指令占比（$f_i$）與其對應 $CPI_i$ 的加權總和：
   $CPI_{\text{avg}} = \sum_{i} (f_i \times CPI_i)$

---

解題方法

(a) 計算在給定時脈週期時間下的 CPI

1. 已知條件：

   • 指令數 $IC = 1.6 \times 10^{12}$
   • 執行時間 $T_{\text{CPU}} = 700\text{ s}$
   • 時脈週期時間 $\tau = 0.25\text{ ns} = 0.25 \times 10^{-9}\text{ s}$
   • （ Reference Time $9000\text{ s}$ 為幹擾資訊，計算 $CPI$ 時不需使用）

2. 推導步驟：
   利用 CPU 執行時間公式：
   $T_{\text{CPU}} = IC \times CPI \times \tau$
   代入已知數值：
   $700 = (1.6 \times 10^{12}) \times CPI \times (0.25 \times 10^{-9})$
   先計算 $IC \times \tau$ 的部分：
   $1.6 \times 10^{12} \times 0.25 \times 10^{-9} = 1.6 \times 250 = 400\text{ s}$
   因此：
   $700 = 400 \times CPI \implies CPI = \frac{700}{400} = 1.75$

(b) 計算指令數與 CPI 增加後 CPU 時間的增加百分比

1. 已知條件：

   • 指令數增加 $30\%$：$IC_{\text{new}} = 1.30 \times IC_{\text{old}}$
   • CPI 增加 $20\%$：$CPI_{\text{new}} = 1.20 \times CPI_{\text{old}}$
   • 時脈週期時間 $\tau$ 保持不變：$\tau_{\text{new}} = \tau_{\text{old}}$

2. 推導步驟：
   新的 CPU 執行時間為：
   $T_{\text{CPU, new}} = IC_{\text{new}} \times CPI_{\text{new}} \times \tau = (1.30 \times IC_{\text{old}}) \times (1.20 \times CPI_{\text{old}}) \times \tau_{\text{old}}$
   $T_{\text{CPU, new}} = 1.30 \times 1.20 \times (IC_{\text{old}} \times CPI_{\text{old}} \times \tau_{\text{old}}) = 1.56 \times T_{\text{CPU, old}}$
   計算 CPU 時間的增加百分比：
   $\text{增加百分比} = \frac{T_{\text{CPU, new}} - T_{\text{CPU, old}}}{T_{\text{CPU, old}}} \times 100\% = (1.56 - 1) \times 100\% = 56\%$

(c) 計算 P1 與 P2 之 CPI 比值（P1 / P2）

1. 已知條件：
   • 指令類別占比：A 類 $20\%$（$0.20$）、B 類 $10\%$（$0.10$）、C 類 $50\%$（$0.50$）、D 類 $20\%$（$0.20$）

(a) 兩補數有號 8 位元
151 → $151-256=-105$，214 → $214-256=-42$。
$-105+(-42)=-147$，超出 $-128\sim127$ 範圍，兩補數會環繞回 $256-147=109$。

【答案】$109$

---

(b) 無號 8 位元飽和運算
$151+214=365$，上限 $2^{8}-1=255$，飽和即取上限。

【答案】$255$

---

(c) IEEE‑754 單精度 0x42700000

• 符號 $s=0$。
• 指數位 $E=0x84=132$，$e=E-127=5$。

核心觀念

直接對映快取的位址欄位中，Offset 用來指定區塊內的位元組位置。因此，區塊大小為 $2^{\text{Offset 位元數}}$ 位元組；若每個 word 為 4 bytes，區塊大小（words）就是區塊大小（bytes）除以 4。

解題方法

圖中 Case I 的 Offset 欄位是 $[3\text{–}0]$，共 4 bits；Case II 的 Offset 欄位是 $[5\text{–}0]$，共 6 bits。依 32-bit word（4 bytes）計算各區塊包含的 word 數：

$$\text{區塊大小（words）} = \frac{2^{\text{Offset 位元數}}}{4}$$

Case I：

核心觀念

直接對映快取的每個位址索引值對應一個快取項目（entry）。若索引欄有 $k$ 個位元，索引共有 $2^k$ 種，因此快取有 $2^k$ 個 entries。

解題方法

圖中 Case I 的 Index field 是位址位元 $[9\text{–}4]$，共 $6$ 位；Case II 的 Index field 是 $[11\text{–}6]$，也共 $6$ 位。兩種情況各自的快取項目數為：

$$2^6=64$$

核心觀念

兩層快取的總 CPI，等於處理器基本 CPI 加上各層快取未命中所造成的停滯週期：

$$\text{總 CPI} = \text{基本 CPI} + \sum_i \left( \text{第 }i\text{ 層未命中率（每指令）} \times \text{該層未命中代價（週期）} \right)$$

本題給的是「每指令」的未命中率，因此可以直接乘上相應的未命中代價。

解題方法

依原卷題意，基本 CPI 為 $1$、時脈頻率為 $4\,\mathrm{GHz}$、主記憶體存取時間為 $100\,\mathrm{ns}$；主快取未命中率為每指令 $2\%$。新增次快取的存取時間為 $5\,\mathrm{ns}$，而到主記憶體的未命中率降至每指令 $0.4\%$。

先換算每個時脈週期的時間：

$$T_{\text{cycle}}=\frac{1}{4\,\mathrm{GHz}}=0.25\,\mathrm{ns}$$

每次主快取未命中都須存取次快取，因此次快取存取代價為：

核心觀念

單層頁表為每個虛擬頁面配置一個頁表項目（PTE）。因此：

$$\text{頁表大小（bytes）} = \text{虛擬頁面數} \times \text{每個 PTE 的大小}$$

虛擬頁面數由虛擬頁碼的位元數決定；虛擬頁碼位元數等於虛擬位址位元數減去頁面內位移位元數。

解題方法

圖中給定虛擬位址大小為 $44$ bits、頁面大小為 $4\,\mathrm{KiB}$、PTE 大小為 $4$ bytes；另列出實體 DRAM 為 $8\,\mathrm{GiB}$。先由頁面大小求出頁面內位移所需位元數：

$$4\,\mathrm{KiB}=2^{12}\ \text{bytes} \quad\Rightarrow\quad \text{頁面內位移}=12\ \text{bits}$$

核心觀念

本題比較兩種 TLB 組織與兩種頁表寫入策略對整體效能的影響。TLB 全相聯可減少直接對映造成的衝突失誤；在定性模型中，寫回可合併或延後寫入，通常比每次都寫入的寫入直達少耗費記憶體流量。不過，兩種技術帶來的效能差異大小並未提供。

整體效能可用有效存取時間理解：它受 TLB 命中率、TLB 存取時間、頁表存取成本，以及頁表寫入成本共同影響。若要精確比較，需要這些成本與失誤率的數值。

解題方法

依原卷表格，四種組合為：事件 1 是直接對映 TLB、寫回頁表；事件 2 是直接對映 TLB、寫入直達頁表；事件 3 是全相聯 TLB、寫入直達頁表；事件 4 是全相聯 TLB、寫回頁表。共用題幹中的虛擬位址、實體記憶體、頁面與 PTE 大小不影響本小題的定性排序。

在假設其他條件相同的定性模型下，全相聯 TLB 與寫回策略各自有利於效能。因此，兩項都有利的事件 4 排在最高；兩項皆無此優勢的事件 2 排在最低。事件 1 與事件 3 各有一項優勢，題目未提供足以判斷兩者先後的效能數據。

各事件分析