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

核心觀念

本題的核心考點為平行計算架構中的阿姆達爾定律（Amdahl's Law）以及通訊開銷（Communication Overhead）對平行加速效能的影響。

1. 阿姆達爾定律（Amdahl's Law）：
   定義加速比（Speedup）為單一處理器之執行時間（$T_1$）與 $p$ 個處理器平行執行時間（$T_p$）的比值：
   $\text{Speedup} = \frac{T_{\text{original}}}{T_{\text{parallel}}} = \frac{T_1}{T_p}$
   若程式中可平行化比例為 $f$，不可平行化（循序執行）比例為 $1 - f$，在忽略通訊與同步開銷的情況下：
   $T_p = T_1 \times \left( (1 - f) + \frac{f}{p} \right)$
   $\text{Speedup} = \frac{1}{(1 - f) + \dfrac{f}{p}}$

2. 納入通訊開銷之平行執行時間：
   當考量通訊額外開銷（$T_{\text{comm}}$）時，總平行執行時間變為：
   $T_p = T_1 \times \left( (1 - f) + \frac{f}{p} \right) + T_{\text{comm}}$
   加速比則修正為：
   $\text{Speedup} = \frac{T_1}{T_p} = \frac{1}{(1 - f) + \dfrac{f}{p} + \dfrac{T_{\text{comm}}}{T_1}}$

---

解題方法

令單一處理器的原始執行時間為基準 $T_1 = 1$。
已知可平行化比例 $f = 80\% = 0.8$，循序比例 $1 - f = 20\% = 0.2$，處理器個數 $p = 8$。

1.1 計算忽略通訊成本時的加速比（$p = 8$）

1. 計算平行執行時間 $T_8$：
   $T_8 = T_1 \times \left( (1 - f) + \frac{f}{8} \right) = T_1 \times \left( 0.2 + \frac{0.8}{8} \right) = T_1 \times (0.2 + 0.1) = 0.3 \times T_1$

核心觀念

本題考查兩個概念：

1. GPU 的峰值浮點吞吐量
   計算所有可同時工作的浮點單元數，再乘上時脈頻率。

2. 記憶體頻寬限制與算術強度（Arithmetic Intensity）
   算術強度定義為：

   $AI=\frac{\text{浮點運算次數}}{\text{從 off-chip memory 搬移的位元組數}}$

   GPU 的實際效能受下式限制：

   $P_{\text{actual}}\leq \min\left(P_{\text{compute}},\ B_{\text{memory}}\times AI\right)$

   即使記憶體延遲能完全隱藏，有限的記憶體頻寬仍可能限制吞吐量。

解題方法

2.1 峰值單精度浮點吞吐量

GPU 中的單精度浮點單元總數為：

$16\ \text{個 SIMD processors}\times 16\ \text{個浮點單元}=256\ \text{個浮點單元}$

時脈頻率為：

$2.0\ \text{GHz}=2.0\times 10^9\ \text{cycles/sec}$

在每個浮點單元每個 clock 完成 1 次浮點運算的假設下：

$$P_{\text{compute}} =256\times 2.0\times 10^9 =512\times 10^9\ \text{FLOP/sec}$$

因此：

$P_{\text{compute}}=512\ \text{GFLOPS}$

2.2 記憶體頻寬是否足以維持此吞吐量

要維持 $512\ \text{GFLOPS}$，所需的最低算術強度為：

$$AI_{\text{break-even}} =\frac{512\ \text{GFLOPS}}{600\ \text{GB/sec}} =\frac{512}{600} \approx 0.853\ \text{FLOP/byte}$$

因此：

• 若 $AI\geq 0.853\ \text{FLOP/byte}$，記憶體頻寬足以支撐計算單元達到 $512\ \text{GFLOPS}$。
• 若 $AI<0.853\ \text{FLOP/byte}$，效能會受記憶體頻寬限制，無法達到峰值。

題目未提供實際程式的資料搬移量，因此嚴格而言缺少算術強度，無法對所有程式給出唯一的「是」或「否」。

3.1 時脈週期時間 (Clock Cycle Time)

