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

(1) MIPS 程式碼逐行註釋

li $t1, 0            # 將迴圈變數 i ($t1) 初始化為 0
for: lw $s1, $s1($a1) # 以 $s1 為偏移量從陣列 A 載入元素 A[s1]（或對應索引之元素 A[i]）至暫存器 $s1
beq $s1, $0, end     # 若 $s1 的值等於 0，則跳轉至 end 結束迴圈
lw $s2, $s1($a2)     # 以 $s1 的值為偏移量從陣列 B 載入元素 B[s1] 至暫存器 $s2
add $s1, $s2, $s1    # 計算 $s2 與 $s1 之和，並將結果存入 $s1 ($s1 = s2 + s1)
add $s1, $s1, $t1    # 將迴圈變數 i ($t1) 加至 $s1 ($s1 = s1 + i)
addi $t1, $t1, 1     # 將迴圈變數 i ($t1) 遞增 1
bne $t1, 20, for     # 若迴圈變數 i ($t1) 不等於 20，則跳回 for 標籤繼續執行
end:                 # 迴圈結束標籤

---

(2) 對應的 C 語言程式碼

假設暫存器 $a1 與 $a2 分別儲存陣列 A 與 B 之基底位址，且暫存器 $t1 代表變數 i：

第 2 題詳解

(a) Amdahl's law

核心觀念

Amdahl's law（阿姆達爾定律）用來估計：只改善系統中的某一部分後，整體效能最多能提升多少。關鍵在於「被改善部分原本占總執行時間的比例」。

設：

• $f$：原本花在可改善部分的時間比例
• $1-f$：不可改善部分的時間比例
• $S$：可改善部分的加速倍數

原本總執行時間設為 $T$，改善後：

$$T_{\text{new}}=(1-f)T+\frac{fT}{S}$$

因此整體加速比為：

$$\text{Overall Speedup} =\frac{T}{T_{\text{new}}} =\frac{1}{(1-f)+\frac{f}{S}}$$

當可改善部分被加速到無限快時，整體最大加速比仍為：

$$\text{Maximum Speedup}=\frac{1}{1-f}$$

解題方法

先找出改善部分占原始執行時間的比例 $f$，再找出該部分的加速倍數 $S$，代入公式即可。比例必須是「執行時間比例」，不能直接把指令數比例當成答案。

例如某部分占 $40\%$，且加速 $5$ 倍：

$$\text{Overall Speedup} =\frac{1}{0.6+\frac{0.4}{5}} =\frac{1}{0.68} \approx 1.47$$

雖然局部加速達 $5$ 倍，整體只加速約 $1.47$ 倍。

解題技巧與陷阱

• 可改善部分比例越小，局部最佳化對整體效能的幫助越有限。
• $S$ 越大，整體加速比越接近上限，呈現報酬遞減。
• 常見錯誤是直接以 $fS$ 當作整體加速比；正確做法必須先計算改善後的總執行時間。

---

(b) Data hazard

核心觀念

Data hazard（資料危障）發生在管線重疊執行時，某一指令需要使用的資料，受到其他尚未完成指令的讀寫順序影響。

例如：

I1: ADD R1, R2, R3
I2: SUB R4, R1, R5

指令 $I2$ 必須讀取 $I1$ 產生的 $R1$。若 $I2$ 讀取 $R1$ 時，$I1$ 尚未完成寫回，就會產生資料危障。

主要分為三類：

1. RAW（Read After Write）

   讀取發生在寫入之前，稱為真實資料相依。

   I1: R1 ← R2 + R3
   I2: R4 ← R1 - R5
   

   $I2$ 必須等候 $I1$ 寫入 $R1$。這是一般五級管線中最常見的資料危障。

2. WAR（Write After Read）

   寫入發生在前一指令讀取之前，稱為反相依。

   I1: 讀取 R1
   I2: 寫入 R1
   

   若採用亂序執行，$I2$ 太早寫入可能破壞 $I1$ 尚未讀取的資料。暫存器重新命名可消除這類名稱相依。

