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

核心觀念

本題考查經典教科書 Computer Organization and Design (Patterson & Hennessy, COD) 所提出之**電腦架構八大前瞻觀念（Great Ideas in Computer Architecture）**及其核心定理與定義：

1. 加速常用案例（Make the common case fast）與阿姆達爾定律（Amdahl's Law）：系統優化應優先處理頻率最高的事件，且最終加速效益受限於無法優化的比例。
2. 管線化（Pipelining）：藉由重疊執行多個指令來提升效能，其核心目標在於提高系統的指令吞吐量（Throughput），而非縮短單指令延遲（Latency）。
3. 區域性原理（Principle of Locality）：分為時間區域性（Temporal Locality）與空間區域性（Spatial Locality）。
4. 通過預測提升效能（Performance via Prediction / Speculation）：透過猜測未來狀態（如分支預測）以解除控制冒險（Control Hazard）並提高指令級平行度（ILP）。

---

解題方法

本題屬概念辨析題，解題切入點在於逐項對照電腦架構的嚴謹定義：

• 定義判斷：核對「常用案例」、「區域性」、「預測投機」之敘述是否與標準定義一致。
• 數學推導／極限分析：引用阿姆達爾定律公式 $Speedup = \frac{1}{(1-f) + \frac{f}{s}}$ 分析系統效能瓶頸。
• 效能指標區分：明確區分「吞吐量（Throughput）」與「延遲（Latency）」在管線化設計中的定義與差異。

---

選項分析

• (a) 正確

  • 原因：「Make the common case fast」是電腦架構設計中最關鍵的指導原則之一。由於資源有限，優化發生頻率高的指令或事件（Common case）所獲得的整體效能提升，遠大於優化罕見案例（Rare cases）。此觀念亦為阿姆達爾定律的核心思想。

• (b) 正確

  • 原因：根據阿姆達爾定律（Amdahl's Law），設 $f$ 為可被加速模式處理的時間比例，$s$ 為加速模式相對原模式的加速倍數，則整體加速比（Speedup）為：
    $Speedup = \frac{1}{(1-f) + \frac{f}{s}}$

核心觀念

本題考查多核心處理器系統中快取一致性協定（Cache Coherence Protocols）與記憶體架構的核心概念，主要涵蓋以下重點：

1. 快取一致性維護機制：寫入失效（Write-Invalidate）與寫入更新（Write-Update）的定義差異。
2. 偽共享（False Sharing）：成因、對效能的影響及快取區塊（Cache Block/Line）競爭。
3. 窺探式協定（Snooping Protocol）：硬體運作原理與對共享通訊介面（如 Shared Bus）的依賴。
4. MESI 協定狀態轉換：Modified (M)、Exclusive (E)、Shared (S)、Invalid (I) 四種狀態下的讀寫權限與匯流排廣播訊號。
5. 架構可擴充性（Scalability）：窺探式（Snooping）與目錄式（Directory-based）協定的訊息傳遞模式及適用規模比較。

---

解題方法

解題時應針對每個選項的電腦結構學術定義與 MESI 狀態轉移機制進行精確比對：

1. 比較 Write-Invalidate 與 Write-Update：區分寫入時是傳送「失效訊號」還是「最新數據」。
2. 分析 False Sharing 邊界問題：確認獨立變數共用同一快取區塊時造成的無效乒乓效應（Cache Line Bouncing）。
3. 確認 Snooping 的物理傳輸介面：窺探機制需依賴具備廣播能力之共享介面（如 Shared Bus 或 Crossbar Broadcast）。
4. 檢查 MESI 寫入條件：確認狀態為 Shared (S) 時，寫入前是否必須向匯流排廣播 invalidate 訊號（BusUpgr / BusRdX）。
5. 分析系統擴充性（Scalability）：評估廣播（Broadcast）與點對點（Point-to-point）訊息傳遞在核心數增加時的效能瓶頸。