1. 非流水線處理器 (Non-pipelined / Single-cycle)：
   時脈週期時間由執行時間最長的指令（即經過全部 5 個階段的 lw 指令）決定：
   $\text{Cycle Time} = \text{IF} + \text{ID} + \text{EX} + \text{MEM} + \text{WB} = 250 + 150 + 350 + 300 + 200 = 1250\text{ ps}$

2. 流水線處理器 (Pipelined)：
   時脈週期時間由延遲最長的單一階段（EX 階段）決定：
   $\text{Cycle Time} = \max(\text{IF}, \text{ID}, \text{EX}, \text{MEM}, \text{WB}) = 350\text{ ps}$

【答案】非流水線處理器為 $1250\text{ ps}$；流水線處理器為 $350\text{ ps}$。

---

3.2 個別指令總延遲 (Individual Total Latency)

1. 非流水線處理器：
   單一時脈週期架構下，時脈週期固定為 $1250\text{ ps}$，故每筆指令執行時間皆佔據一個完整時脈週期 $1250\text{ ps}$（若按硬體實際經過的階段延遲，lw 為 $1250\text{ ps}$，beq 為 $\text{IF} + \text{ID} + \text{EX} = 250 + 150 + 350 = 750\text{ ps}$）。

2. 流水線處理器：
   所有指令在流水線中皆須通過 5 個 pipeline 階段，總延遲為：
   $\text{Latency} = 5 \times 350\text{ ps} = 1750\text{ ps}$
   因此 lw 與 beq 的總延遲皆為 $1750\text{ ps}$。

觀念與前提設定

• 條件分歧指令（BEQ）比例：$20\%$
• 分支預測錯誤懲罰（Penalty）：在傳統 5 階段 Pipeline（IF, ID, EX, MEM, WB）中，若分支結果於 EX 階段（第 3 階段）確定，預測錯誤時需 Flush 已進入 IF 與 ID 階段的 2 個指令，懲罰時間為 $2$ 個 Clock Cycles。
• 基礎 CPI：無任何 Hazard 下之理想 CPI 為 $1.0$。

---

4.1

使用 Always-Taken 預測器，正確率為 $40\%$，預測錯誤率（Misprediction Rate）為 $1 - 40\% = 60\%$。

預測錯誤導致的額外 CPI（Extra CPI）計算如下：
$\text{Extra CPI} = \text{BEQ Frequency} \times \text{Misprediction Rate} \times \text{Penalty Cycles}$
$\text{Extra CPI} = 0.20 \times (1 - 0.40) \times 2 = 0.20 \times 0.60 \times 2 = 0.24$

【答案】$0.24$

---

4.2

使用 2-Bit 預測器，正確率為 $80\%$，預測錯誤率為 $1 - 80\% = 20\%$。

5.1 記憶體存取紀錄分析

快取記憶體位址分割（32-bit 位址）

• 單一區塊大小：$2\text{ words} = 8\text{ bytes} \Rightarrow$ Offset 占 $3\text{ bits}$（含 $1\text{ bit}$ Block Offset 與 $2\text{ bits}$ Byte Offset）。
• 區塊總數：$8\text{ blocks} \Rightarrow$ Index 占 $\log_2(8) = 3\text{ bits}$。
• Tag 長度：$32 - 3 - 3 = 26\text{ bits}$。

位址切割結構如下：

• $\text{Tag} = \text{Word Address} \gg 4$（前 26 位元）
• $\text{Index} = (\text{Word Address} \gg 1) \pmod 8$（中間 3 位元）
• $\text{Block Offset} = \text{Word Address} \pmod 2$（最低 1 位元）

各筆記憶體存取結果推導

1. Word Address = 3 ($00000000000000000000000000000011_2$)

   • 32-bit 位址：0x0000000C ($0000\dots0000001100_2$)
   • Tag: $0$ ($0\dots00_2$)，Index: $1$ ($001_2$)
   • 狀態：Miss（將 Block 1 填入 Tag 0）

2. Word Address = 180 ($00000000000000000000000010110100_2$)

   • 32-bit 位址：0x000002D0 ($0000\dots001011010000_2$)
   • Tag: $11$ ($0\dots01011_2$)，Index: $2$ ($010_2$)
   • 狀態：Miss（將 Block 2 填入 Tag 11）

