108 年 國立暨南國際大學資訊工程學系碩士班《計算機結構與作業系統》

核心觀念

本題考核作業系統（Operating Systems）中虛擬記憶體（Virtual Memory）之**有效記憶體存取時間（Effective Access Time, EAT）**模型。

當系統採用分頁機制（Demand Paging）時，記憶體存取可能發生分頁命中（Page Hit）或分頁錯誤（Page Fault）。若發生 Page Fault，作業系統必須中斷目前行程、進行磁碟 I/O 置換分頁，並更新頁表（Page Table），此處理時間即為分頁錯誤服務時間（Page Fault Service Time）。

其標準計算公式如下：

$$\text{EAT} = (1 - p) \times \text{MAT} + p \times S$$

• $p$：分頁錯誤率（Page Fault Rate）。
• $\text{MAT}$：正常情況下的記憶體存取時間（Memory Access Time）。
• $S$：分頁錯誤服務時間（Page Fault Service Time）。
• 註：在部分教科書定義中，若發生分頁錯誤時仍需加上一次額外的正常記憶體存取時間，公式寫為 $\text{EAT} = \text{MAT} + p \times S$ 或 $\text{EAT} = (1-p) \times \text{MAT} + p \times (\text{MAT} + S)$。然而在實際運算中，因為 $S$ 通常為毫秒（ms）等級，遠大於奈秒（ns）等級的 $\text{MAT}$，且 $p \ll 1$（本題 $p = 2.5 \times 10^{-6}$），這兩類形式的數值差異微乎其微。本解法採 Silberschatz《Operating System Concepts》經典標準定義進行精確推導。

---

解題方法與推導

1. 整理已知數值

• 記憶體存取時間 $\text{MAT} = 200\text{ ns}$
• 分頁錯誤率 $p = 0.0000025 = 2.5 \times 10^{-6}$
• 限制條件：有效記憶體存取時間 $\text{EAT} \le 210\text{ ns}$
• 欲求解之變數：最大分頁錯誤服務時間 $S_{\max}$

2. 代入公式建立不等式

$$(1 - p) \times \text{MAT} + p \times S \le 210$$

將數值代入：

$$(1 - 0.0000025) \times 200 + 0.0000025 \times S \le 210$$

展開並簡化左式：

$$200 - (0.0000025 \times 200) + 0.0000025 \times S \le 210$$

計算常數乘積：

$$0.0000025 \times 200 = 0.0005\text{ ns}$$

核心觀念

本題考查作業系統虛擬記憶體管理中**分頁機制（Paging）**的基本位址轉換與分頁表結構：

1. 邏輯位址結構（Logical Address Structure）：
   在單層分頁架構下，邏輯位址（Logical Address）由兩部分組成：

   • 分頁編號（Page Number, $p$）：用來索引分頁表（Page Table）。
   • 分頁位移（Page Offset, $d$）：用來指出該分頁內的具體位元組偏移量。

2. 分頁大小與位移位元數：
   若分頁大小（Page Size）為 $2^k$ 位元組，則分頁位移佔用 $k$ 個位元（bits）。

3. 分頁表項目數（Number of Page Table Entries, PTEs）：
   分頁表必須能映射邏輯位址空間中的每一個分頁，因此分頁表中的項目數（Number of Entries）等於邏輯位址空間所包含的總分頁數（Total Number of Pages）：

   $$\text{Number of Entries} = 2^p = \frac{\text{Logical Address Space Size}}{\text{Page Size}}$$

---

解題步驟與推導

1. 計算分頁位移所佔位元數（$d$）：
   題目給定分頁大小為 $1\text{ KB} = 1024\text{ Bytes} = 2^{10}\text{ Bytes}$。
   因此，位移欄位佔用位元數為： $$d = \log_2(1024) = 10\text{ bits}$$

核心觀念

本題的核心觀念為分頁機制（Paging Mechanism）下的位址轉換與分頁表結構（Page Table Structure）：

1. 邏輯位址與物理位址分割：
   • 頁面大小（Page Size）為 $S = 2^d$ Bytes，則位移量（Offset / $d$）的位元數由頁面大小唯一決定，且無論在邏輯位址還是物理位址中，Offset 欄位的寬度皆相同。
   • 邏輯位址（Logical Address, $m$ bits）：拆分為頁號（Page Number, $p$）與頁內位移（Page Offset, $d$），其中 $m = p + d$。
   • 物理位址（Physical Address, $n$ bits）：拆分為框號（Frame Number, $f$）與框內位移（Frame Offset, $d$），其中 $n = f + d$。
2. 分頁表的作用與內部項目（Page Table Entry, PTE）：
   • 分頁表負責將「邏輯頁號 $p$」對應到「物理框號 $f$」。
   • 分頁表項目數量（Number of Entries）取決於邏輯位址空間的大小，即 $2^p$ 個項目。
   • 每個分頁表項目（PTE）的寬度至少必須能容納目標的物理框號（Frame Number, $f$ bits），外加相關控制位元（如 Valid/Invalid bit、Dirty bit、Reference bit 等）。

---

解題方法與詳細推導

1. 位移量（Offset）位元數計算

給定頁面大小為 $1\text{ KB} = 1024\text{ Bytes} = 2^{10}\text{ Bytes}$：

$$d = 10\text{ bits}$$

2. 原系統架構（修改前）

• 邏輯位址寬度：$16\text{ bits}$
  • 邏輯頁號位元數：$p = 16 - 10 = 6\text{ bits}$
  • 分頁表項目個數：$2^6 = 64\text{ entries}$