---

選項分析

(a) 錯誤

• 選項原文：In a "Write-Invalidate" protocol, a writing processor commands all other processors to update their copies of the data to the new value immediately.
• 詳細解析：當某個處理器執行寫入操作時，**寫入失效協定（Write-Invalidate Protocol）會向匯流排發送「Invalidate」訊號，命令其他擁有該資料副本的快取將其狀態標示為「無效（Invalid）」，而非將最新資料寫入更新給其他快取。選項所述「立即將其他快取的副本更新為新數值」為寫入更新協定（Write-Update / Write-Broadcast Protocol）**的行為。

(b) 正確

• 選項原文：False sharing occurs when two unrelated variables reside in the same cache block, causing unnecessary invalidations between cores even though they are not sharing data.
• 詳細解析：**偽共享（False Sharing）**發生於兩個邏輯上完全獨立的變數被配置在同一個快取區塊（Cache Block）中。當 Core 1 修改變數 A，Core 2 修改變數 B 時，由於快取一致性維護的基本單位是「整個快取區塊」，Core 1 的寫入會導致 Core 2 所持有的快取區塊整體失效，引發無效化開銷與快取區塊在核心間頻繁傳遞（Cache Line Bouncing），大幅降低系統效能。

核心觀念

本題考查 RISC-V 指令集架構（Instruction Set Architecture, ISA） 的四大核心設計特性：

1. 同步機制（Synchronization Primitives）：RISC-V 採用 Load-Reserved（$lr.w / lr.d$） 與 Store-Conditional（$sc.w / sc.d$） 指令對來構建無鎖（Lock-free）演算法與互斥鎖（Mutex）等原子操作（Atomic Operations）。
2. 分支指令設計（Branch Architecture）：RISC-V 摒棄傳統架構的條件碼／旗標暫存器（Condition Codes / Flags Register），採用直接比較兩暫存器數值的條件分支指令（如 beq, bne, blt, bge），以簡化管線（Pipeline）控制與指令排程。
3. 無條件跳躍與連結（Jump and Link）：jal 指令用於子程式呼叫（Function Call），會在跳轉的同時將下一條指令的位址（即 $PC + 4$）寫入目標暫存器（預設為 $x1$，即 ABI 規定的 ra 暫存器）。
4. 載入—儲存架構（Load-Store Architecture）：RISC 架構的基本原則之一，規定算術與邏輯運算指令（如 add, sub）僅能對暫存器內的資料進行操作，主記憶體的存取必須透過專門的 load 與 store 指令完成。

---

解題方法

依據 RISC-V 原廠規格書與計算機組織（Patterson & Hennessy）標準定義，逐一核對各選項敘述：

1. 檢驗同步指令機制：確認 $lr/sc$ 指令對的合作邏輯，$sc$ 成功與否取決於從 $lr$ 執行之後，該記憶體位址是否被其他寫入操作或中斷破壞保留狀態。
2. 檢驗狀態旗標設計：判斷 RISC-V 是否包含如 x86 的 EFLAGS 或 ARM 的 NZCV 旗標暫存器。
3. 檢驗返回位址計算：確認 RISC-V 基本指令長度（4 位元組）對應的下一條指令位址推導公式 $PC + 4$。
4. 檢驗架構類型限制：區分 Load-Store 架構（RISC 特性）與 Register-Memory 架構（x86 特性）對算術運算元的規定。

---

選項分析

• (a) 正確：RISC-V 使用 Load-Reserved（如 $lr.d$）與 Store-Conditional（如 $sc.d$）指令對實現原子操作（Atomic Operations）。$lr.d$ 會讀取目標記憶體位址的值並設置保留區（Reservation）；$sc.d$ 嘗試將新值寫回，若保留區在此期間未被破壞則寫入成功，這是實現原子比較並交換（Compare-And-Swap, CAS）與鎖（Locks）的基礎。

