111 年 國立中山大學資訊管理學系碩士班甲組《計算機結構》

第 1 題

1. 虛擬記憶體的必要性、優點與缺點

核心觀念

虛擬記憶體（Virtual Memory）將 CPU 產生的虛擬位址轉換成實體記憶體位址。若頁面大小為 $2^p$ bytes，虛擬位址可表示為：

$$\text{Virtual Address}=(\text{VPN},\text{Page Offset})$$

頁表將虛擬頁號 $VPN$ 對映至實體頁號 $PPN$：

$$\text{Physical Address}=(\text{PPN},\text{Page Offset})$$

其中頁內位移 Page Offset 在轉換前後不變。TLB 則是頁表對映的高速快取。若頁表項顯示該頁不在主記憶體中，便產生 Page Fault，由作業系統從磁碟或 SSD 載入頁面。

為何需要虛擬記憶體

1. 提供獨立且連續的位址空間
   每個行程都可以視為擁有自己的大型連續記憶體，不必知道實體頁面實際分散在哪些位置。

2. 實現保護與隔離
   不同行程的虛擬位址可以對映到不同實體頁面，並透過頁表的權限位元限制讀取、寫入與執行權限，避免行程任意存取其他行程或核心資料。

3. 支援需求分頁（Demand Paging）
   程式不必一開始就全部載入主記憶體，只需載入目前使用的頁面，因此可以提高記憶體利用率。

4. 支援大型位址空間與記憶體共享
   行程的虛擬位址空間可以大於實體 RAM；共享函式庫、共享記憶體與 Copy-on-Write 也能透過不同虛擬位址對映到相同實體頁面實現。

優點

• 提供行程隔離與記憶體保護。
• 實體記憶體不必連續配置，配置彈性較高。
• 可用需求分頁降低程式啟動時的載入量。
• 支援共享頁面、虛擬記憶體映射檔案與 Copy-on-Write。
• 在工作集合（Working Set）適合的情況下，可同時執行多個大型程式。

缺點

• 每次記憶體存取都需要位址轉換；TLB Miss 時還要進行 Page Table Walk。
• Page Fault 必須存取磁碟或 SSD，延遲遠高於 RAM 存取。
• 頁表本身需要占用記憶體，多層頁表也會增加管理複雜度。
• 頁面配置會產生內部碎片。
• 若所有行程的工作集合超過可用 RAM，會發生 Thrashing，使系統大量換頁而效能急劇下降。

解題技巧

要區分三種事件：

• TLB Hit：快速完成位址轉換。
• TLB Miss：到頁表查詢，不一定發生 Page Fault。
• Page Fault：頁面不在 RAM，必須由作業系統載入，代價最高。

---

2. 擴大 TLB 後是否仍適合使用 Fully Associative

核心觀念

TLB 儲存的是近期使用的虛擬頁號到實體頁號的對映。Fully Associative TLB 中，每個虛擬頁號都可以放入任意 TLB entry，因此查詢時必須將輸入的 VPN 與所有 entry 平行比較。

若 TLB 有 $N$ 個 entry：

• Fully Associative：每次存取比較 $N$ 個 tag。
• $W$-way Set Associative：先用 index 找到一個 set，再比較該 set 中的 $W$ 個 tag。

解題方法與結論

TLB 通常比頁表小，因此 Fully Associative 的優點很明顯：

• 不需要 index bits。
• 任一虛擬頁都可放入任意位置。
• 沒有因固定索引造成的 Conflict Miss。
• 小型 TLB 可用平行比較快速完成查詢。

但當 TLB 擴大時，Fully Associative 的硬體成本會快速增加：

• 需要更多平行比較器。
• Tag 比對線路、結果選擇器與佈線負擔增加。
• 功耗與晶片面積增加。
• 平行比對結果的選擇與 replacement logic 變得更複雜。
• 存取時間可能受長距離佈線與高負載影響。