3. WAW（Write After Write）

   多個指令寫入同一位置，但寫回順序錯誤，稱為輸出相依。

   I1: 寫入 R1
   I2: 寫入 R1
   

   若 $I2$ 先寫回，隨後 $I1$ 才寫回，最終結果便不符合程式順序。暫存器重新命名與依序提交可解決此問題。

解題方法

分析管線題時，依序判斷：

1. 前一指令產生哪些資料。
2. 後一指令讀取或寫入哪些資料。
3. 讀寫發生的管線階段與時間。
4. 是否能透過 forwarding（資料前遞）直接提供結果。
5. 若無法及時取得，便插入 stall（停滯）或 bubble（氣泡）。

在典型五級管線：

$$\text{IF}\rightarrow\text{ID}\rightarrow\text{EX}\rightarrow\text{MEM}\rightarrow\text{WB}$$

ALU 指令的結果通常可由前遞解決，但典型的 load-use hazard：

I1: LW  R1, 0(R2)
I2: ADD R3, R1, R4

因為載入資料到 $I1$ 的 MEM 階段後才取得，$I2$ 在下一個 EX 階段通常來不及使用，必須插入至少一個停滯週期。

解題技巧與陷阱

• 看到「前一指令寫入、後一指令讀取」先判斷 RAW。
• 經典依序五級管線通常只需特別處理 RAW；WAR、WAW 主要出現在亂序執行。
• Data hazard 不等於 structural hazard（硬體資源衝突），也不等於 control hazard（分支控制衝突）。
• Forwarding 可降低資料危障，但無法消除所有 load-use hazard。

---

(c) Exceptions

核心觀念

Exception（例外）是處理器在正常執行指令流程中偵測到特殊事件後，暫停原本的控制流程，轉移至作業系統或例外處理程式處理的機制。

常見例外包括：

• 非法指令
• 算術溢位
• 記憶體存取錯誤
• 頁面錯誤（page fault）
• 系統呼叫或軟體陷阱（trap）

依發生時機可分為：

（a）IEEE 754 單精度解碼

核心觀念

IEEE 754 單精度格式為：

$$\text{sign}\;|\;\text{exponent}\;|\;\text{fraction} =1\text{ bit}+8\text{ bits}+23\text{ bits}$$

正常數的數值為：

$$V=(-1)^s(1.F)_2\,2^{E-127}$$

其中 $127$ 為單精度的偏移值。

解題方法與計算

將題目位元串分割：

$$S=1\;|\;01111101\;|\;11000000000000000000000$$

因此：

• 符號位：$s=1$，表示負數。
• 指數欄位：

$$E=(01111101)_2=125$$

• 指數實際值：

$$e=E-127=125-127=-2$$

• 有效數：

$$(1.F)_2=(1.110000\cdots)_2 =1+2^{-1}+2^{-2} =1.75$$

指數欄位不是全 $0$，也不是全 $1$，所以這是正常化數：

$$\begin{aligned} V &=(-1)^1(1.75)2^{-2}\\ &=-1.75\times\frac14\\ &=-0.4375 \end{aligned}$$

解題技巧

先看最高位判斷正負，再將後 8 位轉成十進位並扣除偏移值 $127$。小數欄位最左端的隱藏位必須補上 $1$，不可直接把 fraction 欄位當成完整有效數。

【答案】$\boxed{-0.4375}$

---

（b）浮點數加法流程

核心觀念

浮點數相加的關鍵是先將兩數的指數對齊，再進行有效數加減，最後完成正規化與捨入。一般浮點數可表示為：

$$A=(-1)^{s_A}M_A2^{e_A},\qquad B=(-1)^{s_B}M_B2^{e_B}$$

其中 $M_A,M_B$ 為有效數，$e_A,e_B$ 為實際指數。

