108 年 國立中正大學電機工程學系碩士班計算機工程組《計算機組織》

核心觀念

• Data hazard（資料危險）：在流水線（pipeline）執行時，前一指令的執行結果尚未寫回或尚未可供後續指令使用，導致後續指令因讀取到錯誤或未更新的資料而產生衝突。常見類型包括

  • RAW (Read‑After‑Write)：後指令讀取前指令尚未完成寫入的目標暫存器。
  • WAR (Write‑After‑Read)：後指令寫入的暫存器在前指令尚未完成讀取前就被改寫。
  • WAW (Write‑After‑Write)：兩指令寫入同一暫存器，後指令需在前指令寫入完成後才能正確執行。

• Control hazard（控制危險）：分支指令（branch）或跳轉指令的目標位址在取指階段尚未確定，使得流水線無法確定下一個要取的指令是哪一條。若分支預測錯誤，已取的指令必須被撤銷（flush），造成效能損失。

解題方法

1. 先說明 資料危險 與 控制危險 的產生時機與根本原因：
   • 資料危險源於 指令間的資料相依（data dependency）。
   • 控制危險源於 指令流的控制相依（control dependency），即分支的結果決定下一條指令。
2. 以流水線的五階段（IF, ID, EX, MEM, WB）為例，描述兩種危險在各階段的影響：
   • RAW：在 WB 階段才寫回寄存器，若後續指令在 EX 階段需要該寄存器，就會發生 RAW。
   • 分支指令：在 ID 階段才判斷分支條件，若在 IF 階段已經取了錯誤路徑的指令，則產生 control hazard。
3. 介紹常見的 解決手法：
   • 資料危險：前饋（forwarding / bypass）、插入 NOP（stall）、使用讀後寫（read‑after‑write）排程、重新排列指令。
   • 控制危險：分支預測（static / dynamic）、預取（branch delay slot）、流水線清除（flush）及重新取指。

選項分析（若本題為簡答題，以下列點說明正確與錯誤的常見敘述）

• A. Data hazard 與 control hazard 都是因為指令間的相依關係

核心觀念

• 分支預測 (Branch Prediction)：在指令流水線中，當執行到分支指令（如 beq, bne）時，CPU 必須先決定分支是否成立才能決定下一條要取的指令。分支預測是透過硬體或軟體機制，在分支條件尚未計算完成前，提前猜測分支方向（taken / not‑taken），以免流水線因等待分支結果而停頓。常見的預測方法有靜態預測（固定假設 always‑taken、always‑not‑taken、根據分支偏移方向等）以及動態預測（2‑bit saturating counter、全局/本地歷史表、TAGE 等）。

• 分支延遲槽 (Branch Delay Slot)：在某些 RISC 架構（如 MIPS）中，分支指令的執行會產生一個或多個「延遲槽」——即分支指令之後的若干條指令在分支決定之前仍會被執行。這是因為在取指階段就已經把分支目標預取到 PC，導致 PC 仍然向前走了幾個時鐘週期。若能在延遲槽內放置不受分支影響的指令，就能避免流水線空轉。

解題方法

1. 定義差異：先說明兩者在 「何時」 介入與 「目的」 為何不同。

   • 分支預測：在 分支條件尚未求值 前，猜測分支方向，以保持流水線連續。
   • 分支延遲槽：在 分支指令已取回 後，固定執行 若干條指令，不論分支結果如何。

2. 實作層面：比較硬體需求與編譯器支援。

   • 預測需要 分支預測單元、歷史表、回饋回路，屬於 硬體複雜度 的提升。
   • 延遲槽則是 指令編排 的問題，主要由 編譯器 或 手寫彙編 把有意義的指令填入，硬體本身只要支援「延遲執行」即可。

3. 效能影響：

   • 正確預測可讓流水線 無中斷，錯誤預測則必須 清除/重填，代價高達 10–20 個週期（視流水線深度而定）。
   • 延遲槽若填滿有用指令，可減少 1–2 個週期 的空轉；若填不了，就只能執行 NOP，等於浪費了槽位。

核心觀念

• CPU 時間 (CPU time)：指程式在 CPU 上執行所消耗的實際時間。常以秒 (s) 為單位，衡量的是「使用者」感受到的執行時間。
• CPU 時脈週期 (CPU clock cycle)：CPU 時脈的基本單位，一個週期代表時脈訊號從一個上升沿到下一個上升沿的時間間隔。常以「週期」或「ticks」表示，與實際時間的關係由 時脈頻率 (Clock Frequency) 決定。
• 時脈頻率 (f)：每秒鐘的週期數，單位 Hz (cycles/s)。常用 MHz、GHz 表示。
• 指令週期 (CPI, Cycles Per Instruction)：平均每條指令需要的時脈週期數。
• 指令數 (IC, Instruction Count)：程式要執行的指令總數。