核心觀念

本題考驗經典指令管線化（Pipelining）中的三大**管線冒險（Pipeline Hazards）**類型及其解決機制：

1. 結構冒險（Structural Hazard）：當硬體資源有限，無法在同一個時脈週期內同時支援管線中多個指令的執行需求時發生（例如：指令擷取 IF 與資料存取 MEM 階段共用單一記憶體埠）。
2. 資料冒險（Data Hazard）：後續指令需要前面指令尚未寫回的結果（即讀取前寫入 RAW 相依性）。主要解決技術為轉發（Forwarding / Bypassing）與管線暫停（Stall / Bubble）。特別注意：Load-Use 資料冒險無法單靠轉發完全消除，必須搭配 1 個週期的暫停（Stall）。
3. 控制冒險（Control Hazard）：因分支指令（Branch）需要根據前述指令的結果決定下一條指令的位址，而此時後續指令已進入管線擷取。常用解決技術包含分支預測（Branch Prediction）、分支歷史表（Branch History Table, BHT）與分支目標緩衝區（Branch Target Buffer, BTB）。預測機制無法保證 100% 正確，預測錯誤（Misprediction）時仍會產生管線懲罰與暫停。

---

解題方法

依據計算機組織經典教材（Patterson & Hennessy: Computer Organization and Design）的標準定義與管線運作原理，對五個選項進行真偽判斷：

1. 檢視選項 (a)、(b)、(d) 之定義敘述是否精準符合教材定義。
2. 檢視選項 (c) 中轉發技術對於 Load-Use 冒險的物理時間限制。
3. 檢視選項 (e) 中動態分支預測機制是否具備「絕對保證（Guarantees）」之特性。

---

選項分析

• (a) 正確

  • 原文翻譯：結構冒險發生於硬體無法支援我們希望在同一時脈週期內執行的指令組合（例如：單一記憶體埠同時供指令擷取與資料存取使用）。
  • 詳細解析：此為結構冒險（Structural Hazard）的標準定義。當 CPU 採用單一記憶體（Single-ported Memory）而非分離式的指令記憶體與資料記憶體（Harvard Architecture）時，當某指令處於 MEM 階段進行資料讀寫，同時另一指令處於 IF 階段讀取指令，硬體資源便會發生衝突，導致結構冒險。

• (b) 正確

  • 原文翻譯：資料冒險發生於某指令依賴先前尚未完成指令的執行結果。
  • 詳細解析：此為資料冒險（Data Hazard）的標準定義。當發生「寫入後讀取（Read-After-Write, RAW）」資料相依時，若前級指令尚未將運算結果寫回暫存器檔案（Register File），後續指令若在 ID 階段讀取暫存器，將會讀到舊的錯誤資料。

• (c) 錯誤

  • 原文翻譯：轉發（Forwarding/Bypassing）可以解決資料冒險，包含「Load-Use」冒險。
  • 詳細解析：轉發技術（Forwarding）可將 ALU 的輸出或 MEM 暫存器的結果直接傳給後續指令的 ALU 輸入端，解決大部分算術指令之間的 RAW 資料冒險。

核心觀念

本題考查計算機效能評估（Computer Performance Evaluation）中的三大基本指標：指令數（Instruction Count, IC）、平均每指令週期數（Cycles Per Instruction, CPI）、以及 CPU 執行時間（CPU Time）。

計算機效能方程式（CPU Performance Equation）公式如下：
$\text{CPU Time} = \text{Instruction Count} \times \text{CPI} \times \text{Clock Cycle Time} = \frac{\text{Instruction Count} \times \text{CPI}}{\text{Clock Rate}}$

當程式包含多種不同類型的指令時，有效 CPI（Effective CPI） 為各類型指令 CPI 之加權平均（Weighted Average）：
$\text{Effective CPI} = \sum_{i=1}^{n} (\text{CPI}_i \times w_i)$
其中 $\text{CPI}_i$ 為第 $i$ 類指令所需的時脈週期數，$w_i$ 為該類指令佔總指令數的比例（Instruction Mix）。