因此，TLB 大幅擴大後，通常不再適合維持 Fully Associative，而會採用較低路數的 Set Associative，甚至使用多層 TLB：

• 小型、速度要求高的 L1 TLB：可採 Fully Associative 或低路數配置。
• 容量較大的 L2 TLB：通常採 4-way、8-way 等 Set Associative。

解題技巧

Associativity 的取捨可記成：

• Fully Associative：命中率高，但硬體成本隨 entry 數量增加。
• Direct Mapped：硬體最簡單，但 Conflict Miss 較多。
• Set Associative：在成本與命中率之間取得折衷。

---

3. 多層快取的寫入策略

核心觀念

寫入策略主要分成兩部分：

1. Write-Through
   寫入快取的同時，也立即寫入下一層快取或主記憶體。

2. Write-Back
   先只更新目前層級的快取，並將該 cache line 標示為 Dirty；只有在該 line 被替換時，才寫回下一層。

此外，Write Miss 還要決定是否採用：

• Write-Allocate：先將資料所在的 cache line 載入，再在快取中修改。
• No-Write-Allocate：不載入 cache line，直接將資料寫入下一層。

解題方法與合理假設

題目未限定「一致性」是指各層資料立即同步，還是以整體效能為優先；依現代高效能多層快取的標準設計，採用 Write-Back 搭配 Write-Allocate。

寫入流程如下：

1. CPU 寫入 L1 Cache 命中時，只更新 L1，並設定 Dirty Bit。
2. L1 的 Dirty Cache Line 被替換時，整個 line 寫回 L2。
3. 若 L2 也採 Write-Back，則 L2 將該 line 標示為 Dirty。
4. 最後一層快取淘汰該 line 時，才寫回主記憶體。

此策略可避免每次 Store 都存取較低層快取或主記憶體，大幅減少寫入流量。Write-Allocate 則適合具有空間區域性的資料，因為同一 cache line 的其他資料很可能很快被使用。

Write-Through 的特性

Write-Through 的一致性管理較簡單，因為每次寫入都會立即傳遞到下一層；但缺點是：

• 寫入流量大。
• 主記憶體或低層快取承受較多請求。
• 高頻率 Store 會降低有效頻寬。

若課本將「一致性」嚴格定義為 L1 與 L2 的副本必須立即相同，則可使用 L1 Write-Through、較低層 Cache Write-Back 的混合策略。這能保持相鄰快取層的資料同步，並減少寫入主記憶體的次數。

在多核心系統中，Write-Back 本身不等於 Cache Coherence，還必須配合 MESI 等一致性協定，處理其他核心快取中的副本。

解題技巧

• 重視效能與寫入頻寬：Write-Back。
• 重視硬體簡單與立即同步：Write-Through。
• Write-Back 通常與 Write-Allocate 配對。

1. 頁表大小

• 程式位址空間：$4\text{GB}=2^{32}\text{B}$
• 頁面大小：$4\text{KB}=2^{12}\text{B}$
• 頁數 $=2^{32}/2^{12}=2^{20}=1\,048\,576$ 頁
• 每個頁表項假設 4 B（存放框架號與控制位）

$\text{頁表大小}=1\,048\,576 \times 4\text{B}=4\,194\,304\text{B}=4\text{ MB}$

2. 隨機存取下的近似缺頁率

• 實體記憶體可容納框架數 $=2\text{GB}/4\text{KB}=2^{31}/2^{12}=2^{19}=524\,288$ 框
• 程式總頁數 $=1\,048\,576$ 頁

核心觀念與計算假設

本題採用以下標準假設：