關鍵公式

其中

• CPU cycles = $\text{IC} \times \text{CPI}$
• clock frequency $f$ 為每秒的週期數 (例如 $2\,\text{GHz}=2\times10^{9}$ cycles/s)。

解題方法

1. 分辨概念

   • CPU 時間 為「時間」層面的度量；
   • CPU 時脈週期 為「週期」層面的度量。

2. 使用公式

   • 若已知指令數與 CPI，可先求出總 CPU cycles；再以頻率換算成時間。
   • 反之，若已知 CPU 時間與頻率，可逆算出 CPU cycles。

3. 舉例說明（非題目必需，但有助於加深理解）

   假設一段程式執行 10⁶ 条指令，平均 CPI = 2，CPU 時脈頻率 = 2 GHz

$\text{CPU cycles}=10^{6}\times2=2\times10^{6}\ \text{cycles}$

核心觀念

本題的核心在於釐清快取記憶體（Cache Memory）在「功能劃分／內容分離（Functionality / Content Partitioning）」與「組織架構／映射方式（Internal Organization / Placement Policy）」兩個不同正交（orthogonal）維度上的設計概念：

1. Split Cache（分離式快取）：

   • 依存放內容分類：將快取依據處理器存取的資訊型態，硬體上實體分離為專門存放指令的 I-Cache（Instruction Cache） 與專門存放資料的 D-Cache（Data Cache）。
   • 主要目的：解決管線化處理器（Pipelined Processor）中，IF（Instruction Fetch）階段與 MEM（Memory Access）階段同時存取記憶體所引發的結構相依／結構衝突（Structural Hazard），同時使快取可針對指令與資料各自特有的存取局部性（Locality）分別最佳化。
   • 其相對概念為 Unified Cache（統一快取），即指令與資料共用同一個快取。

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

   • 依區塊映射規則分類：快取被劃分為若干個「組（Set）」，每個組內包含 $n$ 個「行／區塊（Cache Lines/Blocks）」，稱為 $n$-way Set-Associative。
   • 映射規則：主記憶體區塊位址對應到固定的 Set：
     $\text{Set Index} = (\text{Block Address}) \pmod{\text{Number of Sets}}$
     但進入特定 Set 內部後，可放置於該 Set 中的任一個空閒或被置換的 Line 之中（關聯度搜尋）。
   • 主要目的：在 Direct-Mapped Cache（直接映射快取）（碰撞失效率高、命中時間短）與 Fully-Associative Cache（全相聯快取）（無衝突失效、硬體代價與命中時間高）之間取得平衡，透過增加關聯度（Associativity）來降低衝突失效（Conflict Miss）。

解題方法

回答本題的破題關鍵在於指出：兩者屬於不同層次（維度）的快取分類標準，不可混為一談；在現代處理器設計中，兩者常同時並存（例如 L1 快取常採用「Split」架構，而其中的 I-Cache 與 D-Cache 各自內部均採用「$n$-way Set-Associative」組織）。

回答應從「定義與設計出發點」、「所處維度與對照組」、「解決的問題」以及「彼此之交互關係」四個維度進行對比剖析：

核心觀念

正緣觸發輸入會在時脈上升緣取樣。被取樣的資料與控制訊號，必須在上升緣前後維持穩定：

• 建立時間 $t_{\text{setup}}$：訊號須在上升緣前穩定至少一段時間。
• 保持時間 $t_{\text{hold}}$：訊號須在上升緣後繼續穩定至少一段時間。

解題方法

對照圖中的時序可見，Data 與 Control 都在時脈正緣附近改變：它們在正緣時才升高，並在正緣後不久又下降。因此，這兩個訊號都沒有滿足取樣所需的穩定時間。

兩個主要問題

核心觀念

正緣觸發的介面會在時脈由低轉高的瞬間取樣輸入。取樣前，資料與控制訊號必須先穩定一段時間，稱為建立時間；取樣後也必須維持穩定一段時間，稱為保持時間。

若資料或控制訊號恰好在正緣改變，接收端可能無法正確判讀該次取樣。因此，兩者都必須在每個正緣附近維持不變：

解題方法

原圖中，Data 與 Control 在時脈正緣附近改變，無法保證建立時間與保持時間。可將輸入訊號的轉換安排在時脈負緣，讓 Data 與 Control 在下一個正緣到來前先穩定，並在正緣後繼續維持。