• 物理位址寬度：$16\text{ bits}$
  • 物理框號位元數：$f_{\text{old}} = 16 - 10 = 6\text{ bits}$
  • 每個 PTE 中儲存的 Frame Number 欄位至少需 $6\text{ bits}$。

3. 新系統架構（修改後）

• 邏輯位址寬度仍為 $16\text{ bits}$：
  • 邏輯頁號位元數維持 $p = 6\text{ bits}$，故分頁表項目總數保持不變（仍為 $64$ 個項目）。

核心觀念

本題的核心考點為 UNIX/Linux 系統呼叫 fork() 的運作機制以及其在迴圈（while）中的衍生行為：

1. fork() 的回傳值與分流機制：
   • 在**子行程（Child Process）**中，fork() 回傳 0。
   • 在父行程（Parent Process）中，fork() 回傳子行程的 PID（非零正整數）。
   • 因此，執行 if (fork() == 0) 時，子行程會進入 if 區塊（執行 k += 1;），而父行程會進入 else 區塊（執行 k += 2;）。
2. 行程空間獨立性：
   • fork() 呼叫後，子行程複製父行程的虛擬記憶體位址空間（包含變數 k、程式計數器 PC 等）。
   • 隨後父行程與子行程各自獨立執行，修改自己空間中的 k 不會互相干擾（Copy-on-Write）。
3. 終止條件判斷：
   • 迴圈條件為 while (k < 2)。一旦某行程的 $k \ge 2$，該行程便會跳出迴圈並結束，不再產生新的子行程。

---

解題方法與詳細推導

我們採用**行程樹（Process Tree / Execution Trace）**來追蹤每個行程的狀態與執行流程。

假設初始行程記為 $P_0$，起始狀態為 $k = 0$。

第一輪迴圈（Round 1）：

所有進入此輪的行程必須滿足 $k < 2$。
此時只有初始行程 $P_0$（$k = 0 < 2$），開始執行：

1. $P_0$ 呼叫 fork()，產生一個全新的子行程，記為 $P_1$。
2. 剛複製完成時，兩者繼承的環境均為 $k = 0$。
3. 根據 fork() 回傳值進行分流：
   • 子行程 $P_1$：fork() == 0 成立，執行 k += 1;，此時 $P_1$ 的 $k = 0 + 1 = 1$。
   • 父行程 $P_0$：fork() == 0 不成立，執行 k += 2;，此時 $P_0$ 的 $k = 0 + 2 = 2$。
4. 第一輪結束後回到 while (k < 2) 檢查：
   • 父行程 $P_0$：$k = 2 \not< 2$，條件不成立，離開迴圈並結束。
   • 子行程 $P_1$：$k = 1 < 2$，條件仍成立，繼續進入第二輪迴圈。

第二輪迴圈（Round 2）：

此輪只有 $P_1$（$k = 1$）進入執行：

1. $P_1$ 呼叫 fork()，產生另一個子行程，記為 $P_2$。
2. 剛複製完成時，兩者繼承的環境均為 $k = 1$。
3. 根據 fork() 回傳值進行分流：

核心觀念

本題測驗作業系統中**雙重模式運作（Dual-Mode Operation）與特權指令（Privileged Instructions）**的劃分準則。

作業系統為了保護系統與各個行程（Process）不受惡意或錯誤程式干擾，硬體通常提供至少兩種執行模式：

• 使用者模式（User Mode）：執行一般使用者行程，指令集受限。
• 核心模式／監督者模式（Kernel Mode / Supervisor Mode）：執行作業系統核心，可執行所有機器指令。

特權指令的定義：任何可能危害系統安全、破壞系統運作或干擾其他行程的指令，皆必須被指定為特權指令，僅能在核心模式下執行；若使用者模式嘗試執行特權指令，硬體將發出 Trap（例外處理）交由作業系統接管。

---

解題方法

判斷某個指令是否為特權指令，切入點在於**「該操作是否具潛在破壞性或安全性威脅」**：

1. 讀取時鐘（Read the clock）：
   • 使用者應用程式頻繁需要知道目前時間（例如效能評測、日誌紀錄、顯示時間等）。
   • 單純讀取時鐘（Read-only）不會更改系統狀態，不會損害硬體，也不會破壞其他行程的執行環境。
   • 因此，「讀取時鐘」是無害的非特權操作（Non-privileged），使用者程式可直接執行（或透過非破壞性的方式取得）。
2. 修改時鐘（Set / Modify the clock）：
   • 若允許使用者隨意更動系統時間，可能導致排程混亂、計費出錯、安全憑證過期失效或日誌時序錯亂，嚴重威脅系統正常運作。
   • 因此，「設定時鐘（Set the clock）」才必須是特權指令（Privileged Instruction）。

---

核心觀念

1. Trap（陷阱／軟體中斷）：由軟體指令或程式執行錯誤所觸發的同步事件（Synchronous event）。最常見的應用是系統呼叫（System Call），讓處於 User Mode（使用者模式）的應用程式能夠主動請求作業系統核心（OS Kernel）提供特權服務（如 I/O 操作、建立行程等）。
2. 特權指令（Privileged Instruction）與非特權指令（Non-privileged Instruction）：
   • Privileged Instruction：只能在 Kernel Mode（特權模式）下執行的指令。若在 User Mode 下執行會引發 CPU 例外並被攔截（如清空記憶體映射暫存器、切換 CPU Mode Bit、關閉中斷 CLI、直接存取硬體 I/O 等）。
   • Non-privileged Instruction：在 User Mode 與 Kernel Mode 下皆可合法執行的指令（如算術運算、載入／儲存資料、跳躍指令等）。