• 32-bit processor 的 word 為 $32$ bits，即 $4$ bytes。
• 記憶體採 byte-addressable。
• Cache 的 $16\text{KB}$ 僅指資料區，不含 tag 與控制位元。
• 每個 cache line 具有 $1$ 個 valid bit 與 $1$ 個 dirty bit。
• 第 3 題的二路組相聯 cache，每組以 $1$ bit 記錄 LRU。
• 第 4、5 題未指定實體位址寬度、TLB 組織與 PTE 欄位；以下採 32-bit 虛擬位址、32-bit 實體位址、10-entry 全相聯 TLB，並計入 valid bit。

Cache 位址欄位公式為：

$$\text{位址}= \text{Tag}+\text{Index}+\text{Block Offset}$$

其中：

• Block offset：指出 block 內的 byte。
• Index：指出 cache line 或 set。
• Tag：儲存在 cache 中，用來比對位址。
• Write-back 需要 dirty bit，表示該 cache line 是否被修改。
• 每個 cache line 需要 valid bit，表示內容是否有效。

---

第 1 題：Direct Mapping，one-word block

解題方法

一個 word 為 $4$ bytes，因此：

$$\text{Block size}=4\text{ bytes}=2^2\text{ bytes}$$

Cache 資料容量為：

$$16\text{KB}=2^{14}\text{ bytes}$$

Cache line 數量：

$$\frac{2^{14}}{2^2}=2^{12}=4096\text{ lines}$$

因此：

• Block offset：$2$ bits
• Index：$\log_2 4096=12$ bits
• Tag：

$$32-12-2=18\text{ bits}$$

每個 cache line 儲存：

$$\underbrace{32}_{\text{資料}} +\underbrace{18}_{\text{Tag}} +\underbrace{1}_{\text{Valid}} +\underbrace{1}_{\text{Dirty}} =52\text{ bits}$$

Direct mapping 每個 index 只有一個候選位置，不需要額外儲存 LRU bit。

因此總位元數為：

$$4096\times 52 =212,992\text{ bits}$$

換算為 bytes：

$$\frac{212,992}{8}=26,624\text{ bytes}$$

【答案】

$$\boxed{212,992\text{ bits}}$$

---

第 2 題：Direct Mapping，four-word block

解題方法

四個 word 的 block 大小為：

$$4\times 4=16\text{ bytes}=2^4\text{ bytes}$$

Cache line 數量：

$$\frac{2^{14}}{2^4}=2^{10}=1024\text{ lines}$$

因此：

• Block offset：$4$ bits
• Index：$\log_2 1024=10$ bits
• Tag：

$$32-10-4=18\text{ bits}$$

每個 block 包含四個 word，資料量為：

$$4\times 32=128\text{ bits}$$

每個 cache line 儲存：

$$128+18+1+1=148\text{ bits}$$

Direct mapping 不需 LRU bit，因此總位元數為：

$$1024\times 148 =151,552\text{ bits}$$

【答案】

$$\boxed{151,552\text{ bits}}$$

---

第 3 題：Two-way Set Associative，four-word block

解題方法

四-word block 仍為 $16$ bytes，因此 cache 總 line 數仍為：

$$\frac{16\text{KB}}{16\text{ bytes}} =1024\text{ lines}$$

二路組相聯表示每一組有兩個 cache lines，所以 set 數量為：

$$\frac{1024}{2}=512=2^9\text{ sets}$$

因此：

• Block offset：$4$ bits
• Set index：$9$ bits
• Tag：

1. 平均記憶體存取時間 (AMAT)

快取存取時間 (hit time) 為 1 個時脈＝$1\text{ns}$。
未命中懲罰 (miss penalty) 為 $20$ 個時脈＝$20\text{ns}$，未命中率 $=5\% =0.05$。

$$\text{AMAT}= \text{hit time} + (\text{miss rate})\times(\text{miss penalty}) = 1\text{ns} + 0.05 \times 20\text{ns} = 1\text{ns} + 1\text{ns} = \boxed{2\text{ns}}$$

---

2. 需使用多少核心才能將效能提升 2 倍？

程式中可平行化部分比例 $P=0.40$，其餘 $1-P=0.60$ 為序列區段。
根據 Amdahl 定律：

