109 年 國立成功大學電機工程學系碩士班戊組《計算機組織》

核心觀念

本題考查經典 RISC 五階段管線處理器（5-stage Pipelined Processor：IF, ID, EX, MEM, WB）的核心架構與控制機制，涵蓋以下四大觀念：

1. 時脈與時序邏輯組件（Datapath Timing & Sequential Logic Elements）：管線暫存器、PC 暫存器與快取記憶體組件在時脈驅動下的運作邏輯與資料通路（Datapath）設計。
2. 記憶體層級與停頓控制（Memory Hierarchy & Pipeline Stall）：L1 Data Cache 發生 Miss 時，系統如何透過凍結（Freeze/Stall）管線與插入氣泡（Bubble/NOP）來處理記憶體懲罰時間（Miss Penalty）。
3. 例外處理與檢測階段（Exception Detection Stages）：不合法指令（Illegal Instruction / Undefined Opcode）在指令解碼（ID）階段由控制器（Control Unit）辨識。
4. 精確中斷（Precise Interrupt）之定義與實現：在中斷／例外發生時，保證處理器架構狀態（Architectural State）一致性與可恢復性（Resumability）的規範。

---

解題方法與詳細解析

(a) 繪製 PC = PC + 4 之簡易資料通路圖（Simple Datapath Diagram）

在經典 5 階段管線中，$PC = PC + 4$ 是指令擷取（IF, Instruction Fetch）階段計算順序下一條指令位址的基本電路。

• 資料流向說明：

  1. $PC$ 暫存器輸出目前的指令位址給加法器（Adder）以及 L1 指令快取（L1 ICache）。
  2. 加法器將 $PC$ 與常數 $4$ 相加，計算出 $PC + 4$。
  3. $PC + 4$ 的結果會經由多工器（MUX，用於分支／跳躍選擇）在下一個時脈正邊緣（Clock Rising Edge）寫回 $PC$ 暫存器；同時 $PC + 4$ 也會傳送至 IF/ID 管線暫存器（Pipeline Register），供後續階段使用。
  4. L1 ICache 依據 $PC$ 位址讀出指令（Instruction），並寫入 IF/ID 管線暫存器。

• 資料通路架構圖：

               +---------------+
               |   Adder (+4)  |
               +-------+-------+
                       ^
                       | (PC)
                       |
     +-------+    +----+----+    +-------------+    +---------------+
     |  MUX  |--->|    PC   |--->|  L1 ICache  |--->|     IF/ID     |
     +-------+    +----+----+    +-------------+    | Pipeline Reg  |
         ^             |                            |               |
         | (PC+4)      +--------------------------->| (Stores PC+4) |
         +------------------------------------------+---------------+

---

(b) 管線資料通路中應連接至 CPU Clock 的組件

在管線處理器中，所有**狀態元素（State Elements / Sequential Logic Circuits）**皆必須連接至 CPU 時脈訊號（CPU Clock），以確保資料能同步地在時脈邊緣觸發並鎖存（Latch）。包含以下組件：

1. 程式計數器（Program Counter, PC 暫存器）。
2. 管線暫存器（Pipeline Registers）：包含 IF/ID、ID/EX、EX/MEM、MEM/WB 暫存器。
3. 暫存器檔案（Register File）：在 WB（Write Back）階段需要時脈訊號驅動寫入操作（通常為半週期邊緣觸發）。
4. L1 快取中的 SRAM 記憶體陣列（L1 ICache & L1 DCache Tag/Data SRAMs）：快取內部狀態與控制暫存器需要時脈同步驅動。
5. 控制單元與狀態機暫存器（如 Hazard Detection Unit、Branch Predictor 的狀態暫存器）。

---

(c) 發生 L1 Data Cache Miss 時的管線處理機制

當在 MEM 階段偵測到 L1 DCache Miss 時，資料無法立即提供給 WB 階段，處理器必須採取以下步驟控制管線：

1. 凍結前半段管線暫存器與 PC（Stall/Freeze Pipeline）：
   • 保持 $PC$ 暫存器、IF/ID、ID/EX、EX/MEM 暫存器的內容不變（關閉其寫入致能訊號 Write Enable = 0），使 IF、ID、EX、MEM 階段的指令停止前進。