3. Word Address = 43 ($00000000000000000000000000101011_2$)

   • 32-bit 位址：0x000000AC ($0000\dots000010101100_2$)
   • Tag: $2$ ($0\dots00010_2$)，Index: $5$ ($101_2$)
   • 狀態：Miss（將 Block 5 填入 Tag 2）

4. Word Address = 2 ($00000000000000000000000000000010_2$)

   • 32-bit 位址：0x00000008 ($0000\dots0000001000_2$)
   • Tag: $0$ ($0\dots00_2$)，Index: $1$ ($001_2$)
   • 狀態：Hit（Block 1 已有 Tag 0）

5. Word Address = 191 ($00000000000000000000000010111111_2$)

   • 32-bit 位址：0x000002FC ($0000\dots001011111100_2$)
   • Tag: $11$ ($0\dots01011_2$)，Index: $7$ ($111_2$)
   • 狀態：Miss（將 Block 7 填入 Tag 11）

6. Word Address = 88 ($00000000000000000000000001011000_2$)

   • 32-bit 位址：0x00000160 ($0000\dots000101100000_2$)
   • Tag: $5$ ($0\dots00101_2$)，Index: $4$ ($100_2$)
   • 狀態：Miss（將 Block 4 填入 Tag 5）

7. Word Address = 190 ($00000000000000000000000010111110_2$)

   • 32-bit 位址：0x000002F8 ($0000\dots001011111000_2$)
   • Tag: $11$ ($0\dots01011_2$)，Index: $7$ ($111_2$)
   • 狀態：Hit（Block 7 已有 Tag 11）

8. Word Address = 14 ($00000000000000000000000000001110_2$)

   • 32-bit 位址：0x00000038 ($0000\dots000000111000_2$)
   • Tag: $0$ ($0\dots00_2$)，Index: $7$ ($111_2$)
   • 狀態：Miss（替換 Block 7 的 Tag 為 0）

9. Word Address = 181 ($00000000000000000000000010110101_2$)

   • 32-bit 位址：0x000002D4 ($0000\dots001011010100_2$)
   • Tag: $11$ ($0\dots01011_2$)，Index: $2$ ($010_2$)
   • 狀態：Hit（Block 2 已有 Tag 11）

10. Word Address = 44 ($00000000000000000000000000101100_2$)

    • 32-bit 位址：0x000000B0 ($0000\dots000010110000_2$)

核心觀念

本題比較兩種快取組織的兩項指標：

1. 平均記憶體存取時間：
   $\text{AMAT}=\text{Hit Time}+\text{Miss Rate}\times\text{Miss Penalty}$

2. CPU 執行時間：
   $T_{\text{CPU}}=\text{Instruction Count}\times\text{CPI}\times\text{Clock Cycle Time}$

完美快取下的 $\text{CPI}=2.0$ 已包含正常快取命中的執行成本，因此只需額外加入快取未命中的停滯時間。

快取總區塊數為：

$\frac{64\text{ KB}}{64\text{ B}}=1024\text{ blocks}$

直接映射快取有 $1024$ 條快取線；二路組合相聯快取有 $512$ 個集合，每集合含 $2$ 條快取線。題目已直接給出兩者的 miss rate，因此不必再由位址存取序列推導 miss rate。

---

6.1 平均記憶體存取時間

直接映射快取

原始時脈週期為：

$T_c=1.0\text{ ns}$

命中時間為一個時脈週期：

$T_{\text{hit}}=1.0\text{ ns}$

因此：

$$\begin{aligned} \text{AMAT}_{\text{direct}} &=T_{\text{hit}}+\text{Miss Rate}\times\text{Miss Penalty}\\ &=1.0+(0.015)(80)\\ &=2.20\text{ ns} \end{aligned}$$

二路組合相聯快取

由於選擇多工器使 CPU 時脈週期延長為原本的 $1.3$ 倍：

$T_c=1.3\times1.0=1.3\text{ ns}$

命中時間為：

$T_{\text{hit}}=1.3\text{ ns}$

因此：

$$\begin{aligned} \text{AMAT}_{\text{2-way}} &=1.3+(0.011)(80)\\ &=1.3+0.88\\ &=2.18\text{ ns} \end{aligned}$$