浮點數加法流程圖

開始
  ↓
拆解兩個輸入：符號、指數、fraction
  ↓
特殊值分類：NaN、無窮大、零、非規格化數
  ├─特殊值可直接決定結果
  │      ↓
  │   產生特殊結果、封裝、結束
  │
  └─有限數運算
         ↓
補上正常數的隱藏位 1，形成有效數
         ↓
比較兩數指數與絕對值大小
         ↓
將較小指數的有效數右移以完成指數對齊
並保留 G、R、S 三個捨入位
         ↓
符號相同？
  ├─是 → 有效數相加，結果符號取共同符號
  │
  └─否 → 較大絕對值減去較小絕對值
          結果符號取較大絕對值者
         ↓
結果有效數是否為 0？
  ├─是 → 輸出零
  │
  └─否
         ↓
正規化
  ├─加法產生進位 → 有效數右移 1 位，指數加 1
  └─減法產生前導零 → 有效數左移，指數相應減少
         ↓
依捨入模式處理 G、R、S
         ↓
捨入是否產生新的進位？
  ├─是 → 再右移 1 位，指數加 1
  └─否
         ↓
檢查指數溢位、下溢與非規格化結果
         ↓
重新封裝符號、指數與 fraction
         ↓
結束

指數對齊

假設 $e_A>e_B$，令：

$$d=e_A-e_B$$

則：

$$\begin{aligned} A+B &=M_A2^{e_A}+M_B2^{e_B}\\ &=\left(M_A+M_B2^{-d}\right)2^{e_A} \end{aligned}$$

因此必須將 $M_B$ 右移 $d$ 位，使兩個有效數具有相同指數。右移時被移出的位元不能全部丟棄，須保留：

• $G$：Guard bit，第一個被捨棄的位元。
• $R$：Round bit，第二個被捨棄的位元。
• $S$：Sticky bit，其餘所有被捨棄位元的 OR 結果。

同號與異號運算

1. 同號

   兩個有效數相加：

   $$M=M_A+M_B$$

   結果符號為兩數共同符號。若結果形成 $10.xxxx_2$，必須右移一位並將指數加一。

2. 異號

   先比較兩數絕對值。比較順序為：

   1. 比較實際指數；
   2. 指數相同時比較有效數。

   再以較大絕對值減去較小絕對值：

   $$M=M_{\text{大}}-M_{\text{小}}$$

   結果符號取較大絕對值者。減法後常出現 $0.00\cdots 1xxx_2$，須使用前導零偵測器決定左移位數。

正規化與捨入

正常化數的有效數形式應為：

$$1.xxxxx_2$$

若加法產生進位：

$$10.xxxxx_2\rightarrow1.0xxxxx_2$$

有效數右移一位，指數加一。

若減法產生前導零，左移 $k$ 位：

$$0.00\cdots 1xxxxx_2 \rightarrow 1.xxxxx_2$$

指數減少 $k$。

題目未指定捨入模式，以下採 IEEE 754 預設的「最接近且取偶數」捨入。若保留部分的最低位為 $L$，則捨入進位條件為：

$$\text{Increment} =G\land(R\lor S\lor L)$$

捨入後若有效數由 $1.111\cdots_2$ 變成 $10.000\cdots_2$，須再右移一位並增加指數。

特殊值處理

• 任一輸入為 NaN，結果為 NaN。
• $+\infty+(-\infty)$ 為 NaN。
• 同號無窮大相加，結果為同號無窮大。
• 無窮大與有限數相加，結果為該符號的無窮大。
• $0+x=x$。
• 相反數相加形成精確零；在預設捨入模式下輸出 $+0$。

解題技巧與常見陷阱