2. 發出下層記憶體存取請求：
   • DCache Controller 向下一層記憶體（L2 Cache 或 Main Memory）發送 Fetch Request，以讀取包含所需資料的整個 Memory Block。
3. 向後半段管線插入氣泡（Insert Bubble / NOP）：
   • 在 MEM/WB 暫存器中將控制訊號清零（如 RegWrite = 0, MemtoReg = 0），相當於向 WB 階段傳送一條 NOP（No Operation）指令，防止無效資料寫回暫存器檔案。
4. 等待區塊載入（Wait for Miss Penalty）：
   • 管線維持 Stall 狀態，直到 L2 Cache 或 Main Memory 將資料區塊填入 L1 DCache。
5. 恢復管線運作（Resume Execution）：

核心觀念

本題旨在考驗計算機組織中「函式呼叫慣例（Procedure Calling Convention）」與「執行時期堆疊操作（Run-time Stack Operations）」的硬體架構與語意機制。核心涵蓋三大觀念：

1. 控制權轉移與角色分工：區分呼叫者（Caller）與被呼叫者（Callee）在暫存器保護（Register Saving）與空間管理上的職責與規範。
2. 堆疊動態管理：利用**堆疊指標（Stack Pointer, SP）**動態追蹤記憶體中堆疊頂端（Top of Stack）的位址，維持 Stack Frame（堆疊訊框）的建立與釋放。
3. 指令集架構設計（ISA）：Jump-and-Link（JAL） 指令如何於單一指令週期內完成程式計數器（PC）轉移與返回位址（Return Address）之保存。

---

解題方法

回答此類觀念名詞與機制題時，切入點應包含標準定義、硬體執行語意、以及在記憶體與暫存器操作中的具體功能：

1. 精準定義（Definition）：明確指出該名詞在計算機結構中的角色或指令語意。
2. 運作機制（Mechanism & Semantics）：配合 MIPS / RISC-V 架構敘述硬體暫存器（如 $sp, $ra）與記憶體位址變化的推導邏輯。
3. 堆疊與呼叫互動（Stack Interaction）：說明當程式遇到嵌套呼叫（Nested Calls）或遞迴（Recursion）時，此三者如何協同運作以維護程式正確性。

---

子題詳細剖析與解答

(a) What is a callee?（何謂被呼叫者？）

• 核心定義：
  在函式呼叫機制中，**被其他函式發起調用／呼叫的目標函式（Procedure / Function）**稱為 Callee（被呼叫者）。發起呼叫的來源函式則稱為 Caller（呼叫者）。
• 在 Stack 操作與暫存器維護中的職責：
  1. Callee-saved 暫存器之保存與還原：根據呼叫慣例（Calling Convention），Callee 若需要使用 Callee-saved 暫存器（例如 MIPS 之 $s0–$s7 或 RISC-V 之 s0–s11），Callee 必須在執行主體前將這些暫存器的原數值壓入堆疊（Push onto Stack）；並在函式返回前將其自堆疊彈出（Pop from Stack）還原，確保返回 Caller 後其執行環境不被破壞。
  2. 建構自身的 Stack Frame：若 Callee 包含區域變數（Local Variables）、超過暫存器容量的傳入參數、或是非葉端函式（Non-leaf Procedure，即自身會再呼叫其他函式），Callee 需透過調整堆疊指標（$SP$）在 Stack 上配置專屬空間。
  3. 交還控制權與傳遞傳回值：將計算結果放入指定的傳回值暫存器（如 MIPS 之 $v0–$v1 或 RISC-V 之 a0–a1），最後執行返回指令（如 jr $ra 或 ret）將執行權交還給 Caller。

(b) What is a stack pointer?（何謂堆疊指標？）

• 核心定義：
  堆疊指標（Stack Pointer, SP） 是 CPU 內部一個專用的通用暫存器（如 MIPS 的 $sp / $29 或 RISC-V 的 sp / x2），用於儲存當前執行時期堆疊（Run-time Stack）頂端的記憶體位址。