---

解題方法

步驟一：計算有效 CPI（Effective CPI）
根據題目給定的指令組合與對應週期數：

• ALU 指令：占比 $40\% = 0.4$，每首需 3 cycles
• Load 指令：占比 $20\% = 0.2$，每首需 6 cycles
• Store 指令：占比 $10\% = 0.1$，每首需 5 cycles
• Branch 指令：占比 $30\% = 0.3$，每首需 2 cycles

帶入加權平均公式計算：
$\text{Effective CPI} = (0.40 \times 3) + (0.20 \times 6) + (0.10 \times 5) + (0.30 \times 2)$
$\text{Effective CPI} = 1.2 + 1.2 + 0.5 + 0.6 = 3.5$

步驟二：計算總 CPU 執行時間（Total CPU Time）
已知參數：

• 指令總數 $IC = 2 \times 10^9$
• 時脈頻率 $f = 3\text{ GHz} = 3 \times 10^9\text{ Hz}$
• 有效 CPI $\text{Effective CPI} = 3.5$

核心觀念

本題旨在考驗記憶體階層（Memory Hierarchy）與快取記憶體（Cache Memory）的基礎觀念，包含以下核心知識點：

1. 區域性原理（Locality of Reference）：
   • 時間區域性（Temporal Locality）：近期被存取的資料/指令，在不久的將來極可能再次被存取。
   • 空間區域性（Spatial Locality）：被存取的資料/指令，其相鄰位址的資料極可能接著被存取。
2. 快取寫入策略（Cache Write Policies）：
   • 直寫法（Write-Through）：資料寫入快取時，同步寫入下一階層記憶體（如 Main Memory）。
   • 寫回法（Write-Back）：資料僅先寫入快取並標記 Dirty Bit，直到該 Block 被替換時才寫回下一階層。
3. 快取的放置政策（Block Placement Policy）：
   • 組結合式（Set-Associative Cache）：記憶體區塊（Memory Block）透過映射公式（$\text{Block Address} \pmod{\text{Number of Sets}}$）決定放入特定的 Set，而在該 Set 內部的任何一個 Cache Line 均可任意放置。
4. 結合度（Associativity）對效能的影響與權衡（Trade-off）：
   • 平均記憶體存取時間公式：$\text{AMAT} = \text{Hit Time} + \text{Miss Rate} \times \text{Miss Penalty}$
   • 提高結合度（Increasing Associativity）能有效減少衝突失誤（Conflict Misses），使整體失誤率（Miss Rate）下降；但因增加 Tag 比較器與多路選擇器（Multiplexer），硬體邏輯複雜度提升，會使命中時間（Hit Time）變長。
5. 失誤懲罰（Miss Penalty）：當快取未命中（Cache Miss）時，從下一階層記憶體讀取一個 Block 至本階層快取所花費額外時間。

---

解題方法

解答本題時，需對題目要求的「何者為**錯誤（FALSE）**敘述」進行逐一判斷。

1. 對比標準教科書（如 Patterson & Hennessy）中針對 Temporal Locality、Write-Through、Set-Associative 與 Miss Penalty 的定義。
2. 著重分析選項 (d) 關於結合度（Associativity）改變時對 $\text{Miss Rate}$ 與 $\text{Hit Time}$ 的影響方向是否符合計算機結構的實際物理特性。

---

選項分析

核心觀念

本題考查**資料層級平行（Data-Level Parallelism, DLP）**的實現機制，包含 SIMD（單一指令多資料流）、向量架構（Vector Architecture）、GPU 架構與 SIMT 執行模型，以及系統架構中指令集擴充（ISA Extensions）、編譯器（Compiler）與作業系統（Operating System）的分工關係。

主要涵蓋的核心觀念如下：