• 不可直接將兩個 fraction 欄位相加，正常數必須先補隱藏位 $1$。
• 指數較小者的有效數必須右移，不能將較大指數者左移。
• 異號相加本質上是有效數相減，必須判斷較大絕對值及結果符號。
• 捨入前不可省略 G、R、S，否則無法得到正確的 IEEE 754 結果。
• 指數溢位必須在正規化與捨入完成後判斷。

【答案】浮點數加法的完整順序為：解包與特殊值判定 → 指數對齊 → 有效數加減 → 正規化 → GRS 捨入 → 指數範圍處理 → 重新封裝。

---

（c）浮點加法硬體單元設計

設計假設與硬體規格

題目未指定捨入模式，以下採 IEEE 754 預設的最接近且取偶數捨入，並保留捨入模式控制輸入。

• 輸入：$A[31:0]$、$B[31:0]$
• 輸出：$R[31:0]$
• 內部有效數：正常數的隱藏位加上 23 位 fraction，共 24 位。

核心觀念

本題考查經典五級管線化 MIPS 處理器的：

1. 五個管線階段及其工作內容。
2. 資料路徑中各硬體元件的連接方式。
3. lw 指令所需的控制訊號。
4. 控制訊號如何透過管線暫存器，與指令及資料同步向後傳遞。

lw 指令的功能為：

$$\texttt{lw rt, offset(rs)}$$

其執行語意為：

$$R[rt] \leftarrow \mathrm{Memory}[R[rs]+\mathrm{SignExt}(offset)]$$

因此，lw 必須先計算有效位址，再讀取資料記憶體，最後將資料寫回暫存器。

---

(a) 五個管線階段及其工作

1. IF：Instruction Fetch

指令擷取階段，工作包括：

• 以程式計數器 $PC$ 作為指令記憶體位址。
• 從指令記憶體讀出目前指令。
• 計算下一個順序指令位址：

$$PC+4$$

• 將指令與 $PC+4$ 儲存至 IF/ID 管線暫存器。

---

2. ID：Instruction Decode / Register Fetch

指令解碼與暫存器讀取階段，工作包括：

• 解碼 opcode，判斷指令類型。
• 從暫存器檔案讀取 $rs$ 與 $rt$ 的內容。
• 將 16 位元立即數進行符號延伸：

$$\mathrm{SignExt}(offset)$$

• 產生本指令所需的控制訊號。
• 將讀出的資料、延伸後立即數、目的暫存器編號及控制訊號寫入 ID/EX。

---

3. EX：Execute / Address Calculation

執行或位址計算階段，工作依指令而定：

• R-type 指令：由 ALU 執行算術或邏輯運算。
• lw、sw：計算有效位址。
• Branch：計算分支目標位址並比較暫存器內容。
• 可能使用 forwarding unit 解決資料相依性。

對 lw 而言，ALU 計算：

$$\mathrm{Effective\ Address} =R[rs]+\mathrm{SignExt}(offset)$$

---

4. MEM：Memory Access

記憶體存取階段：

• lw：以 EX 階段算出的有效位址讀取資料記憶體。
• sw：將資料寫入資料記憶體。
• R-type 指令通常不使用資料記憶體。

對 lw 而言：

$$\mathrm{MemoryData} =\mathrm{Memory}[R[rs]+\mathrm{SignExt}(offset)]$$

---

5. WB：Write Back

寫回階段：

• 將 ALU 結果或資料記憶體讀出值寫回暫存器檔案。
• lw 將資料記憶體讀出的值寫入 rt。
• R-type 指令將 ALU 結果寫入 rd。

對 lw 而言：

$$R[rt]\leftarrow \mathrm{MemoryData}$$

---

(b) 五級管線 MIPS 資料路徑

主要資料流

核心觀念

Cache 將主記憶體切成固定大小的區塊（block），每個 Cache 項目存放一個區塊。位址通常分成：

$$\text{Address}=\text{Tag}+\text{Set Index}+\text{Block Offset}$$

其中：

• Tag：辨識目前 Cache 項目所對應的主記憶體區塊。
• Set Index：選擇哪一個 set。
• Block Offset：選擇區塊內的哪一個 byte 或 word。