• 在 Stack 操作中的運作機制：
  1. 定址與動態配置：Stack 用於存放暫存器備份、區域變數及返回位址。$SP$ 提供基底位址（Base Address），程式可以透過 $SP

核心觀念

本題考查計算機組織中快取記憶體（Cache Memory）的位址映射（Address Mapping）機制與記憶體位址分割欄位計算。

1. 快取基本參數與架構關係：

   • 快取總容量（Cache Size, $C$）
   • 快取區塊／行大小（Block / Line Size, $B$）
   • 快取總行數（Total Cache Lines, $L$）：
     $L = \frac{C}{B}$
   • 相聯度（Degree of Associativity, $K$）：每一組（Set）包含的快取行數。
   • 快取組數（Number of Sets, $S$）：
     $S = \frac{L}{K}$

2. 主記憶體位址分割（Address Breakdown）：
   在 $N$ 位元的實體位址空間下，位址被切割為三個欄位：

   • Offset（區塊偏移量）：用於於區塊內定位具體的 Byte，位元數長度為 $\log_2(B)$。
   • Index（組索引）：用於指定資料映射至快取的哪一個 Set，位元數長度為 $\log_2(S)$。
   • Tag（標籤）：用於比對該快取行是否為目標位址資料，位元數長度為 $N - \text{Index} - \text{Offset}$。

---

解題方法

根據題目給定資訊：

• 位址總長度 $N = 32\text{ bits}$
• 快取總容量 $C = 128\text{ KB} = 128 \times 1024\text{ Bytes} = 2^{17}\text{ Bytes}$
• 快取區塊大小 $B = 32\text{ Bytes} = 2^5\text{ Bytes}$

共通參數預先推導：

1. Offset 欄位位元數：
   $\text{Offset} = \log_2(B) = \log_2(32) = 5\text{ bits}$
2. 快取總行數 $L$：
   $L = \frac{C}{B} = \frac{2^{17}}{2^5} = 2^{12} = 4096\text{ lines}$

接著針對各子題不同的映射機制（相聯度 $K$），求出對應的組數 $S$，進而決定 Index 欄位長度 $\log_2(S)$。

---

子題詳解

a. If the cache is implemented in direct-mapping, how many cache lines does the cache have?

• 推導與解析：
  快取的總行數僅與快取總容量及單一行的大小有關，不受映射方式影響。
  $L = \frac{\text{Cache Size}}{\text{Line Size}} = \frac{128\text{ KB}}{32\text{ Bytes}} = \frac{2^{17}}{2^5} = 2^{12} = 4096$
  因此該快取共有 4096 行快取線。

【答案】4096（或 $2^{12}$）

---

b. Continued from a., what is the length (bits) of the index field used to select a cache line?

• 推導與解析：
  在直接映射（Direct-Mapped）架構中，相聯度 $K = 1$（每一組僅包含 1 個快取行）。
  因此快取的組數 $S$ 等於總行數 $L$：
  $S = \frac{L}{K} = \frac{4096}{1} = 4096 = 2^{12}\text{ sets}$
  選擇快取行所需的 Index 欄位長度即為組數的對數值：
  $\text{Index bits} = \log_2(S) = \log_2(4096) = 12\text{ bits}$

核心觀念

本題考查計算機組織中**虛擬記憶體系統（Virtual Memory System）**的整體架構、記憶體階層（Memory Hierarchy）特性、硬體/軟體分工以及相關關鍵元件（TLB、Page Table）的定義：

1. 虛擬記憶體的開啟機制：MMU（Memory Management Unit）與分頁機制（Paging）在開機時預設關閉，需由作業系統透過執行特權指令修改 CPU 的控制暫存器（Control Registers）來啟用。
2. 記憶體階層中的快取角色：虛擬記憶體技術將主記憶體（Main Memory / DRAM）視為次級儲存裝置（Secondary Storage / Disk）的快取。為最大化降低代價高昂的缺頁率（Page Fault Rate），採用全關聯式映射（Fully Associative）與寫回策略（Write-Back）。
3. TLB 的定義與快取對象：轉譯旁看緩衝區（TLB, Translation Lookaside Buffer）是 CPU 內部的硬體快取，其快取的對象是頁表項目／位址轉譯（Page Table Entries / Address Translations），而非虛擬記憶體的內容資料本身。
4. 頁表的功能：頁表（Page Table）是由作業系統維護的資料結構，用以儲存虛擬位址（Virtual Address）與實體位址（Physical Address）之間的映射（Mapping）關係。

