114 年 國立中山大學資訊工程學系碩士班甲組《計算機結構》

1.1

關鍵步驟：

1. 計算記憶體系統總 Row 數：
   $N_{\text{total}} = 8 \text{ banks} \times 2^{16} \text{ rows/bank} = 8 \times 65,536 = 524,288 \text{ rows}$

2. 計算在單一刷新週期（$64\text{ ms}$）內 Command Bus 佔用的總時間：
   $T_{\text{busy}} = N_{\text{total}} \times 5\text{ ns} = 524,288 \times 5 \times 10^{-9}\text{ s} = 2.62144\text{ ms}$

3. 計算 Command Bus 利用率：
   $\text{Utilization}_{\text{old}} = \frac{T_{\text{busy}}}{T_{\text{ref}}} = \frac{2.62144\text{ ms}}{64\text{ ms}} = 0.04096 = 4.096\%$

【答案】 Command Bus 利用率為 $4.096\%$（或 $0.04096$）。

---

1.2

關鍵步驟：

1. 計算單一 Row 的平均刷新次數比例：
   以 $256\text{ ms}$ 為共同週期計算：

核心觀念

虛擬記憶體位址可分為：

$$\text{Virtual Address}=\text{VPN}+\text{Page Offset}$$

實體記憶體位址可分為：

$$\text{Physical Address}=\text{PPN}+\text{Page Offset}$$

其中：

• Page Offset：頁面內的位移，取決於頁面大小。
• VPN（Virtual Page Number）：虛擬頁編號。
• PPN（Physical Page Number）：實體頁框編號。
• TLB index：決定查詢哪一個 TLB set。
• TLB tag：在該 set 中比對的標籤，通常由 VPN 扣除 index bits 得到。

TLB 為 4 sets、8-way associative，因此總共有：

$$4\times 8=32$$

個 TLB entries。LRU 只影響替換順序，不影響位元數計算。

解題方法

先將所有容量寫成 $2$ 的次方，再依序計算頁面位移、VPN、PPN，以及 TLB 的 index 與 tag。

1. Page Offset bits

頁面大小為 $1\ \mathrm{KiB}$：

$$1\ \mathrm{KiB}=2^{10}\ \mathrm{bytes}$$

因此頁面內位移需要：

$$\boxed{10\ \mathrm{bits}}$$

2. Virtual Page Number（VPN）bits

虛擬位址空間為 $4\ \mathrm{GiB}$：

$$4\ \mathrm{GiB}=2^2\times 2^{30}=2^{32}\ \mathrm{bytes}$$

虛擬位址總長度為 $32$ bits。扣除 $10$ bits 的 page offset：

$$\text{VPN bits}=32-10=22$$

因此：

$$\boxed{\text{VPN}=22\ \mathrm{bits}}$$

虛擬頁面的總數也就是：

$$\frac{2^{32}}{2^{10}}=2^{22}$$

3. Physical Page Number（PPN）bits

實體位址空間為 $256\ \mathrm{MiB}$：

$$256\ \mathrm{MiB}=2^8\times 2^{20}=2^{28}\ \mathrm{bytes}$$

實體位址長度為 $28$ bits。扣除 $10$ bits 的 page offset：

$$\text{PPN bits}=28-10=18$$

因此：

$$\boxed{\text{PPN}=18\ \mathrm{bits}}$$

4. TLB index bits

TLB 有 4 個 sets，因此 index 需要能表示 4 種 set：

$$\text{TLB index bits}=\log_2 4=2$$

因此：

$$\boxed{\text{TLB index}=2\ \mathrm{bits}}$$

5. TLB tag bits

TLB 通常以 VPN 查詢。VPN 中有 $2$ bits 用作 set index，其餘位元作為 tag：

$$\text{TLB tag bits}=22-2=20$$

因此：

3.1

解題觀念
當分支指令在第 6 階段確定結果時，代表管線在確定結果前已擷取了後續指令。一旦發生分支猜錯（Misprediction），這些已擷取的指令皆屬錯誤路徑，必須全部清空（Flush）。

推導步驟

1. 分支指令於第 1 階段擷取，至第 6 階段解析完成。
2. 在第 2 至第 6 階段期間，管線已接續擷取了 $6 - 1 = 5$ 個後續指令。
3. 當分支預測錯誤時，這 5 個指令皆為無用工作（Wasted work）。

