108 年 國立中央大學資訊工程學系軟體工程碩士班《作業系統與計算機組織》

核心觀念

• 多工系統的 CPU 利用率：在多程式系統中，CPU 只有在全部程式同時等待 I/O 時才會閒置。
• 等待機率：若單一程式有 $p$ 的機率在任何時刻等待 I/O，則該程式 就緒 的機率為 $1-p$。
• 獨立性假設：各程式的 I/O 等待相互獨立，系統的閒置機率為所有程式同時等待的機率 $p^{n}$，其中 $n$ 為多工度（同時駐留於記憶體的程式數）。

解題方法

1. 依題意，單一程式等待 I/O 的機率 $p = 0.40$。
2. 多工度 $n = 6$（同時有 6 個程式）。
3. 系統閒置機率 $= p^{n}=0.40^{6}$。
4. CPU 利用率 $U = 1 - p^{n}=1-0.40^{6}$。
5. 計算 $0.40^{6}$：

$$0.40^{2}=0.16,\; 0.40^{3}=0.064,\; 0.40^{4}=0.0256,\; 0.40^{5}=0.01024,\; 0.40^{6}=0.004096$$

故

$U = 1 - 0.004096 = 0.995904$

核心觀念

• 快取未命中率 (miss rate)：指存取快取時找不到資料的比例。
• 未命中懲罰 (miss penalty)：一次未命中所需額外的時脈週期。
• CPI (Cycles Per Instruction)：每條指令平均需要的時脈週期，若快取命中則無額外懲罰，此題假設 CPI = 1 為基本值。
• 指令快取 vs. 資料快取：指令快取只影響每條指令的取指；資料快取只在執行資料存取指令時才會產生影響。

解題方法

1. 計算每條指令的平均懲罰
   • 指令快取未命中

$$\text{指令未命中懲罰 per instruction}= \text{指令未命中率}\times \text{未命中懲罰} =0.02 \times 50 = 1\;\text{cycle}$$

• 資料快取未命中
  只有 20% 的指令會執行資料存取，因此每條指令的平均資料未命中懲罰為

$$\text{資料未命中懲罰 per instruction}=0.20 \times (\text{資料未命中率}\times \text{未命中懲罰}) =0.20 \times (0.04 \times 50)=0.20 \times 2 =0.4\;\text{cycle}$$

2. 求每條指令的總 CPI

核心觀念

• IEEE‑754 單精度（32 bit）浮點數的位元配置

$\text{[sign (1 bit)]}\;\; \text{[exponent (8 bits)]}\;\; \text{[fraction / mantissa (23 bits)]}$

• 正規化 (normalized)：指數欄位不全為 0，也不全為 1，隱含的前導位元為 1。
• 非正規化 (denormalized)：指數全部為 0，隱含前導位元為 0，只有 fraction 部分決定大小。
• 特殊值：指數全為 1，fraction 為 0 → 正/負無限大；fraction ≠ 0 → NaN。
• 位元運算 XOR：相同位元得 0，不同位元得 1。題目要求計算四個浮點數的位元 XOR，然後統計 1 的個數 $K$，求 $K\bmod 5$。

---

解題方法

1. 寫出每個數的 32 位元表示（十六進位）

   • A：最大非正規化數
     • sign = 0、exponent = 0x00、fraction = 全 1 → $0x007FFFFF$
   • B：最小正規化正數
     • sign = 0、exponent = 0x01、fraction = 0 → $0x00800000$
   • C = –2.25
     • 2.25 的二進位 = $10.01_2 = 1.001_2 \times 2^1$
     • sign = 1、biased exponent = $1+127 = 128 = 0x80$ → $\text{exp}=0x80$
     • fraction = 「001」後全 0 → $0x00100000$
     • 整體位元 = $0x80000000 + 0x40000000 + 0x00100000 = 0xC0100000$
   • D：正無限大
     • sign = 0、exponent = 0xFF、fraction = 0 → $0x7F800000$

2. 逐步 XOR

核心觀念

