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

概念速記

• R‑format：僅有三個寄存器欄位，無記憶體操作。
• I‑format：含立即數，亦作為 load（如 lw）的記憶體存取格式。
• 呼叫慣例：參數與返回值寄存器（a0‑a7）屬 caller‑saved，呼叫者自行保存，非被保留。
• 分支指令：使用 PC‑相對 byte 位移，位址以位元組為單位，因此符合記憶體位址對齊規則。

判斷

說明

• (a) RAW (Read‑After‑Write) 牽涉到前一指令的寫入與後一指令的讀取，與 instruction fetch 階段無關，故錯誤。
• (b) 若分支之實際結果與預測不符，流水線須暫停或清除錯誤指令，產生 control hazard，此描述正確。

核心觀念

本題旨在考驗對**虛擬記憶體（Virtual Memory, VM）**運作機制與架構特性的核心概念，包含：

1. 位址轉譯（Address Translation）與頁表存取成本：虛擬位址（Virtual Address, VA）轉換為實體位址（Physical Address, PA）時，若無 TLB（Translation Lookaside Buffer）快取的支援，存取實體資料額外所需的主記憶體存取次數。
2. 虛擬記憶體定義與專有名詞：分頁（Page）與分頁錯誤（Page Fault）的定義與功能。
3. 記憶體快取階層（Memory Hierarchy）之寫入策略：主記憶體與次級儲存裝置（Secondary Storage，如 SSD/HDD）之間的存取懲罰（Miss Penalty）對寫入策略（Write-through vs. Write-back）選擇的決定性影響。

---

解題方法

解答本題時，需掌握虛擬記憶體與 Cache 在架構設計上的本質關係：

• 存取成本分析：將主記憶體視為次級儲存裝置的 Cache。CPU 存取記憶體時需先進行「位址轉譯」取得實體位址，再存取「目標資料」。若未配備 TLB，位址轉譯必須存取位於主記憶體中的頁表（Page Table），因此一次資料存取至少觸發兩次主記憶體存取。
• 寫入策略評估：次級儲存裝置的讀寫時間（微秒 $\mu\text{s}$ 至毫秒 $\text{ms}$ 級）比起主記憶體（奈秒 $\text{ns}$ 級）慢了 $10^5 \sim 10^6$ 倍以上。巨大的 Miss Penalty 使得任何需要頻繁寫入次級儲存裝置的策略（如 Write-through）在效能上完全不可行，必須採用 Write-back 策略。

---

選項分析

(a) 正確

在配備虛擬記憶體且**無 TLB（Translation Lookaside Buffer）**的系統中，CPU 發出虛擬位址欲存取資料時，必須經過以下步驟：

1. 第一步（位址轉譯）：處理器必須先存取位於主記憶體中的頁表（Page Table），查表將虛擬頁號（VPN）轉譯為實體頁號（PPN），以合成實體位址（PA）。（註：若採用多層頁表 Multi-level Page Table，此步驟需要的記憶體存取次數會更多）。
2. 第二步（存取資料）：處理器使用合成出的實體位址，再次存取主記憶體取得真正的指令或資料。

因此，在沒有 TLB 緩衝的情況下，處理器每一次存取資料至少需要 2 次記憶體存取（Memory References）。故本選項敘述正確。

核心觀念

本題考驗 CPU 快取寫入策略（Cache Write Policies） 的運作機制及其效能與一致性比對：

1. 寫直達（Write-Through）：
   當 CPU 執行寫入操作且快取命中（Write Hit）時，資料會同時寫入快取（Cache）與下層的主記憶體（Main Memory）。優點是架構簡單、主記憶體隨時保持最新狀態；缺點是每一次寫入操作都會引發主記憶體匯流排傳輸，極易引發記憶體頻寬瓶頸。

2. 寫回（Write-Back）：
   當 CPU 執行寫入操作時，資料僅更新於快取區塊（Cache Line），並將該區塊的髒位元（Dirty Bit）標記為 1。只有當該快取區塊被替換（Evict / Replace）時，若 Dirty Bit 為 1，才會將資料寫回主記憶體。優點是可大幅降低記憶體匯流排存取次數；缺點是主記憶體存在舊資料（Stale Data）。

3. 多處理器快取一致性（Multi-processor Cache Coherence）：
   在多處理器系統中，若處理器 A 修改了其私有快取中的資料，Write-Back 策略會導致主記憶體未能即時更新。當處理器 B 試圖讀取該位址時，必須依靠快取一致性協定（如 MESI、MOESI）進行監聽（Snooping）與區塊轉接，增加了維護一致性的複雜度。

