108 年 國立中山大學電機工程學系碩士班己組《計算機結構》

核心觀念

int 在 MIPS 中占 4 bytes，因此陣列索引必須先乘以 4：

乘以 4 可用左移 2 位的 sll 完成。此題另有三個重點：

• A[i] 必須先載入，並同時作為運算值與 B 的索引。
• A[i]==0 時必須立即離開，避免不必要地讀取 B[A[i]]，這對應 C 的短路求值。
• 迴圈條件 i<20 可放在 i++ 之後作為回跳條件。因為 i 從 0 開始，且只有完成迴圈本體後才遞增，所以每次進入 LOOP 時必定有 $0\le i<20$。

以下使用基本 MIPS 指令，不使用 li、move 等偽指令。

暫存器配置

(a) 程式執行時間之正式算式推導

程式執行時間（CPU Execution Time）基本公式為：
$\text{CPU Execution Time} = \text{CPU Clock Cycles} \times \text{Clock Cycle Time} = \frac{\text{CPU Clock Cycles}}{\text{Clock Rate}}$

若將總時脈週期數拆解為指令數（Instruction Count, $\text{IC}$）與平均每指令週期數（Cycles Per Instruction, $\text{CPI}$）：
$\text{CPU Clock Cycles} = \text{Instruction Count (IC)} \times \text{CPI}$

當處理器包含不同指令類別（Type $i$），各類別指令週期數為 $\text{CPI}_i$，執行次數為 $\text{IC}_i$ 時，正式算式如下：
$\text{CPU Clock Cycles} = \sum_{i} (\text{IC}_i \times \text{CPI}_i)$
$\text{CPU Execution Time} = \frac{\sum_{i} (\text{IC}_i \times \text{CPI}_i)}{\text{Clock Rate}}$

(b) 最壞情況執行時間計算

假設說明

依據第 1 題 C 語言程式碼之最簡 MIPS 組合語言轉譯結果，在最壞情況下，迴圈完整執行 20 次（即 $i = 0 \sim 19$ 均滿足條件），並於第 21 次檢查時條件不成立跳出迴圈。

指令數量統計 (Instruction Count)

1. 迴圈前初始化：1 次 Arithmetic (add)
2. 迴圈內單次疊代（執行 20 次）：
   • Arithmetic (9 次)：slti, sll, add, sll, add, add, add, add, addi
   • Data transfer (3 次)：lw, lw, sw
   • Jump/Branch (3 次)：beq, beq, j
3. 迴圈結束判定（第 21 次）：1 次 Arithmetic (slti)、1 次 Branch (beq)

• $\text{IC}_{\text{Arith}} = 1 + 20 \times 9 + 1 = 182$
• $\text{IC}_{\text{Data}} = 20 \times 3 = 60$

(a)

IEEE 754 單精度浮點數格式由 32 位元組成，定義如下：
$S = (-1)^s \times (1 + F) \times 2^{E - 127}$

解析位元串 1 01111101 00100000000000000000000：

1. 符號位元 ($s$)：$1$（代表負數）
2. 偏壓階數 ($E$)：$01111101_2 = 125_{10}$
   • 實際指數 $e = E - 127 = 125 - 127 = -2$
3. 尾數欄位 ($F$)：$00100000000000000000000_2 = 2^{-3} = 0.125$
   • 有效位元 $M = 1 + F = 1.001_2 = 1 + 0.125 = 1.125$

計算十進位數值：
$S = (-1)^1 \times 1.125 \times 2^{-2} = -1.125 \times 0.25 = -0.28125$

【答案】：$-0.28125$

(b)

1. 溢位 (Overflow)

   • 定義：運算結果之絕對值過大，超越該浮點數格式所能表示的最大有限範圍（單精度階數 $E > 254$ 或 $e > 127$），結果通常被設定為 $\pm\infty$。
   • 範例：單精度運算 $2^{120} \times 2^{20} = 2^{140}$，指數 $140 > 127$，超出單精度最大階數範圍，產生溢位。