核心觀念

本題考查三個重點：

1. 資料相依與停滯：沒有資料前饋（forwarding）時，後續指令必須等前一指令將結果寫回暫存器，才能讀到正確資料。
2. 共用加減法器：利用二補數關係 $A-B=A+\overline{B}+1$，讓加法與減法共用同一個加法器，再以多工器選出算術或邏輯結果。
3. 管線階段重配置：運算可以移到較早的階段，但資料、控制訊號與管線暫存器必須配合調整，並符合每階段一個時脈週期的限制。

解題方法

由原圖可讀出五階段為 IF、ID、EX、MEM、WB，未畫出將 EX/MEM 或 MEM/WB 結果送回 ALU 輸入端的前饋路徑。分支目標位址的加法器位於 EX，而 Branch 與 Zero 在 MEM 經 AND 閘產生 PCSrc，控制 IF 的 PC 選擇。

（1）是否需要停滯？需要幾個週期？

程式第一條指令：

sub $2, $1, $3

會產生新的暫存器 $2 值。其後四條指令都需要讀取 $2：

指令	$2 的用途
and $12, $2, $5	AND 的來源運算元
or $13, $6, $2	OR 的來源運算元
add $14, $2, $2	ADD 的兩個來源運算元
sw $15, 100($2)	計算記憶體位址的基底暫存器

因此存在 RAW（先寫後讀）資料相依。

圖中沒有前饋路徑，and 必須等 sub 到達 WB，才能在 ID 讀到新值。圖未註明暫存器檔的讀寫時序，採用標準 MIPS 的「同一週期先寫入、後讀取」設計。

sub 的執行時序為：

$$\text{IF}_1\rightarrow\text{ID}_2\rightarrow\text{EX}_3 \rightarrow\text{MEM}_4\rightarrow\text{WB}_5$$

and 原本在第 3 週期進入 ID、第 4 週期進入 EX；現在必須停留在 ID，等到第 5 週期讀取 $2，第 6 週期才能進入 EX。

$$\text{停滯週期數}=6-4=2$$

完整時序如下：

指令	IF	ID	EX	MEM	WB
sub	1	2	3	4	5
and	2	3～5	6	7	8
or	3，停留至 5	6	7	8	9
add	6	7	8	9	10
sw	7	8	9	10	不寫回

停滯期間應凍結 PC 與 IF/ID 暫存器，並在 EX 插入兩個氣泡（bubble）；前方的 sub 繼續前進。第 5 週期 sub 寫回後，and 讀到新值，其餘指令也都在更晚的週期讀取 $2，因此不需額外停滯。

（2）設計支援程式的最小 ALU 架構

這段程式需要以下功能：

指令	ALU 所需運算
sub	$A-B$
and	$A\land B$
or	$A\lor B$
add	$A+B$
sw	基底位址加上符號延伸後的立即數

sw 的 ALU 輸入由圖中的 ALUSrc 多工器選擇，使：

$$A=\operatorname{Reg}[2],\qquad B=\operatorname{SignExtend}(100)$$

ALU 執行加法，得到有效位址 $\operatorname{Reg}[2]+100$。待儲存的資料 $\operatorname{Reg}[15]$ 經另一條資料路徑送往資料記憶體，並非此加法的運算元。

共用加減法器

令 SUB 為減法控制訊號，對 $B$ 的每一位執行 XOR：

$$B'_i=B_i\oplus SUB,\qquad i=0,\ldots,31$$

再將 $A$、$B'$ 與進位輸入送入同一個 32 位元加法器：

$$Sum=A+B'+SUB\pmod{2^{32}}$$

• SUB = 0：$B'=B$、進位輸入為 $0$，得到 $A+B$。
• SUB = 1：$B'=\overline{B}$、進位輸入為 $1$，得到 $A+\overline{B}+1=A-B