• 快取結構：16 個字 (word)容量、兩路組合相聯 (2‑way set associative)、每個區塊 2 個字。
  • 區塊數 = 16 / 2 = 8 塊。
  • 每組 (set) 2 塊 → 組數 = 8 / 2 = 4 組。
• 位元切割（以 word address 為單位）
  • 區塊位元 (offset) = $\log_2 2 = 1$ 位。
  • 組位元 (index) = $\log_2 4 = 2$ 位。
  • 標籤 (tag) = 其餘高位元。
• 映射公式
  • $\text{block\_num} = \left\lfloor\frac{\text{address}}{2}\right\rfloor$
  • $\text{set\_idx} = \text{block\_num} \bmod 4$
  • $\text{tag} = \left\lfloor\frac{\text{block\_num}}{4}\right\rfloor$
• 置換政策：LRU (Least Recently Used) 於兩路組合相聯的每組內獨立執行。

---

解題方法

1. 依序將每個存取位址換算成 block number、set index、tag。
2. 針對該 set 檢查目前快取內的兩個 block 是否已含相同 tag：
   • 若已有 → Hit，更新該組的 LRU 狀態。
   • 若沒有 → Miss，若組內尚有空位則直接塞入；若已滿則根據 LRU 驅除最舊的 block，再放入新 block。
3. 整個序列完成後統計命中次數 $K$，求 $K\ \bmod\ 5$。

以下以表格呈現每一步的計算與結果（ H = Hit、M = Miss）：

存取位址	block = ⌊addr/2⌋	set = block mod 4	tag = ⌊block/4⌋	快取狀態變化	命中?
12	6	2	1	M → set2: {1}	M
17	8	0	2	M → set0: {2}	M
18	9	1	2	M → set1: {2}	M
16	8	0	2	H (set0已有2)	H

核心觀念

• 流水線基本 CPI：在理想情況（無任何資料相依與分支衝突）下，流水線每條指令只佔 1 個時脈週期，即基礎 CPI = 1。
• 額外停頓週期：任何因相依或分支預測失誤而產生的氣泡，都會在平均 CPI 中累加「指令比例 × 停頓週期」的貢獻。
• 加權平均：$CPI = 1 + \sum_i (\text{比例}_i \times \text{每條指令額外週期}_i)$

解題方法

1. 列出每種指令的額外停頓
   • Load：$1/4$ 的 load 之後緊跟使用其結果的指令，需要 1 個週期 的 stall。

$\text{額外週期}_{\text{load}} = \frac14 \times 1 = 0.25$

• Branch：$50\%$ 的 branch 被錯誤預測，產生 1 個週期 的延遲。

$\text{額外週期}_{\text{branch}} = 0.5 \times 1 = 0.5$

• Jump：所有 jump 都必定產生 1 個週期 的延遲。

$\text{額外週期}_{\text{jump}} = 1 \times 1 = 1$

• Store、ALU：題目未提及任何停頓，視為 $0$。

2. 以指令混合比例加權

指令類型	比例	額外週期/指令	加權貢獻
Load	$24\% = 0.24$	$0.25$	$0.24 \times 0.25 = 0.06$
Store	$20\% = 0.20$	$0$	$0$
ALU	$30\% = 0.30$	$0$	$0$

核心觀念

1. Superscalar 與指令級平行 (ILP)
   • Superscalar 處理器同一個時脈週期內可發射多條指令，主要依賴硬體的 動態排程 (dynamic scheduling)、指令解碼 (multiple issue)、執行單元多元化，而非編譯器的靜態排程。
2. 快取 (Cache) 的概念
   • 快取是一種 暫存機制，用來減少對較慢層次記憶體的存取次數。快取的本質是「將較慢層次的資料暫存於較快層次」。
3. 頁表 (Page Table)
   • 虛擬記憶體系統中，頁表是一個 映射結構 (VPN → PPN)。每一次記憶體訪問若要轉譯，需要查詢頁表；因為查詢成本高，通常在硬體中加入 TLB 以快取近期的轉譯結果。