3. Dual-Mode Operation（雙重模式運作機制）：為了系統安全與保護，硬體區分 User Mode 與 Kernel Mode。由 User Mode 切換至 Kernel Mode 的主要途徑正是透過 Interrupt、Fault 或軟體觸發的 Trap。

---

解題方法

本題切入點在於**「誰需要發出 Trap 指令？以及發出時系統處於何種模式？」**：

• 觸發 Trap 的指令（例如 x86 的 INT n / SYSENTER / SYSCALL、ARM 的 SVC / SWI、MIPS 的 syscall）之根本目的，是允許執行於 User Mode 下的應用程式主動向核心發出請求。

核心觀念

1. LRU（Least Recently Used）分頁置換演算法：
   • 核心假設為「局部性原理（Principle of Locality）」，特別是「時間局部性（Temporal Locality）」，即最近被存取過的分頁在不久的將來最有可能再次被存取；相對地，最久未被存取的分頁未來被使用的機率最低。
   • LRU 屬於 堆疊演算法（Stack Algorithm），理論上不會發生 Belady's Anomaly（即配置較多頁框時，分頁錯誤率保證不會增加）。
2. LRU 的最差情況（Worst-case Scenario）：
   • LRU 並非「在所有存取模式下」都表現優異（does not always perform well）。
   • 當工作負載為循環式存取（Sequential Flooding / Cyclic Reference Pattern），且循環中的分頁數 $N$ 大於實體頁框數 $M$（即 $N = M + 1$）時，LRU 會退化為最差情況，導致每一次存取都發生分頁錯誤（Page Fault Rate $= 100\%$）。

---

解題方法

本題為是非判斷題（Yes / No）。題幹宣稱「LRU 分頁置換演算法**總是（always）**表現良好」。要證明該敘述為偽（No），只需提出一個明確的反例（Counterexample）：

假設系統配置 $M = 3$ 個頁框（Frame），存取序列為大小為 $4$（即 $N = M + 1$）的循環存取序列：
$1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4, \dots$

追蹤 LRU 置換過程：

1. 存取 $1, 2, 3$：發生 $3$ 次 Page Fault，頁框內容為 $[1, 2, 3]$。
2. 存取 $4$：發生 Page Fault，替換最久未用的 $1$，頁框內容變為 $[2, 3, 4]$。
3. 存取 $1$：發生 Page Fault，替換最久未用的 $2$，頁框內容變為 $[3, 4, 1]$。

核心觀念

本題考察作業系統與計算機結構跨領域的核心觀念：內文切換（Context Switch）對快取記憶體（Cache）效能的衝擊。

1. Context Switch（內文切換）的成本構成：
   • Direct Overhead（直接開銷）：儲存舊 Process 的暫存器狀態（PCB）、載入新 Process 的狀態、更新記憶體管理單元（MMU）暫存器（如更新 Page Directory 暫存器 CR3 或重設 PCID）等。此部分為確定且相對短暫的 CPU 指令週期。
   • Indirect Overhead（間接開銷）：切換 Process 後對快取記憶體（CPU Cache）、TLB（Translation Lookaside Buffer）與分支預測器（Branch Predictor）所造成的局部性破壞。
2. 快取污染與冷啟動效應（Cache Pollution & Cold Misses）：
   • 當 CPU 從 Process A 切換至 Process B 時，Cache 內原先充滿 Process A 的工作集（Working Set）。
   • Process B 開始執行時，原有的資料局部性（Locality of Reference）瞬間失效，產生大量 Cold Start Misses（冷啟動不命中） 或 Capacity/Conflict Misses。
   • 當一段時間後又切換回 Process A，Process A 原本載入好的 Cache 行已被 Process B 驅逐（Evict），Process A 必須重新從慢速主記憶體（DRAM）中抓取資料，大幅降低快取的命中率（Hit Rate），拉長平均記憶體存取時間（Average Memory Access Time, AMAT）。

---

解題方法

判斷內文切換是否會影響快取效能，可從記憶體階層架構的 AMAT 公式進行推導分析：

$$\text{AMAT} = \text{Hit Time} + (\text{Miss Rate} \times \text{Miss Penalty})$$

• 頻繁發生 Context Switch 會導致快取內有效資料不斷被置換。
• 對新排班執行的 Process 而言，短期內的 $\text{Miss Rate}$ 會顯著上升。

核心觀念

本題考查計算機結構中著名的歷史經驗法則——**摩爾定律（Moore's Law）**的精確定義與內涵。

1. 摩爾定律（Moore's Law）：由英特爾（Intel）聯合創始人戈登·摩爾（Gordon Moore）於 1965 年提出（並於 1975 年修正），其核心內容為：「積體電路（IC）上所能容納的電晶體數量（number of transistors），大約每 18 至 24 個月（早期論文為每 12 個月，後修正為每兩年）會增加一倍」，晶片效能也隨之呈指數型成長。
2. 功耗問題（Power Wall）：
   • 摩爾定律陳述的是電晶體集成密度，而非晶片的耗電量（Power Consumption）。
   • 早期遵循**登納德縮放定律（Dennard Scaling）**時，隨著電晶體尺寸縮小，單位面積功耗大致保持恆定（電壓與電流等比例縮小）。
   • 當登納德縮放失效後，處理器功耗急遽增加，觸碰到所謂的「功耗牆（Power Wall）」，促使架構轉向多核心發展。若功耗真如題目所述每年翻倍，晶片將迅速產生極端高溫而無法運作。