二路組合相聯快取的 AMAT 為 $2.18\text{ ns}$，略低於直接映射快取的 $2.20\text{ ns}$。

---

6.2 CPU 執行時間

設程式共有 $I$ 條指令。每條指令平均有 $1.5$ 次記憶體參考，因此每條指令的 miss 次數為：

$\text{Misses per Instruction}=1.5\times\text{Miss Rate}$

每條指令的額外 miss 停滯時間為：

$\text{額外時間}=(1.5)(\text{Miss Rate})(80\text{ ns})$

直接映射快取

每條指令的 miss 次數：

$1.5\times0.015=0.0225$

每條指令的 miss 停滯時間：

核心觀念

本題考查兩部分：

1. 單層頁表的大小計算：

   • 虛擬位址由「虛擬頁號 VPN」與「頁內位移 offset」組成。
   • 頁表需要一個 PTE 對應一個虛擬頁。
   • 頁表大小＝PTE 數量 × 每個 PTE 大小。

2. TLB、頁表與 Page Fault 的判斷：

   • 先以虛擬位址查 TLB。
   • TLB 命中：直接取得 Physical Page Number。
   • TLB 未命中，再查頁表。
   • 頁表有效：稱為 page table hit，並將映射填入 TLB。
   • 頁表無效且標示 Disk：發生 page fault，從磁碟載入頁面，再更新頁表與 TLB。
   • TLB 採 4-entry fully associative，必須逐筆比對 Tag。
   • 替換策略為 true LRU，最近使用的項目保留，最久未使用的項目被替換。

---

7.1 單層頁表大小

步驟一：計算頁內位移位元數

頁面大小為 $4\text{ KiB}$：

$$4\text{ KiB}=4\times 2^{10}=2^{12}\text{ bytes}$$

因此頁內位移需要 $12$ bits。

步驟二：計算虛擬頁號位元數

虛擬位址為 $42$ bits，因此虛擬頁號為：

$$42-12=30\text{ bits}$$

可表示的虛擬頁數為：

$$2^{30}\text{ pages}$$

單層頁表每個虛擬頁需要一個 PTE，所以 PTE 數量為：

$$\boxed{2^{30}\text{ 個 PTE}}$$

步驟三：計算頁表所需記憶體

每個 PTE 為 $4$ bytes：

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

而：

$$2^{32}\text{ bytes}=4\text{ GiB}$$

因此頁表需要：

$$\boxed{4\text{ GiB}}$$

題目給出的 Physical DRAM Installed 為 $16$ GiB，並不影響單層頁表本身的計算；它只表示系統實際安裝的實體記憶體容量。

---

7.2 位址轉換與 TLB 更新

已知系統

• Page Size：$4\text{ KiB}=4096$ bytes
• TLB：4-entry fully associative
• Replacement：true LRU
• 虛擬頁號：

$$VPN=\left\lfloor \frac{\text{Virtual Address}}{4096}\right\rfloor$$

• 頁內位移：

$$offset=\text{Virtual Address}\bmod 4096$$

初始 TLB

Valid	Tag（VPN）	Physical Page Number
1	11	12
1	7	4
1	3	6
0	4	9

其中 Tag 代表虛擬頁號 VPN。

初始 Page Table

VPN	Valid	Physical Page 或 Disk
0	1	5
1	0	Disk
2	0	Disk
3	1	6
4	1	9
5	1	11
6	0	Disk
7	1	4
8	0	Disk
9	0	Disk
10	1	3
11	1	12

題目中的完整位址串流只列出 4669, 13916, ...，省略號後的位址未提供，因此無法唯一決定原題要求的完整最終狀態。以下先依照目前明確列出的兩筆位址計算；此計算也展示完整串流的處理方式。

---

Reference 1：Virtual Address = 4669

計算 VPN 與 offset

$$4669=1\times4096+573$$

因此：

$$VPN=1,\qquad offset=573$$

查詢 TLB

初始 TLB 的 Tag 為 $11,7,3$，沒有 VPN $1$。

因此：

$$\boxed{\text{TLB miss}}$$

查詢 Page Table

VPN $1$ 的頁表項為：

VPN	Valid	Physical Page 或 Disk
1	0	Disk

該頁不在實體記憶體中，因此發生：

$$\boxed{\text{page fault}}$$