4. TLB (Translation Lookaside Buffer)
   • TLB 本質上是 頁表的快取，存放最近使用的虛擬頁號與實體頁框號的對應關係，屬於 地址轉譯快取。
5. 微程式控制 (Microprogramming)
   • 微程式化的控制單元以 微指令 方式實現指令的控制訊號。其優點是 可延伸性、易於修改，但因需逐條執行微指令，速度較 硬體直接編碼 (hard‑wired control) 慢。

---

解題方法
本題為多選題，重點在於辨識每個敘述是否符合上述概念。對每個選項直接比對其描述與正確定義，若敘述與概念相符即為 True，否則 False。

---

選項分析

選項	判斷	理由
(A) Superscalar machines mainly rely on hardware to achieve instruction‑level parallelism.	True	Superscalar 依賴硬體結構（多發射單元、動態排程、分支預測、寫入背壓等）來同時執行多條指令。編譯器的靜態排程只能提供有限幫助，主要平行度仍由硬體決定。

核心觀念

• 單循環 (single‑cycle) CPU：每條指令在同一個時脈週期內完成。時脈週期長度必須足以容納最慢指令的全部微操作路徑。
• 多循環 (multi‑cycle) CPU：指令被切分成多個微操作，每個微操作佔一個時脈週期。時脈週期長度只受最慢 微操作（而非最慢整條指令）限制。
• 時脈頻率 (clock rate)：$f = \frac{1}{T_{\text{cycle}}}$，$T_{\text{cycle}}$ 為時脈週期。
• CPI (Cycles Per Instruction)：平均每條指令需要的時脈週期數。單循環 CPU 的 CPI 恒為 1。
• 吞吐量 (throughput)：單位時間內完成的指令數，公式 $\text{Throughput}= \frac{f}{\text{CPI}}$。

---

解題方法
逐一檢視每個敘述，套用上述概念與公式判斷其真偽。若涉及比較（如時脈頻率或吞吐量），以「最慢的微操作」與「最慢的指令」的差異作為關鍵判斷點。

---

選項分析

選項	判斷	理由
(A) The clock rate of the multiple‑cycle CPU design is larger than single‑cycle CPU design.	✅ 正確	多循環 CPU 的時脈週期只需容納最慢 微操作，通常遠小於需容納最慢整條指令的單循環 CPU 時脈週期，因而得到較高的時脈頻率 $f_{\text{multi}} > f_{\text{single}}$。

核心觀念

1. Superscalar 與指令級平行 (ILP)
   • Superscalar 處理器同一個時脈週期內可發射多條指令，主要依賴硬體的 動態排程 (dynamic scheduling)、指令解碼 (multiple issue)、執行單元多元化，而非編譯器的靜態排程。
2. 快取 (Cache) 的概念
   • 快取是一種 暫存機制，用來減少對較慢層次記憶體的存取次數。快取的本質是「將較慢層次的資料暫存於較快層次」。
3. 頁表 (Page Table)
   • 虛擬記憶體系統中，頁表是一個 映射結構 (VPN → PPN)。每一次記憶體訪問若要轉譯，需要查詢頁表；因為查詢成本高，通常在硬體中加入 TLB 以快取近期的轉譯結果。
4. TLB (Translation Lookaside Buffer)
   • TLB 本質上是 頁表的快取，存放最近使用的虛擬頁號與實體頁框號的對應關係，屬於 地址轉譯快取。
5. 微程式控制 (Microprogramming)
   • 微程式化的控制單元以 微指令 方式實現指令的控制訊號。其優點是 可延伸性、易於修改，但因需逐條執行微指令，速度較 硬體直接編碼 (hard‑wired control) 慢。

---

解題方法
本題為多選題，重點在於辨識每個敘述是否符合上述概念。對每個選項直接比對其描述與正確定義，若敘述與概念相符即為 True，否則 False。

---

選項分析

選項	判斷	理由
(A) Superscalar machines mainly rely on hardware to achieve instruction‑level parallelism.	True	Superscalar 依賴硬體結構（多發射單元、動態排程、分支預測、寫入背壓等）來同時執行多條指令。編譯器的靜態排程只能提供有限幫助，主要平行度仍由硬體決定。