---

解題方法

比對題幹敘述與摩爾定律的標準定義：

• 題目敘述：「摩爾定律指出，晶片的功耗每年會翻倍（the power consumption of a chip doubles every year）。」
• 摩爾定律描述的物理量是晶片上的電晶體數量（number of transistors），翻倍的週期普遍定義為約 18 至 24 個月（或約 2 年），完全不是指「晶片的功耗（power consumption）」。
• 因此，此敘述混淆了「電晶體數量」與「晶片功耗」，為明顯的錯誤觀念。

---

核心觀念

本題測驗計算機組織的基本架構分類——**范紐曼架構（Von Neumann Architecture）與哈佛架構（Harvard Architecture）**的定義及其在現代計算系統中的實際應用：

1. 范紐曼架構（儲存程式概念，Stored-Program Concept）：
   • 程式指令與資料共用同一個記憶體位址空間（Unified Memory），並透過同一組系統匯流排（Bus）傳輸。
   • 硬體設計相對簡單、彈性高，但容易受限於指令與資料無法同時存取所產生的「范紐曼瓶頸（Von Neumann Bottleneck）」。
2. 哈佛架構（Harvard Architecture）：
   • 指令記憶體（Instruction Memory）與資料記憶體（Data Memory）在實體上完全分離，擁有各自獨立的位址與資料匯流排，允許管線化中同時進行指令擷取（IF）與資料存取（MEM）。
3. 現代處理器設計（Modified Harvard Architecture）：
   • 現代個人電腦（如 x86/x64 架構）與智慧型手機（如 ARM 架構），在晶片內部階層採用分開的 L1 指令快取（L1 I-Cache）與 L1 資料快取（L1 D-Cache）來消除管線結構衝突（屬於改良型哈佛架構）。
   • 然而在晶片外部與系統記憶體（Main Memory / DRAM）階層，程式與資料皆存放於統一的共享記憶體空間中，本質上仍然屬於范紐曼架構（Stored-Program Computer）的範疇。

---

解題方法

從「計算機體系結構的巨觀分類」切入：

• 在電腦科學與研究所考試的定義中，只要系統採用「指令與資料存放在同一主記憶體、由 CPU 讀取並執行」的通用計算機制，該系統即被歸類為范紐曼架構或儲存程式電腦。

核心觀念

本題的核心觀念在於管線化（Pipelining）對單一指令執行時間（Latency）與整體吞吐量（Throughput）的影響，以及管線暫存器帶來的額外開銷（Pipeline Overhead）。

1. 延遲（Latency） vs. 吞吐量（Throughput）：

   • 管線化技術的核心目的在於提高指令層級的平行度（ILP），藉此增加處理器在單位時間內完成的指令數量（即提高 Throughput）。
   • 管線化不會縮短個別指令的執行時間（Latency / Execution Time）；相反地，單一指令的執行時間往往會持平或變長。

2. 單一指令執行時間公式：
   若將指令的執行切分成 $k$ 個管線級數（Stages），假設原先非管線化架構下該指令的總邏輯延遲為 $T_{\text{logic}}$，管線化後的單一指令執行時間為：

   $$\text{Execution Time of Single Instruction} = k \times \tau$$

   其中 $\tau$ 為管線的時脈週期時間（Clock Cycle Time），決定於最慢的階段延遲加上管線暫存器的建立與傳遞開銷（Register Overhead, $d_{\text{reg}}$）：

   $$\tau = \max(T_{\text{stage}_1}, T_{\text{stage}_2}, \dots, T_{\text{stage}_k}) + d_{\text{reg}}$$

---

解題方法

比較「管線級數較多（$k$ 較大）」與「管線級數較少或無管線」時，單一指令（Single Instruction）的執行時間變化：

1. 管線切割不平衡（Stage Imbalance）：
   當級數 $k$ 增加時，各階段的邏輯延遲很難被完全均分。時脈週期 $\tau$ 必須以「最長階段（Bottleneck Stage）」為準，因此 $k \times \tau > T_{\text{logic}}$，且切得愈細，不平衡造成的浪費通常愈顯著。
2. 暫存器延遲開銷（Pipeline Overhead）：

核心觀念

本題考查管線化處理器（Pipelined Processor）中的管線危障（Pipeline Hazards）及其解決機制（Hazard Resolution Techniques）。

1. 管線危障（Pipeline Hazard）：指在管線執行過程中，下一條指令因某種原因無法在下一個時脈週期如期執行。危障主要分為三類：
   • 結構危障（Structural Hazard）：硬體資源衝突（例如同時存取單一記憶體）。
   • 資料危障（Data Hazard）：指令間存在資料相依性（RAW、WAR、WAW），資料尚未產出。
   • 控制危障（Control Hazard）：分支指令目標位址或條件尚未確定，無法決定下一條要擷取的指令。
2. 管線停頓（Pipeline Stall / Bubble）：為消除危障而強制讓管線凍結一個或多個週期的處置手段。
3. 消除危障不必然需要停頓（Stall）：
   • 資料危障可藉由**轉發／旁路（Forwarding / Bypassing）**技術直接將運算結果傳至下一條指令，不需插入停頓。
   • 資料危障亦可透過編譯器進行**指令重排（Code Scheduling）**填補延遲槽，消除停頓。
   • 控制危障可藉由分支預測（Branch Prediction）與延遲分支（Delayed Branch），在預測成功或排程成功時完全不停頓。

---

解題方法

題幹敘述為「Pipeline hazards surely cause pipeline stalls.」（管線危障必定會導致管線停頓）。