---

解題方法

本題為觀念比較選擇題，從以下三個維度切入評估：

1. 寫入時機與頻寬負擔：比較 Write-Through（每次寫入皆存取記憶體）與 Write-Back（僅替換時存取記憶體）對主記憶體匯流排頻寬的消耗狀況。
2. 工作負載適合度：高頻率寫入情境下，評估何者能更有效合併（Aggregate）寫入動作。
3. 多處理器架構影響：評估主記憶體資料非最新（Stale）狀態對多核心一致性維護所帶來的挑戰。

---

選項分析

• (a) 正確。
  根據寫直達（Write-Through）的定義，每次寫入命中時，資料皆會同步寫入快取與主記憶體，以保證下層記憶體隨時擁有最新資料。

核心觀念

本題考查計算機組織與作業系統中**多執行緒（Multithreading）**的核心機制，涵蓋以下關鍵概念：

1. 執行緒（Thread）與程序（Process）的資源關係：程序為資源分配的基本單位；執行緒為 CPU 排程與執行的基本單位。同一程序內的多個執行緒共享虛擬位址空間、程式碼區段（Code Segment）、全域資料（Data Segment）與作業系統資源（如開啟的檔案）。
2. 硬體多執行緒（Hardware Multithreading）的架構需求：處理器若要在硬體層級支援多執行緒（如細粒度 Fine-grained、粗粒度 Coarse-grained 或同時多執行緒 SMT/Hyper-Threading），必須為每個執行緒複製獨立的架構狀態（Architectural State），即獨立的暫存器組（Register File）與程式計數器（Program Counter, PC）。其餘運算單元（ALU）、快取（Cache）與記憶體介面則互相共享。
3. 內文切換（Context Switch）的開銷差異：執行緒層級的內文切換（Thread Context Switch）僅需保存與還原 CPU 暫存器與 PC，無需切換頁表（Page Table Base Register）或刷新 TLB，開銷遠低於程序層級的內文切換（Process Context Switch）。
4. 並發（Concurrency）與並行（Parallelism）：Multithreading 旨在程序內部切分多個執行緒以提升 CPU 資源利用率；而跨程序的排程運作屬於多工作業（Multitasking）範疇。

---

解題方法

判斷多執行緒相關敘述之正誤，可依據以下邏輯切入：

1. 區分 Thread 與 Process 作用層級：確定敘述對象是程序內部的執行線索（Thread）還是獨立的執行程序（Process）。
2. 檢視硬體資源配置：判斷硬體多執行緒中哪些元件需「獨立複製」，哪些元件為「共享」。
3. 分析 Context Switch 的具體內容：辨析同程序內切換執行緒與跨程序切換的差別。
4. 釐清並行執行的硬體條件：確認單一處理器在支援 SMT 或多核心時如何達成真正的並行（Simultaneous Execution）。

---

選項分析

• (a) Multithreading involves the simultaneous execution of multiple threads within the same process.（正確）
  • 分析：多執行緒（Multithreading）的核心定義即是在「同一個程序（Process）」內部包含並執行多個獨立的執行線索（Threads）。在現代多核心或支援硬體多執行緒（SMT）的處理器環境下，同程序內的多個執行緒得以在硬體上實現真正的同時（Simultaneous）或並行執行，從而提升系統吞吐量。

核心觀念

本題考查計算機組織（Computer Organization）中**定址模式（Addressing Modes）**的基本定義與有效位址（Effective Address, EA）之計算方式。

定址模式決定了指令如何取得操作數（Operand）或計算出操作數於主記憶體中的有效位址。常見定址模式的標準定義如下：

1. 立即定址模式（Immediate Addressing Mode）：操作數直接編碼在指令欄位中（即 Operand = Immediate Value）。
2. 暫存器定址模式（Register Addressing Mode）：操作數儲存在 CPU 的內部暫存器中，指令中僅指定暫存器編號（即 Operand = $R[\text{Register}]$）。
3. 直接定址模式（Direct Addressing Mode）：指令欄位直接包含操作數在記憶體中的有效位址（即 $EA = \text{Address}$）。
4. 間接定址模式（Indirect Addressing Mode）：指令欄位包含一個記憶體位址，該位址儲存的內容才是操作數真正的有效位址（即 $EA = M[\text{Address}]$）。
5. 索引定址模式（Indexed Addressing Mode）：有效位址由基底位址加上索引暫存器（Index Register）的值計算而得（即 $EA = \text{Base Address} + R[\text{Index}]$）。