以下保留原圖在各正緣預期取樣的高、低值；Data 與 Control 的波形相同：

核心觀念

管線暫存器（IF/ID、ID/EX、EX/MEM、MEM/WB）位於各管線階段之間，用來在時脈邊緣保存某一指令的中間資料與控制訊號。這讓多條指令能同時處於不同階段執行，而每個階段都能取得屬於該指令的正確資訊。

資料訊號包含後續階段需要的指令欄位、暫存器讀值、立即值、ALU 結果或記憶體資料。控制訊號則指定後續操作，例如 ALU 運算、資料記憶體讀寫，以及暫存器寫回方式。

解題方法

沿著圖中的管線追蹤一條指令：控制單元在解碼階段產生控制訊號，並將它與指令所需資料一同存入 ID/EX；之後，資料和控制訊號隨指令傳到 EX/MEM、MEM/WB，供各階段完成運算、記憶體存取及結果寫回。

核心觀念

本題考的是五級管線中的資料相依與資料前推。當目前在 EX 階段的指令需要某個暫存器值，而較早的指令尚未把結果寫回暫存器檔時，前推單元可直接從管線暫存器取得新值，送到 ALU 輸入端。

解題方法

若目前 EX 階段指令的來源暫存器，與 MEM/WB 階段指令的目的暫存器相同，而且該 MEM/WB 指令會寫回暫存器，就會觸發從 MEM/WB 前推：

並且目的暫存器符合目前指令的來源暫存器：

或

核心觀念

分支成立會造成控制危障：處理器在確認分支結果前，可能已依序取入下一條指令；但分支成立後，這條順序路徑上的指令不應執行。因此要清除錯誤路徑指令，並讓 PC 改指向分支目標位址。

解題方法

原圖是含 IF、ID、EX、MEM、WB 階段的管線資料路徑，標示了 PC、IF/ID 暫存器，以及 PCWrite 和 IF/IDWrite。其中 IF/IDWrite 是寫入致能訊號；原圖沒有標出獨立的 IF/ID 清除訊號，而禁止寫入只會保留暫存器中的內容，不能代替清除。

分支成立時，控制流程如下：

1. 順序取指可能已將下一條指令放入 IF/ID；分支成立後，這條指令屬於錯誤路徑。

核心觀念

• Amdahl 定律：在提升程式中某一部分的效能時，整體加速比受該部分執行時間比例所限制。
  $S_{\text{overall}}=\frac{1}{(1-f)+\frac{f}{k}}$
  其中 $f$ 為欲加速部份佔原始執行時間的比例，$k$ 為該部份的加速倍數，$S_{\text{overall}}$ 為整體加速倍數。

解題方法

1. 計算「multiply」在原始程式中佔的比例
   $f=\frac{90\text{ sec}}{100\text{ sec}}=0.9$
2. 設欲得到的整體加速倍數為 4 倍，即 $S_{\text{overall}}=4$。代入 Amdahl 定律，解 $k$：
   $4=\frac{1}{(1-0.9)+\frac{0.9}{k}}$
   $\Rightarrow (0.1)+\frac{0.9}{k}= \frac{1}{4}=0.25$
   $\Rightarrow \frac{0.9}{k}=0.25-0.1=0.15$

核心觀念

這題考的是移位加法乘法器：把乘數與部分乘積放在同一個 64 位元暫存器中，逐位檢查乘數的最低位元，必要時將被乘數加到部分乘積，再將整個暫存器右移。

解題方法

設 64 位元暫存器為 $P$，32 位元暫存器為 $M$：

1. 將 32 位元被乘數存入 $M$。
2. 初始化 $P$：高 32 位元設為 $0$，低 32 位元放入 32 位元乘數。因此，$P$ 同時保存部分乘積與尚待處理的乘數。
3. 重複 32 次：
   • 檢查 $P$ 的最低位元 $P_0$。
   • 若 $P_0=1$，將 $M$ 加到 $P$ 的高 32 位元。
   • 將整個 $P$ 向右移一位。
4. 32 次迴圈結束後，$P$ 的 64 位元內容就是乘積。

核心觀念

這題考「移位加法乘法器」的控制流程。64 位元暫存器同時存放部分乘積與乘數：高 32 位元存部分乘積，低 32 位元存尚未處理的乘數。控制單元每回合檢查低位元 $Q_0$；若 $Q_0=1$，就把被乘數加到高 32 位元，再將整個 64 位元暫存器右移一位。重複 32 回合後，暫存器內即為 64 位元乘積。

解題方法