【答案】5 個指令

---

3.2

解題觀念
總擷取指令數等於正確路徑指令數加上因分支猜錯而額外擷取的錯誤路徑指令數。

推導步驟

1. 正確路徑指令數為 $N$。
2. 題目給定分支指令佔總指令數的 20%，故分支指令總數為 $0.2N$。
3. 分支預測正確率為 $A$，則猜錯率為 $1 - A$，猜錯的分支數量為 $0.2N(1 - A)$。
4. 每次猜錯會浪費 5 個指令，故因猜錯而擷取的額外指令數為：
   $5 \times 0.2N(1 - A) = N(1 - A)$
5. 總擷取指令數 $N_{\text{fetch}}$ 為：
   $N_{\text{fetch}} = N + N(1 - A) = N(2 - A)$

【答案】$N(2 - A)$

---

3.3

解題觀念
雙路徑執行（Dual Path Execution）會在遇到分支時，同時從「跳躍（Taken）」與「不跳躍（Not-Taken）」兩條路徑擷取等量的指令。

核心觀念

本題考查計算機結構中的 管線效能分析（Pipeline Performance Analysis）、資料冒險（Data Hazards） 以及 前推機制（Forwarding / Bypassing） 對時脈週期時間（Clock Cycle Time, CCT）與執行時間（Execution Time）的權衡（Trade-off）。

1. 程式執行時間公式：
   $\text{Execution Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time (CCT)}$
   在 steady state 假設下，每執行一條指令（包含 NOP）耗費 $1$ 個週期（CPI = 1），因此總週期數等於總指令數：
   $\text{Total Cycles} = n + \text{NOP Count}$
   $\text{Execution Time} = (n + \text{NOP Count}) \times \text{CCT}$

2. 加速比（Speedup）：
   $\text{Speedup} = \frac{\text{Execution Time}_{\text{without forwarding}}}{\text{Execution Time}_{\text{with forwarding}}}$

3. 硬體設計權衡（Trade-off）：
   引入 Forwarding 硬體可以減少控制／資料相依所產生的 NOP（停頓週期），但額外增加的旁路邏輯與多工器（Mux）會拉長關鍵路徑（Critical Path），進而增加時脈週期時間（從 $250\text{ ps}$ 增加至 $300\text{ ps}$）。只有當減少 NOP 所節省的週期比例大於週期時間拉長的比例時，整體效能才會提升。

(註：題幹前言寫著 $4*n$ 係考題印刷誤植，子題 4.1 已明確給出無前推時的 NOP 數量為 $0.4*n$。解題統一採子題 4.1 設定之 $0.4*n$ 進行精確推導。)

---

解題方法

採用「量化執行時間比較法」：

1. 子題 4.1：分別計算無前推（Without Forwarding）與有前推（With Forwarding）兩種架構下的總執行時間 $T_{\text{no\_fwd}}$ 與 $T_{\text{fwd}}$，再相除求出 Speedup。
2. 子題 4.2：計算當無前推管線僅需 $0.075n$ 個 NOP 時的執行時間，並與前推架構的「理論極限最佳時間」（即 NOP 降為 $0$ 時）進行比較。
3. 子題 4.3：設無前推管線下的 NOP 比例為 $p$，列出前推架構「最佳狀況執行時間 $< T_{\text{no\_fwd}}$」的不等式，解出臨限值（Threshold）。

---

子題詳解與分析

4.1 (4%) 加速比計算

• 無前推管線（Without Forwarding）：

  • NOP 數量 = $0.4n$
  • 總指令／週期數 = $n + 0.4n = 1.4n$
  • 時脈週期時間 $\text{CCT}_{\text{no\_fwd}} = 250\text{ ps}$
  • 總執行時間：
    $T_{\text{no\_fwd}} = 1.4n \times 250\text{ ps} = 350n\text{ ps}$

• 具前推管線（With Forwarding）：

  • NOP 數量 = $0.05n$
  • 總指令／週期數 = $n + 0.05n = 1.05n$
  • 時脈週期時間 $\text{CCT}_{\text{fwd}} = 300\text{ ps}$
  • 總執行時間：
    $T_{\text{fwd}} = 1.05n \times 300\text{ ps} = 315n\text{ ps}$