1. Flynn 觀念分類法與 SIMD：SIMD 透過單一指令控制多個算術邏輯單元（ALU），對向量或矩陣中的多個資料元素同時進行運算。
2. 記憶體延遲處理策略（Latency Reduction vs. Latency Hiding）：
   • CPU：以「降低延遲（Latency Reduction）」為核心目標，採用大容量快取（Large Cache）、分支預測與亂序執行（Out-of-Order Execution）。
   • GPU：以「隱藏延遲（Latency Hiding）」為核心目標，採用巨量多執行緒（Massive Multithreading）與硬體 Warp 排程器，當執行緒因記憶體存取卡頓（Stall）時，無縫切換執行其他就緒執行緒。
3. 向量架構（Vector Architecture）：具備深度的向量暫存器（Vector Registers）與流水線化（Pipelined）執行單元，一條向量指令即可處理長度達數十至數百個元素的向量。
4. SIMT（Single Instruction, Multiple Thread）模型：GPU 專用的程式設計與硬體執行模型，程式員以純量執行緒（Scalar Threads）的角度撰寫程式，硬體排程器將執行緒打包成 Warp/Wavefront 並在 SIMD 硬體上同時執行相同指令流。
5. 電腦抽象層劃分（Abstraction Layers）：指令集架構（ISA）是硬體與編譯器的介面。所有 ISA 擴充（如 x86 AVX、RISC-V Vector Extension）對編譯器均為完全公開可見。編譯器可進行自動向量化（Auto-vectorization）或讀取 Intrinsics 生成向量指令；作業系統僅負責上下文切換（Context Switch）時保存與還原向量暫存器的狀態。

---

解題方法

本題要求選出關於 DLP、SIMD 及 GPU 敘述中**錯誤（FALSE）**的選項。切入點為比對電腦系統階層劃分與各平行架構的運作原理：

1. 分析軟體與 ISA 介面劃分：指令集擴充（ISA Extensions）如 AVX、RISC-V Vector Extension 屬於計算機架構的 ISA 層級。編譯器必須識別這些指令與向量暫存器，才能在編譯期生成目標機器碼。因此，宣稱「SIMD 擴充完全由作業系統處理且對編譯器不可見」的敘述違反軟體與硬體介面的基本設計邏輯。

步驟與衝突分析

指令	需要的前置資料	供應階段	何時可供應	產生衝突
ld x10,0(x2)	—	MEM (載入完成)	MEM 結束時	–
add x11,x10,x3	x10 (自 ld)	EX	需要在 EX，但 ld 只有在 MEM 後才有資料 → Load‑Use Hazard
sub x12,x11,x4	x11 (自 add)	EX	add 於 EX 末可轉發 → 無衝突
beq x12,x0,Label	x12 (自 sub)	EX (判斷)	sub 於 EX 末可轉發 → 無衝突

核心觀念

本題考查虛擬記憶體（Virtual Memory）架構中的定址劃分（Address Translation Breakdown）與頁表（Page Table）容量計算。

1. 虛擬位址結構（Virtual Address Architecture）：
   虛擬位址（Virtual Address, VA）長度為 $n$ 位元，可拆分為兩部分：

   • 虛擬頁號（Virtual Page Number, VPN）：用於索引頁表項（PTE）或 TLB。
   • 頁偏移量（Page Offset, PO）：指示資料在頁面內的具體位址，在虛擬位址與實體位址中維持相同長度與數值。

2. 頁面大小與偏移量關係：
   若頁面大小（Page Size）為 $P$ 位元組，則頁偏移量所需的位元數 $p$ 為：
   $p = \log_2(P)$

3. 虛擬頁號長度計算公式：
   $\text{VPN bits} = \text{Virtual Address bits} - \text{Page Offset bits}$