---

解題方法

從記憶體階層架構與作業系統／硬體介面的觀念切入判斷：

1. 控制層面：檢查 CPU 暫存器架構，確認啟用 MMU 是否依賴特定指令。
2. 架構層面：釐清「誰是誰的 Cache」：
   • 主記憶體（DRAM）是次級儲存裝置（Disk/SSD）的 Cache。
   • TLB 是頁表（Page Table / 位址轉譯）的 Cache。
   • L1/L2/L3 Cache 是主記憶體（DRAM）的 Cache。
3. 策略層面：評估 Disk access 延遲（Miss Penalty 達 $10^6$ 個週期）對快取設計策略的約束，確認全關聯式與 Write-Back 的必然性。
4. 定義層面：比對教科書對 Page Table 與 TLB 的精確定義。

---

選項分析

• a. Virtual memory function can be enabled through instructions.（正確）
  在現代處理器架構（如 x86、ARM、RISC-V 等）中，系統開機時 MMU 預設關閉（處於實體位址模式）。作業系統在初始化階段，必須透過執行**特權指令（Privileged Instructions）**寫入控制暫存器來開啟虛擬記憶體與分頁機制。

  • 例如在 x86 架構中，執行 mov cr0, eax 將控制暫存器 CR0 的 PG（Paging Enable）位元設定為 $1$。
  • 在 RISC-V 架構中，透過 csrw satp, t0 指令寫入 satp 暫存器以設定分頁模式並啟用位址轉譯。
    因此，虛擬記憶體功能確實可透過指令開啟。

• b. Virtual memory technique treats part of the main memory as a fully-set associative write-back cache for program execution.（正確）
  在記憶體階層中，虛擬記憶體將主記憶體（DRAM）視為硬碟（Disk/SSD）的快取。因為從硬碟讀取資料的缺頁懲罰（Miss Penalty）極大（高達數百萬個時脈週期），為了將缺頁率（Page Fault Rate）降至最低：

核心觀念

1. 虛擬記憶體與位址轉譯（Address Translation）：
   虛擬位址（Virtual Address, VA）分為「虛擬頁號（Virtual Page Number, VPN）」與「頁面偏移量（Page Offset）」。實體位址（Physical Address, PA）分為「實體頁號（Physical Page Number, PPN）」與「頁面偏移量（Page Offset）」。因為虛擬頁面與實體頁面的大小相等，位址轉譯過程僅需將 $VPN$ 轉換為 $PPN$，而 $Page\ Offset$ 保持不變，不參與轉譯。
2. 轉譯後備緩衝區（Translation Lookaside Buffer, TLB）：
   TLB 是頁表（Page Table）的硬體快取（Cache），專門用來快取 $VPN \to PPN$ 的對映關係及相關控制位元（如 Valid bit、Dirty bit、Protection bits 等），以避免每次記憶體存取都需額外查詢主記憶體中的頁表。
3. Split TLB 架構（ITLB 與 DTLB）：
   為避免管線（Pipeline）中的結構衝突（Structural Hazard），現代處理器常將 TLB 獨立拆分為：
   • ITLB（Instruction TLB）：於指令擷取階段（IF stage）使用，輸入位址為程式計數器（Program Counter, PC）所指向的指令虛擬位址。
   • DTLB（Data TLB）：於記憶體存取階段（MEM stage）使用，輸入位址為載入／儲存指令（Load/Store）由 ALU 計算出之資料有效位址（Effective Address）。

---

解題方法

本題旨在考驗對 TLB 內部結構、轉譯對象以及處理器管線中 ITLB/DTLB 存取來源的理解。切入點如下：

1. 比較 TLB 快取欄位與位址結構：$Page\ Offset$ 在轉譯前後完全相同，直接由虛擬位址複製至實體位址，因此 TLB 標籤與資料陣列中無需儲存 $Page\ Offset$。

核心觀念