2. 下溢 (Underflow)

   • 定義：非零運算結果之絕對值過小，低於該格式正規化與非正規化數值所能精確表示的最小非零範圍（單精度絕對值小於 $2^{-149}$），導致精確度喪失或被捨入為 0。
   • 範例：單精度運算 $2^{-100} \times 2^{-60} = 2^{-160}$，數值小於單精度最小可表示非正規化數 $2^{-149}$，產生下溢。

核心觀念

這題考的是如何把新指令的資料流映射到單周期 MIPS 資料路徑，並判斷現有元件是否能在同一個週期內完成所有運算。

指令語意為：

因此，指令要在同一週期內完成三件事：讀取 Reg[Rd] 作為記憶體位址、讀取記憶體資料並加上 Reg[Rs]，最後將結果寫回 Reg[Rt]。

以下依圖中的標準指令欄位假設：Rs 位於 Instruction[25:21]、Rt 位於 Instruction[20:16]、Rd 位於 Instruction[15:11]。

解題方法

先逐步追蹤運算資料：

1. 暫存器檔讀取 Reg[Rd] 與 Reg[Rs]。
2. 將 Reg[Rd] 送至資料記憶體位址端，讀出 Mem[Reg[Rd]]。
3. 將記憶體讀出值與 Reg[Rs] 相加。
4. 將總和寫入 Reg[Rt]。

原圖的 ALU 位於資料記憶體之前，負責計算記憶體位址；但本指令需要在讀出記憶體資料後再做加法。同一個組合式 ALU 無法在同一週期先產生記憶體位址、再等待記憶體讀出後進行第二次運算，因此要加入新的加法路徑。

(a) 可沿用的既有元件

• 暫存器檔：讀取 Reg[Rd]、Reg[Rs]，並將結果寫回 Reg[Rt]。
• 資料記憶體：以 Reg[Rd] 為位址讀取資料。
• 目的暫存器選擇器 RegDst：選擇 Instruction[20:16]，也就是 Rt，作為寫入目的暫存器。
• 暫存器寫入控制 RegWrite：啟用寫回。
• 資料記憶體讀取控制 MemRead：啟用讀取。

資料記憶體位址可直接接上暫存器檔輸出的 Reg[Rd]，不必用原本的 ALU 計算位址。

(b) 需要新增或擴充的功能元件

1. 暫存器讀取位址選擇器：原圖第二個讀取埠固定讀取 Instruction[20:16]。本指令需要讀取位於 Instruction[15:11] 的 Rd，因此需加入選擇器，讓第二個讀取埠能選擇 Rt 欄位或 Rd 欄位。
2. 加法器：接收資料記憶體讀出值與 Reg[Rs]，計算兩者的總和。

核心觀念

本題考查計算機結構中**快取記憶體（Cache Memory）**的核心設計原理，包含以下三大主軸：

1. 快取映射機制（Cache Mapping Schemes）：

   • 主記憶體位址（Memory Address）映射至快取區塊（Cache Line / Block）的三種架構：直映式（Direct-Mapped）、組關聯式（Set-Associative） 與 全關聯式（Fully Associative）。
   • 位址欄位切割公式：
     • 若總區塊數為 $N$，總組數（Number of Sets）為 $S$，每組區塊數（Ways / Degree of Associativity）為 $W$，則 $N = S \times W$。
     • 位址格式：$\text{Block Address} = \text{Tag} \times S + \text{Index}$。
     • $\text{Index Bits} = \log_2(S)$
     • $\text{Tag Bits} = \text{Block Address Bits} - \text{Index Bits}$

2. 快取控制位元（Cache Control Bits）：

   • 有效位元（Valid Bit）：用以標示該快取區塊內存放的資料是否有效（Valid / Invalid）。
   • 髒位元（Dirty Bit）：應用於寫回策略（Write-Back Policy），用以記錄該快取區塊資料是否已被 CPU 修改而與主記憶體不一致。

3. 快取替換政策與命中比對（Replacement Policy & Trace Analysis）：

   • 在組關聯式與全關聯式快取中，當該組（Set）或全快取空間已滿且發生未命中（Miss）時，需利用 最近最少使用政策（LRU, Least Recently Used） 決定被淘汰（Evict）的區塊。

解題方法