4. 單層（扁平化）頁表容量計算公式：
   在單層頁表架構下，系統必須為每一個可能的虛擬頁面建立對應的頁表項（PTE）。

   • 頁面總數（Total Virtual Pages）$= 2^{\text{VPN}}$
   • 頁表總容量（Page Table Size）$= 2^{\text{VPN}} \times \text{PTE Size}$

---

解題方法

(a) 計算虛擬頁號（VPN）的位元數

1. 確定頁偏移量（Page Offset）位元數：
   已知頁面大小為 $8\text{ KB}$：
   $8\text{ KB} = 8 \times 1024\text{ Bytes} = 2^3 \times 2^{10}\text{ Bytes} = 2^{13}\text{ Bytes}$
   因此，頁偏移量需佔用 $13\text{ bits}$。

2. 推導 VPN 位元數：
   已知虛擬位址總長度為 $40\text{ bits}$：
   $\text{VPN} = \text{Virtual Address} - \text{Page Offset} = 40 - 13 = 27\text{ bits}$

(b) 計算單層頁表總容量（Bytes）

1. 計算頁表項總數量：
   VPN 長度為 $27\text{ bits}$，代表虛擬位址空間最多包含 $2^{27}$ 個虛擬頁面。在單層頁表中，每個頁面均需對應一個 PTE：
   $\text{Total Entries} = 2^{27}\text{ entries}$

2. 計算頁表總容量：
   已知每個 PTE 大小為 $4\text{ bytes}$（即 $2^2\text{ bytes}$）：

核心觀念

本題考查計算機組織中**組相聯快取記憶體（Set-Associative Cache Memory）**的實體位址切割（Address Breakdown）機制。

在採用 Byte 定址的記憶體架構中，$n$-bits 的實體位址（Physical Address）會依序劃分為三個核心欄位：
$\text{Physical Address} = \text{Tag} + \text{Index} + \text{Offset}$

各欄位的數學定義與計算公式如下：

1. 區塊偏移量（Offset bits）：用於定址快取區塊（Cache Block / Line）內部的特定 Byte。
   $\text{Offset bits} = \log_2(\text{Block Size in Bytes})$
2. 總組數（Number of Sets）：快取記憶體劃分出的組（Set）數量。組相聯快取將多個區塊歸為一組，其公式為：
   $\text{Number of Sets} = \frac{\text{Total Cache Capacity}}{\text{Associativity} \times \text{Block Size}}$
3. 組索引位元（Index bits）：用於定址快取中的特定組。
   $\text{Index bits} = \log_2(\text{Number of Sets})$
4. 標籤位元（Tag bits）：用於儲存主記憶體區塊的高位址資訊，以便在快取比對時判斷資料是否命中（Hit）。
   $\text{Tag bits} = \text{Total Physical Address bits} - (\text{Index bits} + \text{Offset bits})$

---

解題方法

根據題目給定條件：

• 實體位址長度（Physical Address Space）$= 64 \text{ bits}$
• L2 快取總容量（Cache Size）$= 256 \text{ KB} = 256 \times 2^{10} \text{ Bytes} = 2^{18} \text{ Bytes}$
• 連帶關聯度（Associativity）$= 8\text{-way} = 2^3$
• 區塊大小（Block / Line Size）$= 64 \text{ Bytes} = 2^6 \text{ Bytes}$

詳細推導步驟如下：

1. 計算 Offset 位元數：
   $\text{Offset bits} = \log_2(64) = 6 \text{ bits}$

2. 計算快取總組數（Number of Sets）：
   每個組包含 $8$ 個區塊，單一組的儲存容量為 $8 \times 64 \text{ Bytes} = 512 \text{ Bytes} = 2^9 \text{ Bytes}$。
   全快取的總組數為：
   $\text{Number of Sets} = \frac{256 \text{ KB}}{8 \times 64 \text{ Bytes}} = \frac{2^{18} \text{ Bytes}}{2^9 \text{ Bytes}} = 2^9 = 512 \text{ sets}$