分析切入點在於副詞 「surely」（必定／必然）：

• 只要能舉出「存在管線危障，但能透過硬體或軟體技術化解，而不產生任何 stall」的反例，該敘述即為錯誤（False）。
• 在典型五級 MIPS 管線中：

核心觀念

1. 延遲（Latency / Response Time）與產能（Throughput / Bandwidth）的區別：
   • 延遲（Latency）：完成單一特定任務（Job / Task）所需的時間（例如：執行時間 Execution Time）。
   • 產能（Throughput）：單位時間內系統所能完成的工作總量。
2. 阿姆達爾定律（Amdahl's Law）與並行性極限：
   • 若一項工作具備可並行化的部分（Fraction enhanced/parallelized 為 $f$），則使用 $N$ 個資源加速時的加速比（Speedup）為： $$S = \frac{1}{(1 - f) + \frac{f}{N}}$$
   • 當工作「完全無法被並行化」（strictly sequential / inherently serial，即 $f = 0$）時，不論增加多少資源（$N \to \infty$），加速比永遠為： $$S = \frac{1}{(1 - 0) + 0} = 1$$ 這代表該工作的執行時間（Latency）無法透過增加重複資源而獲得縮減。
3. 重複資源（Duplicate Resources / Replicated Hardware）的角色：
   • 增加重複資源（例如增加相同的 CPU 核心、伺服器或工作站）主要用來提升系統整體的「產能」（Throughput），或降低多個任務排隊時的「等待時間」（Queueing Time）。但對於「單一、正在執行且無法切割並行的工作」本身，其服務時間（Service Latency）完全由其內部循序指令鏈（Critical Path）決定，增加多餘的計算節點無法加快其運算速度。

---

解題方法

題目敘述為：

"Adding duplicate resources must be able to reduce latency of a job that cannot be parallelized."

切入點如下：

1. 題幹明確指定該工作為 "cannot be parallelized"（無法被並行化）。
2. 根據 Amdahl's Law，完全循序（Sequential）的工作無法將運算分散至多個相同的硬體資源上執行。

核心觀念

評估計算機系統的「效能」（Performance），最基本且核心的準則為程式執行時間（CPU Execution Time）。效能與執行時間成反比：

$$\text{Performance} = \frac{1}{\text{Execution Time}}$$

根據經典的 CPU 效能公式（CPU Performance Equation）：

$$\text{CPU Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time} = \frac{\sum (\text{IC}_i \times \text{CPI}_i)}{\text{Clock Rate}}$$

其中：

• $\text{IC}_i$：第 $i$ 類指令的執行數量（Instruction Count）。
• $\text{CPI}_i$：第 $i$ 類指令平均所需的時脈週期數（Clock Cycles per Instruction）。
• 總時脈週期數 $\text{CPU Clock Cycles} = \sum_{i} (\text{IC}_i \times \text{CPI}_i)$。

在題目未特別提及時脈頻率（Clock Rate / 時脈週期時間）改變的前提下，預設兩項改良方案的時鐘頻率相同。因此，總時脈週期數愈少，執行時間愈短，系統效能愈高。

---

解題方法

計算原始系統、改良方案 Alpha 與改良方案 Beta 的總執行週期數（Total Clock Cycles），並比較兩者的執行時間與加速比（Speedup）。

1. 原始系統（Original Baseline）之總週期數

依題意表格資料：

• Type A：$\text{IC}_A = 1\text{M}$，$\text{CPI}_A = 2$
• Type B：$\text{IC}_B = 0.5\text{M}$，$\text{CPI}_B = 1$
• Type C：$\text{IC}_C = 0.5\text{M}$，$\text{CPI}_C = 3$

$$\text{Cycles}_{\text{orig}} = (1\text{M} \times 2) + (0.5\text{M} \times 1) + (0.5\text{M} \times 3) = 2.0\text{M} + 0.5\text{M} + 1.5\text{M} = 4.0\text{M cycles}$$

2. 改良方案 Alpha 之總週期數

• 條件變更：Type C 的 $\text{IC}_C$ 由 $0.5\text{M}$ 降至 $0.1\text{M}$，$\text{CPI}_C$ 由 $3$ 降至 $1.5$；其餘指令類型不變。
• Type A：$1\text{M} \times 2 = 2.0\text{M cycles}$
• Type B：$0.5\text{M} \times 1 = 0.5\text{M cycles}$
• Type C：$0.1\text{M} \times 1.5 = 0.15\text{M cycles}$

$$\text{Cycles}_{\text{Alpha}} = 2.0\text{M} + 0.5\text{M} + 0.15\text{M} = 2.65\text{M cycles}$$

相較於原始設計之加速比（Speedup）：

核心觀念

本題評估電腦系統效能與能耗（Energy Consumption）的關係，涉及計算機結構的經典效能公式與能耗公式：

1. CPU 執行週期數（Total Clock Cycles, $\text{CPU Cycles}$）：
   若指令集包含多種不同型態的指令，總執行週期數為各指令型態之指令數（Instruction Count, $\text{IC}$）與其個別每指令週期數（Cycles Per Instruction, $\text{CPI}$）乘積的總和：

   $$\text{CPU Cycles} = \sum_{i} (\text{IC}_i \times \text{CPI}_i)$$

2. CPU 執行時間（CPU Execution Time, $T$）：

   $$T = \text{CPU Cycles} \times T_c = \frac{\text{CPU Cycles}}{f}$$

   其中 $T_c$ 為時脈週期（Clock Cycle Time），$f$ 為時脈頻率（Clock Frequency）。在題目未特別提及更改時脈週期或頻率的前提下，預設 $T_c$ 為固定常數。