1. (a) 三大映射機制定義與比較：

   • 從映射函數（Mapping Function）、硬體搜尋成本（比較器數量）、衝突未命中率（Conflict Miss Rate）三個面向切入分析。

2. (b) 有效位元與髒位元運作機制：

   • 從開機／清空（Boot / Cold Start）、資料載入（Line Fill）、寫入策略（Write-Back）等動態情境說明其重要性。

3. (c) 4 區塊 Direct-Mapped Cache 架構繪製與解說：

   • 總區塊數 $N = 4 = 2^2 \Rightarrow \text{Index Bits} = 2$ bits。
   • 繪製含有 解碼器（Decoder）、快取記憶體陣列（Valid, Tag, Data）、標記比較器（Tag Comparator） 及 AND 閘（Hit Signal Generation） 的完整邏輯電路圖並說明存取流程。

4. (d) 快取參考位址追蹤（Cache Trace Analysis）：

   • 前提假設：題目給定的參考位址序列 $(1, 74, 39, 28, 21, 5, 7, 39, 20, 33, 1, 21)$ 為區塊位址（Block Address），總區塊數 $N = 8$。初始狀態為空（All Valid Bits = 0）。
   • Direct-Mapped ($N=8, S=8, W=1$)：$\text{Index} = \text{Block Address} \pmod 8$，$\text{Tag} = \lfloor \text{Block Address} / 8 \rfloor$。
   • 4-Way Set-Associative ($N=8, W=4 \Rightarrow S=2$)：$\text{Index} = \text{Block Address} \pmod 2$，$\text{Tag} = \lfloor \text{Block Address} / 2 \rfloor$。每組容量 4 個區塊，採 LRU 替換。
   • Fully Associative ($N=8, W=8 \Rightarrow S=1$)：無 Index，$\text{Tag} = \text{Block Address}$。全快取容量 8 個區塊，採 LRU 替換。

子題詳解

(a) What are direct-mapped cache, set-associative cache and fully associative cache?

1. 直映式快取（Direct-Mapped Cache）：

   • 定義：主記憶體的每一個區塊只能映射到快取中唯一指定的一個特定位置（Block Location）。
   • 映射公式：$\text{Cache Block Index} = (\text{Block Address}) \bmod (\text{Total Cache Blocks})$。
   • 特點：硬體結構最簡單，只需要 $1$ 個比較器（Comparator），存取時間最快；但容易產生大量的衝突未命中（Conflict Misses）。

2. 組關聯式快取（Set-Associative Cache）：

   • 定義：將快取分割成若干個「組（Set）」，每個 Set 包含 $W$ 個區塊（稱為 $W$-way）。主記憶體區塊先映射到特定的 Set，在該 Set 內則可以放置於 $W$ 個區塊中的任意位置。
   • 映射公式：$\text{Cache Set Index} = (\text{Block Address}) \bmod (\text{Total Cache Sets})$。
   • 特點：介於直映式與全關聯式之間的折衷方案。若為 $W$-way，則需要 $W$ 個比較器平行比對。兼具合理成本與較低的 Miss Rate。

3. 全關聯式快取（Fully Associative Cache）：

   • 定義：主記憶體的任意區塊可以放置在快取中的任何一個自由位置（不需 Index 解碼）。
   • 映射方式：無 Index 欄位，整個區塊位址皆作為 Tag。
   • 特點：完全消除了衝突未命中（Conflict Miss），快取利用率最高；但搜尋時必須與所有區塊的 Tag 同時進行平行比對，硬體需要 $N$ 個比較器，成本極高且延遲較大。

(b) Why do we need valid bits and dirty bits in cache designs?

1. 有效位元（Valid Bit）的必要性：

   • 目的：用以標示快取區塊內目前所儲存的資料是否為真實且有效的主記憶體資料。
   • 運作情境：
     • 開機／復位（Power-on / Reset）：快取內的 SRAM 隨機狀態值無效，系統將所有區塊的 Valid Bit 設為 0。此時若 CPU 存取快取，即便 Tag 意外匹配，亦因 Valid Bit 為 0 而判定為 Miss（Compulsory Miss），避免 CPU 讀取到未初始化的垃圾資料（Garbage Data）。
     • 快取刷洗（Cache Flush / Invalidation）：當進行 DMA 傳輸或多核心快取一致性（Cache Coherence）維護時，可直接將特定的 Valid Bit 清零（0）以宣告該資料失效。