先把 64 位元暫存器記作 $[A,Q]$，其中 $A$ 是高 32 位元、$Q$ 是低 32 位元；另以 32 位元暫存器保存被乘數 $M$。初始化為 $A=0$、$Q=\text{乘數}$，並令回合計數器 $C=32$。

每回合依序執行：

1. 檢查 $Q_0$。若 $Q_0=1$，令 $A\leftarrow A+M$；若 $Q_0=0$，不做加法。
2. 將串接的 $[A,Q]$ 邏輯右移一位。右移時保留加法結果的進位，使其進入高位端。
3. 令 $C\leftarrow C-1$。若 $C\ne 0$，開始下一回合；若 $C=0$，結束，乘積位於 $[A,Q]$。

控制流程圖

核心觀念

• 暫時性局部性 (Temporal Locality)：指同一記憶體位置在短時間內被多次存取。
• 空間局部性 (Spatial Locality)：指相鄰記憶體位置在短時間內被存取。
• 記憶體排佈：題目說「同一列的元素連續存放」，在 C 語言的 列優先 (row‑major) 佈局下，A[i][j] 的 第 i 列 內的所有 j 位置是連續的，而 A[i][j] 與 A[i][j+1] 之間的位址相差一個元素大小。

解題方法

1. 先寫出程式的四個記憶體存取：
   • A[i][j] (寫)
   • B[j][0] (讀)
   • A[j][i] (讀)
2. 觀察迴圈結構：外層 j 固定後，內層 i 從 0 走到 7999。
3. 依照 同一變數在同一次外層迭代內是否被重複使用 來判斷暫時性局部性。

變數的暫時性局部性分析

核心觀念
本題測試MIPS 指令與 C 語言對應的能力，包含：

1. 記憶體位址運算：使用 addi、add 計算陣列元素的位址。
2. 資料存取指令：sw（store word）寫入記憶體，lw（load word）讀取記憶體。
3. 暫存器與變數的映射：題目已把變數 $f、$g、$h、$i、$j 分別對應到$s0‑$s4，陣列 A、B 的基址對應到$s6、$s7。
4. 指令序列的資料流：必須追蹤每個暫存器的值如何變化，最後得到 $s0（即變數 f）的值。

解題方法
依序解讀每條指令，寫出對應的 C 程式碼（或等價的運算式），同時說明每一步對暫存器與記憶體的影響。

把上述步驟整理成完整的 C 程式片段：

核心觀念

本題測驗 IEEE 754 單精度浮點數格式（Single-Precision Floating-Point Format） 的標準轉換。

IEEE 754 單精度浮點數共佔 32 個位元（bits），其格式劃分如下：

1. 符號位元（Sign bit, $S$）：佔 1 bit。
   • 正數為 $0$；負數為 $1$。
2. 指數欄位（Exponent, $E$）：佔 8 bits。
   • 採用偏差標記法（Biased Representation / Excess-127）。
   • 若實際真實指數為 $e$，則欄位儲存值為 $E = e + \text{Bias} = e + 127$。
3. 小數部分／尾數欄位（Fraction / Mantissa, $F$）：佔 23 bits。
   • 採用正規化表示式（Normalized form）：$(-1)^S \times (1.F)_2 \times 2^e$。
   • 最高位的整數部分「$1$」為隱含位元（Hidden bit），不佔用欄位空間，欄位僅儲存小數點後面的 23 個位元。

解題方法

將十進位小數 $(2.25)_{10}$ 轉換為 IEEE 754 單精度格式，依序經過以下步驟：

步驟一：將十進位數轉換為二進位表示式

• 整數部分：$(2)_{10} = (10)_2$
• 小數部分：$(0.25)_{10} = \frac{1}{4} = 2^{-2} = (0.01)_2$
• 合併：
  $(2.25)_{10} = (10.01)_2$

步驟二：正規化為科學記號（Normalized Scientific Notation）

將二進位小數點向左平移 1 位，使其符合 $1.F \times 2^e$ 的格式：
$(10.01)_2 = 1.001_2 \times 2^1$

由此可得：

• 符號為正數，故真實指數 $e = 1$。
• 小數部分 $F = 001_2$。

步驟三：決定三個欄位的位元值

1. 符號位元（$S$）：
   • 數值為正數，故：
     $S = 0$
2. 指數欄位（$E$）：
   • 真實指數 $e = 1$，加上 Bias（127）：
     $E = 1 + 127 = 128_{10}$
   • 將 128 轉成 8 位元二進位：
     $E = (10000000)_2$
3. 尾數欄位（$F$）：
   • 取正規化小數點後的位元，不足 23 位元者在右側補 0：
     $F = 00100000000000000000000_2 \quad (\text{共 23 bits})$