題目未給定 CPU 位址長度與每個 block 的大小，因此 Tag 與 Offset 的實際位數以符號表示；Cache 的組織方式與 set 數量則可直接確定。

---

(a) 三種 Cache 組織方式

1. Direct-mapped cache（直接對映 Cache）

每一個主記憶體區塊只能放入 Cache 中唯一指定的位置。

若 Cache 有 $N$ 個 blocks，主記憶體區塊編號為 $j$，則：

$$\text{Cache Index}=j\bmod N$$

位址中的 Index 選出一個 Cache line，再利用 Tag 判斷該 line 是否存放所需區塊。

優點是硬體簡單、查找速度快；缺點是兩個經常使用但對映到同一位置的區塊會互相取代，形成較多的 conflict miss。

---

2. Set-associative cache（組相聯 Cache）

Cache 被分成多個 set，每個 set 包含數個 ways。主記憶體區塊先對映到唯一的 set，再放入該 set 中任一個空的 way。

若 Cache 有 $N$ 個 blocks、每個 set 有 $A$ 個 ways，則 set 數為：

$$S=\frac{N}{A}$$

主記憶體區塊 $j$ 所對映的 set 為：

$$\text{Set Index}=j\bmod S$$

查找時，同一個 set 中的 $A$ 個 Tag 會同時比較。

---

3. Fully associative cache（全相聯 Cache）

所有主記憶體區塊都可以放入 Cache 中的任一個 line，因此只有一個 set，不需要 Set Index。

查找時，必須將輸入 Tag 與所有 Cache line 的 Tag 同時比較：

$$\text{Hit}=\bigvee_{i=0}^{N-1} \left(\text{Valid}_i\land(\text{Tag}_i=\text{Input Tag})\right)$$

優點是 conflict miss 最少；缺點是需要大量平行比較器與複雜的替換硬體，成本和耗電較高。

---

(b) 四路組相聯、共 16 個 blocks 的 Cache 架構

四路組相聯表示每個 set 有 4 個 ways，因此 set 數為：

$$S=\frac{16}{4}=4$$

所以此 Cache 的組織為：

$$\boxed{4\text{ sets}\times4\text{ ways}=16\text{ blocks}}$$

若使用 $m$ 位元 byte address，每個 block 大小為 $B$ bytes，則：

• Block Offset：$\log_2 B$ bits
• Set Index：$\log_2 4=2$ bits
• Tag：$m-\log_2B-2$ bits

Cache 儲存陣列

每個 Cache line 至少包含 Valid bit、Tag 與 Data block：

              Way 0              Way 1              Way 2              Way 3
Set 0     [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]
Set 1     [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]
Set 2     [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]
Set 3     [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]  [ V | Tag | Data ]

每個 set 另需保存替換資訊，例如 LRU、FIFO 或 Random 的控制位元。

資料路徑

CPU 位址
   │
   ├────────────── Tag ───────────────┐
   │                                  │
   ├──── Set Index ──> 2-to-4 解碼器   │
   │                         │         │
   └── Block Offset          ▼         │
                         選定一個 Set  │
                              │        │
                 ┌────────────┴────────────┐
                 │ 該 Set 的四個 Ways       │
                 │ V、Tag、Data            │
                 └──────┬──────┬──────┬────┘
                        比較器  比較器  比較器  比較器
                          │       │       │       │
                         Hit0    Hit1    Hit2    Hit3
                           └──────┴──────┴──────┘
                                  │
                         OR 得到總 Hit 訊號
                                  │
                       Data MUX 選出命中 Way
                                  │
                         Block Offset 選字組
                                  │
                              回傳 CPU

四個 Way 的 Tag 比較器必須平行運作，才能在一次 Cache access 中完成查找。

---

(c) Cache 運作流程

以下以讀取資料的流程說明：