---

解題方法

本題為多重選擇題，切入點為比對各大定址模式的官方標準定義與記憶體存取機制，逐一檢視各選項敘述的正確性：

1. 檢查操作數與位址的儲存位置（指令內部、暫存器、主記憶體）。
2. 比對有效位址（Effective Address, EA）的計算公式。
3. 判定各選項的英文字面敘述是否符合計算機結構理論。

---

選項分析

• (a) 正確。

  • 題目原文：Immediate addressing mode involves specifying the operand value directly in the instruction.
  • 詳細說明：立即定址模式的特徵是操作數數值直接放置在指令的常數欄位（Immediate field）中，CPU 擷取指令後無須額外存取記憶體或暫存器即可直接獲得操作數。故本敘述正確。

• (b) 錯誤。

  • 題目原文：Register addressing mode utilizes an address stored in memory to access the operand.

核心觀念

本題考查精簡指令集（RISC，如 RISC-V）與複雜指令集（CISC，如 x86）之架構哲學與效能差異。

處理器效能可由經典的 CPU 效能定律（Iron Law of Processor Performance） 評估：
$\text{CPU Time} = \text{IC} \times \text{CPI} \times \text{Clock Cycle Time}$
其中：

• $\text{IC}$（Instruction Count）：執行程式所需的總指令數。
• $\text{CPI}$（Cycles Per Instruction）：平均每條指令執行所需的時脈週期數。
• $\text{Clock Cycle Time}$（CCT）：時脈週期時間（即 $\frac{1}{\text{Clock Rate}}$）。

RISC（Reduced Instruction Set Computer）的核心設計哲學包括：

1. 簡化指令格式與固定指令長度：採用 Load/Store 架構與硬線邏輯控制（Hardwired Control Unit）。
2. 降低 CPI：使絕大多數基本指令能在單一週期內或透過高效流水線（Pipelining）完成，達到極低的平均 $\text{CPI} \approx 1$。
3. 簡化硬體解碼與流水線控制：指令格式高度規整（如 RISC-V 的 32-bit 定長指令），硬體可在指令解碼（ID）階段輕鬆擷取暫存器索引與操作碼，進而提高執行效率。

---

解題方法

解題切入點在於對比 RISC-V 與傳統 CISC 在 CPU 效能三因子（$\text{IC} \times \text{CPI} \times \text{CCT}$）上的權衡（Trade-off）：

• CISC 傾向於提供強大且複雜的單一指令（降低 $\text{IC}$），但代價是指令解碼極度複雜，多數指令需要多個時脈週期才能完成（高 $\text{CPI}$）。

核心觀念

本題考查 RISC-V 組合語言 的指令語意、暫存器操作以及迴圈結構控制。主要涵蓋以下觀念：

1. 暫存器 $x0$ 的特性：RISC-V 的 $x0$ 為硬體固定為 0 的暫存器（Zero Register），唯讀且寫入無效。
2. 算術與邏輯指令語意：
   • addi rd, rs1, imm：$rd = rs1 + imm$（立即數加法）。
   • sub rd, rs1, rs2：$rd = rs1 - rs2$（暫存器減法）。
   • add rd, rs1, rs2：$rd = rs1 + rs2$（暫存器加法）。
   • slli rd, rs1, shamt：邏輯左移立即數（Shift Left Logical Immediate），等價於 $rd = rs1 \times 2^{shamt}$。在此處 slli x4, x1, 2 代表 $x4 = x1 \times 2^2 = x1 \times 4$。
3. 控制流指令：
   • beq rs1, rs2, label：若 $rs1 == rs2$ 則跳轉至指定標號（Branch if Equal）。
   • j label：無條件跳轉（Jump）。
4. 記憶體寫入指令：
   • sw rs2, offset(rs1)：將暫存器 $rs2$ 的 32-bit 資料寫入記憶體位址 $rs1 + offset$。

---

解題方法

1. 代數數學化簡法（快速解法）

分析程式碼之控制流與暫存器變更邏輯：

• x1：初始化為 $5$，每次迴圈減 $1$（因為 x3 = 1），當 x1 == 0 時跳出迴圈。故迴圈共執行 $5$ 次，x1 傳入的數值依序為 $5, 4, 3, 2, 1$。
• x4：在迴圈內計算 $x4 = x1 \times 4$。
• x2：初始化為 $-5$，每次迴圈累加 $x4$ 的值。

因此，暫存器 x2 的最終值可表示為初值加上數列求和：
$x2_{\text{final}} = x2_{\text{initial}} + \sum_{x1=1}^{5} (x1 \times 4)$