3. 能耗（Energy Consumption, $E$）：
   能耗為平均功率（Average Power, $P$）與執行時間（$T$）之乘積：

   $$E = P \times T = P \times \text{CPU Cycles} \times T_c$$

   評估不同改良方案的能耗優劣時，能耗越低（消耗能量越少）的方案越佳。

---

解題方法

比較改良方案 Alpha 與 Beta 的總能耗，依下列步驟推導：

步驟一：計算原始系統（Original）的總週期數與相對能耗

• 各指令型態週期數：
  • Type A：$1\text{ M} \times 2 = 2.0\text{ M cycles}$
  • Type B：$0.5\text{ M} \times 1 = 0.5\text{ M cycles}$
  • Type C：$0.5\text{ M} \times 3 = 1.5\text{ M cycles}$
• 總週期數： $$\text{Cycles}_{\text{orig}} = 2.0\text{ M} + 0.5\text{ M} + 1.5\text{ M} = 4.0\text{ M cycles}$$
• 平均功率 $P_{\text{orig}} = 20\text{ W}$，故能耗為： $$E_{\text{orig}} = 20\text{ W} \times 4.0\text{ M} \times T_c = 80.0\text{ M} \cdot T_c \text{ Joules}$$

步驟二：計算方案 Alpha 的總週期數與能耗

• 題目條件：Type C 的 $\text{IC}$ 由 $0.5\text{ M}$ 降為 $0.1\text{ M}$，$\text{CPI}$ 由 $3$ 降為 $1.5$；其餘維持不變；平均功率增至 $30\text{ W}$。
• 各指令型態週期數：
  • Type A：$1\text{ M} \times 2 = 2.0\text{ M cycles}$
  • Type B：$0.5\text{ M} \times 1 = 0.5\text{ M cycles}$
  • Type C：$0.1\text{ M} \times 1.5 = 0.15\text{ M cycles}$
• 總週期數： $$\text{Cycles}_{\alpha} = 2.0\text{ M} + 0.5\text{ M} + 0.15\text{ M} = 2.65\text{ M cycles}$$
• 平均功率 $P_{\alpha} = 30\text{ W}$，故能耗為： $$E_{\alpha} = 30\text{ W} \times 2.65\text{ M} \times T_c = 79.5\text{ M} \cdot T_c \text{ Joules}$$

核心觀念

1. 流水線冒險（Pipeline Hazard）的定義：
   在管線化處理器（Pipelined Processor）中，因某些狀況導致下一條指令無法在下一個時脈週期（Clock Cycle）順利執行，而使流水線發生停頓（Stall / Bubble）的現象。
2. 資料冒險（Data Hazard）：
   管線中重疊執行的指令之間存在資料相依性（Data Dependency），而後續指令所需的運算元（Operand）尚未由先前的指令計算完成或寫回暫存器，導致後續指令讀取到舊值或錯誤資料的情況。
3. 資料相依的類型：
   • RAW（Read After Write，真相依／True Dependence）：指令 $j$ 嘗試在指令 $i$ 寫入暫存器之前讀取該暫存器。這是標準循序執行管線（如經典 MIPS 5-stage pipeline）中最常見的 Data Hazard。
   • WAR（Write After Read，反相依／Anti-dependence）：指令 $j$ 嘗試在指令 $i$ 讀取之前覆寫該目標暫存器（多發生於亂序執行管線）。
   • WAW（Write After Write，輸出相依／Output Dependence）：指令 $j$ 嘗試在指令 $i$ 寫入之前覆寫相同目標暫存器，造成最後寫入順序顛倒（多發生於亂序執行管線）。

---

解題方法

本題要求解釋「Data Hazard」，答題時應從本質定義出發，結合題幹所給的組合語言程式碼作為實例佐證，並簡要提及解決方案以展現答案的完整性：

1. 文字定義：說明何謂 Data Hazard（因指令間有資料相依，執行管線重疊時發生讀寫時序衝突）。
2. 實例說明（結合題幹指令）：
   • 觀察題幹指令：

     I1: lw    R1, 0(R2)     # 於 WB 階段將記憶體資料寫入 R1
     I2: add   R3, R1, R4     # 於 ID 階段需要讀取 R1
     I3: add   R5, R3, R6     # 於 ID 階段需要讀取 R3
     I4: add   R7, R8, R9
     

   • $I_1$ 與 $I_2$ 之間：$I_1$ 的目標暫存器為 R1，而 $I_2$ 的來源暫存器亦包含 R1，存在 RAW 相依。

核心觀念

1. 管線資料危障（Pipeline Data Hazard）：

   • 當前後指令存取相同的暫存器，且執行順序在管線重疊（overlapping）中會導致非預期的讀寫順序時，即發生資料危障。
   • 在標準的五階段管線（IF, ID, EX, MEM, WB）中，暫存器的寫入通常發生在 WB 階段後半週期，讀取發生在 ID 階段前半週期。若前行指令尚未將結果寫回暫存器，後續指令就試圖在 ID 階段讀取該暫存器，便會讀到舊值。

2. 資料相依性分類（RAW, WAR, WAW）：

   • RAW（Read After Write，真相依性 True Dependency）：後續指令需要讀取前一個指令將要寫入的暫存器。在循序發射（In-order issue）的標準五階段 MIPS 管線中，唯一會發生的資料危障即為 RAW Hazard。
   • WAR（Write After Read） 與 WAW（Write After Write） 僅在亂序執行（Out-of-order execution）或非循序寫回的架構中才會構成危障，在經典五階段循序管線中不會產生。