2. 髒位元（Dirty Bit）的必要性：

   • 目的：在使用**寫回策略（Write-Back Policy）**的快取設計中，用以記錄該區塊資料是否曾被 CPU 寫入修改過（即快取資料與下層主記憶體資料不一致）。
   • 運作情境：
     • 當 CPU 執行 Write Hit 時，資料僅更新於 Cache，並將該區塊的 Dirty Bit 設為 1，暫不寫回主記憶體以節省匯流排頻寬。
     • 當該區塊未來因 Miss 需被替換（Evict）出快取時，控制邏輯先檢查 Dirty Bit：
       • 若 Dirty Bit $= 1$：代表資料已被修改，必須將該區塊寫回（Write Back）主記憶體，隨後才能載入新資料。
       • 若 Dirty Bit $= 0$：代表資料與主記憶體一致，直接覆蓋即可，無需額外執行寫回主記憶體的動作。

(c) Architecture of a Direct-Mapped Cache with 4 Blocks

1. 架構圖（Architecture Diagram）

4 區塊 Direct-Mapped Cache 的硬體結構包含：CPU Address 拆解、2-to-4 Decoder、4 行 Cache SRAM 陣列、1 個 Tag Comparator 與 1 個 AND 閘。

                    CPU Address
     +-------------------+---------------+------------------+
     |     Tag Bits      | Index (2 bits)| Offset (b bits)  |
     +-------------------+---------------+------------------+
               |                 |                 |
               |                 v                 v
               |          +--------------+   Data Selection
               |          | 2-to-4 Decoder|   (Block Offset)
               |          +--------------+
               |                 | (Select Line 0..3)
               |                 v
               |     +---+---------------+------------------+
               |     | V |   Tag Array   |    Data Array    |
               |     +---+---------------+------------------+
               |   0 |   |               |                  |
               |   1 |   |               |                  |
               |   2 |   |               |                  |
               |   3 |   |               |                  |
               |     +---+---------------+------------------+
               |           | Valid           | Tag Out
               v           v                 |
            +-----------------+              |
            | Tag Comparator  |<-------------+
            +-----------------+
                    | Equal (1/0)
                    v
                 +-----+
                 | AND |--------------------> Cache Hit / Miss Signal
                 +-----+
                    ^
                    | Valid Bit

2. 運作細節說明（Operating Steps）

• Step 1: 位址拆解（Address Splitting）：
  CPU 發出 $M$-bit 位址，拆解為三大欄位：

  • Offset（$b$ bits）：用來定位區塊內的特定 Byte/Word。
  • Index（$2$ bits）：因為總區塊數 $N = 4 = 2^2$，故需 2 bits（$A_1 A_0$）來定址 4 個 Cache Lines。
  • Tag（$M - 2 - b$ bits）：剩餘的高位元用於唯一辨別該區塊的主記憶體來源。

• Step 2: 解碼與索引（Indexing）：
  2-bit 的 Index 輸入至 2-to-4 Decoder，活化（Enable）Cache 陣列中相對應的唯一 Index 區塊（Line 0, 1, 2 或 3），並同時讀出該區塊的 Valid Bit、Tag 與 Data。

• Step 3: 標記比對與有效性檢查（Tag Match & Valid Check）：

  • 將 Cache 讀出的 Tag Out 與 CPU Address 的 Tag Bits 送入 Comparator 進行相等性比較（Equal）。
  • 將 Comparator 輸出與該區塊的 Valid Bit 送入 AND 閘。

• Step 4: Hit / Miss 判定與資料輸出：

  • Cache Hit（AND 輸出為 1）：表示資料有效且 Tag 匹配。此時控制邏輯透過 Offset 從 Data Block 中選擇目標 Word/Byte 傳回 CPU。
  • Cache Miss（AND 輸出為 0）：表示資料無效或 Tag 不匹配。