帶入已知數值計算：
$x2_{\text{final}} = -5 + 4 \times (5 + 4 + 3 + 2 + 1) = -5 + 4 \times 15 = -5 + 60 = 55$

---

2. 逐步程式追蹤表（Trace Table）

迭代輪次	x1 (進入迴圈)	beq x1, x0 判斷	slli x4, x1, 2	sub x1, x1, x3	add x2, x2, x4	x2 更新後結果
初始狀態	5	—	—	—	—	-5

核心觀念

1. 向量處理器與向量暫存器長度限制（Vector Register Length / MVL）
   向量處理器中的向量暫存器容量為有限值（本題為 $MVL = 64$ 個元素）。當要處理的向量長度 $N$ 超過向量暫存器的容量時，無法使用單一向量指令將所有元素一次處理完畢。
2. 條帶開採（Strip-mining）
   將長度為 $N$ 的大向量切分為數個長度不超過 $MVL$ 的小片段（chunks）並分批執行的技術稱為 Strip-mining。所需的執行批次數（迴圈迭代次數）計算公式為：
   $\text{批次數} = \left\lceil \frac{N}{MVL} \right\rceil$
3. 固定執行時間模式
   題幹明確指出「執行單次向量加法運算需時 5 個時脈週期，且與向量長度無關（regardless of the vector length）」。這代表無論該批次載入的是滿載的 64 個元素還是剩餘不足 64 個的元素，執行該次向量加法指令皆固定耗時 5 個時脈週期。

---

解題方法

步驟一：計算 Strip-mining 所需的總批次數
已知：

• 待處理向量長度 $N = 480$ 個元素
• 向量暫存器容量 $MVL = 64$ 個元素

帶入 Strip-mining 公式計算批次數：
$\text{批次數} = \left\lceil \frac{480}{64} \right\rceil = \lceil 7.5 \rceil = 8 \text{ 批}$
即前 7 批每批處理 64 個元素（共 $7 \times 64 = 448$ 個元素），第 8 批處理剩餘的 32 個元素（$480 - 448 = 32$ 個元素）。

核心觀念

本題考查快取記憶體（Cache Memory）的組織架構與參數計算，特別是**組關聯式映射（Set-Associative Mapping）**中快取容量、快取行（Cache Line / Block）與組（Set）之間的數量關係。

解題所需的關鍵定義與公式如下：

1. 快取總容量（Total Cache Size, $C$）：快取所能儲存的總資料量（若未特別說明，預設不包含 Tag 與 Control bits 等開銷）。
2. 快取行大小（Cache Line Size / Block Size, $B$）：單一快取行可儲存的資料位元組數（Bytes）。
3. 組關聯度（Associativity / Ways per Set, $N$）：每一組（Set）內包含的快取行數量。本題為 4-way set-associative，故 $N = 4$。
4. 總快取行數（Total Cache Lines, $L$）：
   $L = \frac{\text{快取總容量 } C}{\text{快取行大小 } B}$
5. 總組數（Number of Sets, $S$）：
   $S = \frac{\text{總快取行數 } L}{\text{每組的行數 } N} = \frac{C}{B \times N}$

---

解題方法

根據題目給定的已知條件：

• 快取總容量 $C = 32 \text{ KB} = 32 \times 1024 \text{ Bytes} = 32,768 \text{ Bytes} = 2^{15} \text{ Bytes}$
• 快取行大小 $B = 64 \text{ Bytes} = 2^6 \text{ Bytes}$
• 組關聯度 $N = 4 \text{ (4-way)}$

推導步驟如下：

(a) 計算快取中的組數（Number of Sets）

依據組數公式 $S = \frac{C}{B \times N}$：

1. 每組（Set）包含的總資料容量為：
   $B \times N = 64 \text{ Bytes} \times 4 = 256 \text{ Bytes} = 2^8 \text{ Bytes}$
2. 將總容量除以單一組的容量可得組數：
   $S = \frac{32,768 \text{ Bytes}}{256 \text{ Bytes}} = 128 \text{ 組}$
   若採用 $2$ 的次方展開計算：
   $S = \frac{2^{15}}{2^6 \times 2^2} = \frac{2^{15}}{2^8} = 2^{15-8} = 2^7 = 128 \text{ 組}$

(b) 計算快取中的總行數（Total Cache Lines）

依據總快取行數公式 $L = \frac{C}{B}$：

1. 快取的總行數只由「快取總容量」與「單一行大小」決定，與組關聯度無關：