---

解題方法

將給定的組語指令依序編號，並逐一列出各指令的來源暫存器（Source Registers）與目的暫存器（Destination Register）：

• $I_1$: lw R1, 0(R2)
  • 讀取暫存器：R2
  • 寫入暫存器：R1（在 MEM 階段從記憶體讀出資料，WB 階段寫入暫存器）
• $I_2$: add R3, R1, R4
  • 讀取暫存器：R1, R4（需在 ID 階段讀取）
  • 寫入暫存器：R3
• $I_3$: add R5, R3, R6
  • 讀取暫存器：R3, R6（需在 ID 階段讀取）
  • 寫入暫存器：R5
• $I_4$: add R7, R8, R9
  • 讀取暫存器：R8, R9
  • 寫入暫存器：R7

依序檢查指令間的暫存器相依（RAW 相依）：

1. $I_1$ 與 $I_2$ 之間的相依性：
   • $I_1$（lw）預計寫入 R1，而緊接在後的 $I_2$（add）需要讀取 R1。
   • 此為 RAW（Read After Write） 資料相依。在標準五階段管線中，若無 forwarding，會造成資料危障；即使有 forwarding，由於 lw 是在 MEM 階段結束才取得資料，而 $I_2$ 在 EX 階段就需要該數值，仍會產生一個週期的 Load-use Data Hazard。

核心觀念

本題考查管線化處理器（Pipelined Processor）中的 指令排程（Instruction Scheduling） 觀念。

• 定義：指令排程是指透過編譯器（靜態排程，Static Scheduling）或處理器硬體（動態排程，Dynamic Scheduling），在不改變程式原始執行結果（語意正確性）的前提下，重新排列指令的執行順序（Reordering Instructions）。
• 主要目的：避免或減少管線冒險（Pipeline Hazards，特別是 Load-use 資料相依性所造成的 Pipeline Stall / Bubble），從而提高指令層級平行度（Instruction-Level Parallelism, ILP）並降低程式的整體執行時脈週期數（Clock Cycles）。

---

解題方法

回答本題應從「定義、目的、分類與實例示範」切入：

1. 基本定義與目標：

   • 指令排程是為了解決資料相依性（Data Hazard，如 RAW）引發的停頓（Stall）。
   • 當前後指令存在相依性且硬體轉發（Forwarding）仍無法完全消除停頓（例如典型的 Load-use Hazard）時，可利用其他「彼此獨立、互不相依」的指令填入等待間隙中。

2. 實現方式（兩種途徑）：

   • 靜態指令排程（Static Instruction Scheduling）：由**編譯器（Compiler）**在編譯時期分析相依性圖（Dependency Graph），重排組合語言指令順序，又稱為編譯器最佳化排程（Compiler-based Scheduling）。
   • 動態指令排程（Dynamic Instruction Scheduling）：由**硬體（Hardware）**在執行時期（Runtime）根據運算元就緒狀態進行亂序執行（Out-of-Order Execution, OoO），常見架構如 Tomasulo 演算法。

3. 結合題幹程式碼示範：
   題幹原始程式碼如下：

核心觀念

在標準的 MIPS 5 級管線（IF、ID、EX、MEM、WB）且具備**轉發機制（Forwarding / Bypassing）**的架構下：

1. Load-use Data Hazard：
   lw 指令從記憶體讀取的資料，要到 MEM 階段結束（或 WB 階段開始）才能獲得；而接續的指令若需要該資料作為運算元，在轉發機制下最快也必須在 EX 階段開始拿到。因此，若緊接在 lw 之後的指令立即使用其載入的值，即便有轉發硬體，仍必然產生 **1 個週期（1 stall cycle）**的停頓。
2. 指令排程（Instruction Scheduling / Code Reordering）：
   編譯器可藉由靜態重排無資料相依性（Data Dependency）的獨立指令，填入 lw 與其相依指令之間的「延遲槽（Delay Slot）」，在不改變原程式語意的前提下，完全消除管線停頓（Stall）。

---

解題方法

1. 資料相依性分析

觀察原始組合語言指令序列：

• $I_1$: lw R1, 0(R2) $\rightarrow$ 寫入 R1
• $I_2$: add R3, R1, R4 $\rightarrow$ 讀取 R1、R4，寫入 R3（與 $I_1$ 存在 Load-use Hazard，需停頓 1 個週期）
• $I_3$: add R5, R3, R6 $\rightarrow$ 讀取 R3、R6，寫入 R5（與 $I_2$ 存在 RAW 相依，但透過 EX-to-EX 轉發可於 0 stall 順暢執行）
• $I_4$: add R7, R8, R9 $\rightarrow$ 讀取 R8、R9，寫入 R7（完全獨立，與前三道指令皆無資料相依性）

2. 利用指令重排消除 Stall

在原始碼中，僅 $I_1$ 與 $I_2$ 之間存在 1 個週期的 Load-use stall。

核心觀念

本題考查計算機結構中**記憶體階層（Memory Hierarchy）**的基本架構與設計目的。

1. 記憶體階層的目標：利用局部性原理（Principle of Locality），兼顧存取速度快與儲存容量大兩大目標，營造出「速度如最快層、容量如最大層」的虛擬效果。
2. 階層順序與定位：傳統記憶體階層由上至下（速度由快至慢、容量由小至大、單位成本由高至低）依序為：
   • 暫存器（Registers）
   • 快取記憶體（Cache Memory）
   • 主記憶體（Main Memory / DRAM）
   • 次級儲存裝置（Secondary Storage / Disk / SSD）