核心觀念

• 單循環 (single‑cycle) CPU：每條指令在同一個時脈週期內完成。時脈週期長度必須足以容納最慢指令的全部微操作路徑。
• 多循環 (multi‑cycle) CPU：指令被切分成多個微操作，每個微操作佔一個時脈週期。時脈週期長度只受最慢 微操作（而非最慢整條指令）限制。
• 時脈頻率 (clock rate)：$f = \frac{1}{T_{\text{cycle}}}$，$T_{\text{cycle}}$ 為時脈週期。
• CPI (Cycles Per Instruction)：平均每條指令需要的時脈週期數。單循環 CPU 的 CPI 恒為 1。
• 吞吐量 (throughput)：單位時間內完成的指令數，公式 $\text{Throughput}= \frac{f}{\text{CPI}}$。

---

解題方法
逐一檢視每個敘述，套用上述概念與公式判斷其真偽。若涉及比較（如時脈頻率或吞吐量），以「最慢的微操作」與「最慢的指令」的差異作為關鍵判斷點。

---

選項分析

選項	判斷	理由
(A) The clock rate of the multiple‑cycle CPU design is larger than single‑cycle CPU design.	✅ 正確	多循環 CPU 的時脈週期只需容納最慢 微操作，通常遠小於需容納最慢整條指令的單循環 CPU 時脈週期，因而得到較高的時脈頻率 $f_{\text{multi}} > f_{\text{single}}$。

核心觀念

本題評量 MIPS 五級管線（Pipeline: IF, ID, EX, MEM, WB）中的資料相依性（Data Dependency）、資料冒險（Data Hazard）及其解決機制（Forwarding / Bypassing 與 Stalling / Bubble）。

1. 資料冒險類型：

   • RAW (Read-After-Write，真實相依性 True Dependency)：後續指令需讀取前面指令所寫入的目的暫存器。若後續指令在資料尚未寫回前就嘗試讀取，即會讀到舊值。
   • WAR (Write-After-Read，反相依性 Anti-Dependency)：後續指令寫入目的暫存器的時間早於前面指令讀取該暫存器的時間。
   • WAW (Write-After-Write，輸出相依性 Output Dependency)：後續指令寫入目的暫存器的時間早於前面指令寫入相同暫存器的時間，導致最後留下的值錯誤。
     註：在標準五級循序（In-order）管線架構中，指令皆按順序讀取暫存器（ID 階段）與寫回暫存器（WB 階段），因此僅會發生 RAW 冒險，不可能發生 WAR 或 WAW 冒險。

2. 資料前向傳遞（Data Forwarding / Bypassing）：

   • 當前一道指令的運算結果已經在硬體內部產生（例如 ALU 運算於 EX 階段結束時已產出結果），可直接透過內部旁路（Bypass Network）拉線將結果傳送給下一道指令的 ALU 輸入端，無需等待資料寫回暫存器檔案（Register File），從而完全消除因 RAW 產生的氣泡（Bubble）。

---

解題方法

1. 暫存器讀寫分析

MIPS R-type 指令的組合語言格式為：op rd, rs, rt（rd 為目的暫存器 Destination Register，rs 與 rt 為來源暫存器 Source Registers）。

• 第一道指令 $I_1$：add $s0, $t0, $t1
  • 寫入暫存器（Write / Destination）：$s0
  • 讀取暫存器（Read / Sources）：$t0, $t1
• 第二道指令 $I_2$：sub $t2, $s0, $t3
  • 寫入暫存器（Write / Destination）：$t2
  • 讀取暫存器（Read / Sources）：$s0, $t3

2. 相依性與冒險判定

• RAW 判定：$I_2$ 需讀取 $s0$，而 $s0$ 正是由前一道指令 $I_1$ 所計算並準備寫入的目標。因此兩者在暫存器 $s0$ 上存在 RAW 資料相依性，若無防護措施將導致 RAW Hazard。
• WAW 判定：$I_1$ 寫入 $s0$，而 $I_2$ 寫入 $t2$。