本題考查處理器（Processor）在上電（Power-on）開機時的硬體重置機制（Hardware Reset Mechanism）與程式計數器（Program Counter, PC）的初始化流程。

關鍵觀念與定義包含：

1. 硬體重置與重置向量（Reset Vector）：當處理器接通電源或接收到重置訊號（Power-On Reset, POR）時，內部的邏輯電路（Reset Circuits）會自動將 PC 暫存器設定為一個硬體預設的固定記憶體位址（即重置向量 Reset Vector，例如 x86 架構中的 $0\text{xFFFFFFF0}$ 或 MIPS 架構中的 $0\text{x80000000}$）。
2. 引導程序（Bootstrapping）順序：
   $\text{Power-On} \xrightarrow{\text{Hardware Logic}} \text{Initial PC (Reset Vector)} \xrightarrow{\text{Fetch}} \text{BIOS / Firmware} \xrightarrow{\text{Bootloader}} \text{Operating System}$
   在開機瞬間，作業系統（OS）尚未載入 RAM，且處理器尚未執行任何指令，因此初始 PC 的設定完全由硬體邏輯觸發與寫入，非透過軟體指令或作業系統完成。

---

解題方法

切入點為分析「開機瞬間處理器內部的硬體狀態與軟體執行順序」：

1. 處理器抓取指令的前提：處理器必須先有正確的 PC 值，才能從記憶體中抓取（Fetch）指令。若 PC 尚未初始化，處理器無法讀取任何指令，故「透過執行指令來設定初始 PC」在邏輯上屬於循環悖論。
2. 開機時的軟體存在狀態：上電瞬間，主記憶體（RAM）內無任何程式，作業系統（OS）根本尚未啟動。第一個被執行的程式是位於 ROM/Flash 中的 BIOS/UEFI 韌體。
3. 初始 PC 值的來源：硬體設計者在 CPU 內部將初始 PC 暫存器的電路接至固定數值，當重置訊號生效時，觸發器（Flip-flops）自動載入該固定位址。

因此，應選擇描述「初始 PC 係透過硬體操作預設於 PC 暫存器中」的選項。

---

選項分析

• 選項 a 錯誤：
  • 原文：a. The initial program counter is loaded by the processor from a specified memory location through a load instruction at b

核心觀念

本題考驗計算機組織中關於**快取記憶體（Cache Memory）**的綜合觀念，涵蓋以下四大核心主題：

1. 快取的發音與術語：英文專有名詞的標準讀音。
2. 快取一致性協定（Cache Coherency Protocol）：多處理器系統中匯流排監聽（Snooping-based）機制的維護方式（Write-invalidate vs. Write-update）。
3. 快取寫入未命中策略（Write Miss Policy）：Write-allocate（寫入分配）與 Write-around / No-write-allocate（環繞寫入 / 寫入不分配）。
4. 快取寫入命中策略（Write Hit Policy）：Write-through（直寫式）與 Write-back（寫回式）。

---

解題方法

針對本題各選項，依據計算機結構的標準定義進行驗證與分析：

1. 語意與發音：檢視音標標示是否符合標準英文字彙讀音。
2. 快取一致性分析：判斷當某個 Core/Cache 寫入資料時，控制器的行為是「將其他快取中的副本標記為無效（Invalidate）」還是「同步更新其他快取（Update）」。
3. 寫入策略對應：
   • Write Hit 時：判斷寫入動作是「僅更新快取並標記 dirty」還是「同時更新快取與下一層記憶體」。
   • Write Miss 時：判斷寫入動作是「將缺失資料區塊載入快取」還是「繞過快取直接寫入下一層記憶體」。

---

選項分析

• 選項 (a) 錯誤

  • 原因：Cache 的正確國際音標（IPA）發音為 $/kæʃ/$（讀音與 "cash" 相同），而非 $[kætʃ]$。$[kætʃ]$ 為 "catch"（抓住）的發音。

• 選項 (b) 正確

  • 原因：此敘述為**寫無效快取一致性協定（Write-invalidate Cache Coherency Protocol）**的標準定義。在基於監聽（Snooping）的一致性機制中，當某個處理器對特定記憶體位址進行寫入時，快取控制器會透過 Bus 廣播該寫入動作；