快取記憶體通常由 SRAM（靜態隨機存取記憶體）構成，其物理與邏輯位置介於 CPU（處理器內部的暫存器與運算單元）與主記憶體（Main Memory） 之間，用以彌補處理器執行速度與主記憶體存取延遲之間的巨大效能落差（Memory Wall）。

---

解題方法

題目詢問快取記憶體在記憶體階層中通常位於何處（"where is cache usually located?"）：

核心觀念

本題評量快取記憶體（Cache Memory）的基本組織架構與參數關係。

在快取組織中，快取區塊總數（Number of Cache Blocks / Lines） 與 快取總容量（Cache Capacity / Data Size） 以及 區塊大小（Block Size） 滿足基本定義關係：

$$\text{Cache Blocks} = \frac{\text{Cache Capacity}}{\text{Block Size}}$$

對於直接對映快取（Direct-Mapped Cache），每個集合（Set）恰好包含一個區塊（即 $1\text{-way set associative}$），因此區塊總數亦等於集合總數（Number of Sets）：

$$\text{Number of Sets} = \text{Number of Blocks} = 2^{\text{Index bits}}$$

---

解題方法

1. 統一計量單位（轉換為 $2$ 的次方）：

   • 快取總容量（Capacity）：$C = 2\text{ MB} = 2 \times 2^{20}\text{ Bytes} = 2^{21}\text{ Bytes}$。
   • 區塊大小（Block Size）：$B = 256\text{ Bytes} = 2^8\text{ Bytes}$。

2. 計算區塊總數：
   代入定義公式計算：

核心觀念

本題考查計算機結構中最基礎的數值表示法：十六進位（Hexadecimal）與二進位（Binary）的進位制轉換。

在現代計算機架構中，記憶體定址以 Byte 為基本單位，每個十六進位數字（Hex digit）恰好對應 4 個二進位位元（Bits，即一個 Nibble），對應關係如下表：

十六進位	二進位	十六進位	二進位
0	0000	8	1000
1	0001	9	1001
2	0010	A	1010
3	0011	B	1011
4	0100	C	1100
5	0101	D	1101
6	0110	E	1110
7	0111	F	1111

---

解題方法

給定 32 位元記憶體位址十六進位表示為 0x1A8899F2，將每一個十六進位字元逐一展開為對應的 4-bit 二進位碼：

1. 第 1 個 Nibble：1 $\rightarrow 0001_2$
2. 第 2 個 Nibble：A $\rightarrow 1010_2$（因 $\text{A}_{16} = 10_{10} = 8 + 2$）
3. 第 3 個 Nibble：8 $\rightarrow 1000_2$
4. 第 4 個 Nibble：8 $\rightarrow 1000_2$
5. 第 5 個 Nibble：9 $\rightarrow 1001_2$（因 $9_{10} = 8 + 1$）

核心觀念

在快取記憶體（Cache Memory）架構中，記憶體位址會被切割為三個欄位：

1. Tag（標記）：用來辨識目前存放在該 Cache Line/Set 的資料是否為所欲存取的區塊。
2. Index（索引）：用來決定該位址對應到 Cache 中的哪一個 Set（在 Direct-Mapped Cache 中，一個 Set 僅包含一個 Line/Block，因此 Set 索引即為 Line 索引）。
3. Offset（區塊內位移）：用來定位 Block 內的具體位元組（Byte）。

相關規格與欄位長度計算公式如下：

• Offset 位元數：
  $b = \log_2(\text{Block Size})$
• Set 數量（Number of Sets）：
  $\text{Number of Sets} = \frac{\text{Cache Capacity}}{\text{Block Size} \times \text{Associativity}}$
  • 由於本題為直接對應快取（Direct-Mapped Cache），其關聯度 $\text{Associativity} = 1$。
• Index 位元數：
  $s = \log_2(\text{Number of Sets})$
• 位址映射計算（Mapping Formula）：
  $\text{Set Index} = \left( \frac{\text{Memory Address}}{\text{Block Size}} \right) \bmod (\text{Number of Sets})$
  亦即直接擷取位址中由低位元算起、排在 Offset 之後的 $s$ 個位元。

---

解題方法

1. 分析 Cache 規格與位址欄位切割

• 快取容量（Capacity）：$2\text{ MB} = 2 \times 2^{20}\text{ Bytes} = 2^{21}\text{ Bytes}$
• 區塊大小（Block Size）：$256\text{ B} = 2^8\text{ Bytes}$
• 映射方式：Direct-Mapped（$\text{Associativity} = 1$）

因此：

• Offset 長度：
  $b = \log_2(256) = 8\text{ bits}$
• Set 總數：
  $\text{Number of Sets} = \frac{2^{21}\text{ B}}{256\text{ B} \times 1} = \frac{2^{21}}{2^8} = 2^{13} = 8192\text{ 個}$
• Index 長度：
  $s = \log_2(8192) = 13\text{ bits}$

位址的位元配置如下（設為 32-bit 位址）：

• Bit [7:0]（共 8 bits）：Offset
• Bit [20:8]（共 13 bits）：Index（決定映射到哪一個 Set / Line，範圍為 $0 \sim 8191$）
• Bit [31:21]（共 11 bits）：Tag

---

2. 定位所欲查詢之位址（The above address）

本題為題組第 8-D 題，題幹述及「the above address」，指涉同題組前面小題所給定的記憶體位址。暨南大學資工所該年度第 8 題組前文所給之存取位址為十六進位位址 0x12345678。