108 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《計算機系統（計算機組織）》

核心觀念

本題考查單周期 MIPS 處理器的：

• 關鍵路徑（critical path）
• 各硬體元件的延遲時間
• 同一條指令中，資料必須依序通過的元件延遲總和
• 時脈週期由所有指令類型中最長的路徑決定

計算公式為：

$$\text{Clock cycle time}=\max(\text{各指令類型的路徑延遲})$$ $$\text{Clock frequency}=\frac{1}{\text{Clock cycle time}}$$

題目附件目前顯示的是工程數學考卷，未包含本題所需的 MIPS datapath 圖。以下依照標準單周期 MIPS datapath，假設資料路徑包含：

• PC 暫存器
• Instruction Memory
• Register File
• ALUSrc 2:1 MUX
• ALU
• Data Memory
• MemtoReg 2:1 MUX
• Register File 寫入

解題方法

所有指令都必須先經過：

$$\text{PC Register read} \rightarrow \text{Instruction Memory} \rightarrow \text{Register File read}$$

之後依照指令類型分流。

控制訊號由 Control Unit 與 ALU Control Unit 平行產生；若其延遲沒有比資料本身抵達更晚，就不列入主要資料關鍵路徑。

(a) 各類指令的關鍵路徑

1. R-format

R-format 使用兩個暫存器運算，ALU 的結果再寫回 Register File。

關鍵路徑為：

$$\text{PC Register read} \rightarrow \text{Instruction Memory} \rightarrow \text{Register File read} \rightarrow \text{2:1 MUX} \rightarrow \text{ALU} \rightarrow \text{2:1 MUX} \rightarrow \text{Register File write}$$

延遲為：

$$1+15+7+2+10+2+5=42\text{ ns}$$

其中第一個 MUX 是 ALUSrc MUX，第二個 MUX 是 MemtoReg MUX。

2. Load-word

Load-word 先利用 ALU 計算記憶體位址，再從 Data Memory 讀取資料，最後寫回暫存器。

關鍵路徑為：

$$\text{PC Register read} \rightarrow \text{Instruction Memory} \rightarrow \text{Register File read} \rightarrow \text{2:1 MUX} \rightarrow \text{ALU} \rightarrow \text{Data Memory read} \rightarrow \text{2:1 MUX} \rightarrow \text{Register File write}$$

延遲為：

$$1+15+7+2+10+15+2+5=57\text{ ns}$$

3. Store-word

Store-word 使用 ALU 計算記憶體位址，並將 Register File 讀出的資料寫入 Data Memory。

關鍵路徑為：

核心觀念

本題考查計算機系統結構中「CPU 效能方程式（CPU Performance Equation）」與「加權平均每指令週期數（Cycles Per Instruction, CPI）」的核心計算。

關鍵公式如下：

1. CPU 執行時間（CPU Execution Time）：
   $\text{CPU Execution Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time } (T_c) = \frac{\text{Total Clock Cycles}}{\text{Clock Rate } (f)}$
2. 加權平均 CPI：
   $\text{CPI} = \frac{\sum (\text{Instruction Count}_i \times \text{CPI}_i)}{\text{Total Instruction Count}} = \frac{\text{Total Clock Cycles}}{\text{Total Instruction Count (IC)}}$
3. 加速比（Speedup）：
   $\text{Speedup} = \frac{\text{Execution Time}_{\text{old}}}{\text{Execution Time}_{\text{new}}} = \frac{\text{Total Clock Cycles}_{\text{old}}}{\text{Total Clock Cycles}_{\text{new}}} \quad (\text{在處理器頻率 } f \text{ 不變的前提下})$

---

解題方法

(a) 原始程式之執行時間與 CPI 計算

• 步驟一：計算原始總時脈週期數（Total Clock Cycles）
  根據題目表格與各指令的 CPI 權重：

  • Arithmetic：$500 \times 4 = 2000 \text{ cycles}$
  • Store：$50 \times 4 = 200 \text{ cycles}$
  • Load：$100 \times 5 = 500 \text{ cycles}$
  • Branch：$50 \times 3 = 150 \text{ cycles}$

  $\text{Total Clock Cycles}_{\text{orig}} = 2000 + 200 + 500 + 150 = 2850 \text{ cycles}$

• 步驟二：計算平均 CPI
  原始總指令數 $\text{IC}_{\text{orig}} = 700$：
  $\text{CPI}_{\text{orig}} = \frac{\text{Total Clock Cycles}_{\text{orig}}}{\text{IC}_{\text{orig}}} = \frac{2850}{700} = \frac{57}{14} \approx 4.0714$

• 步驟三：計算 CPU 執行時間
  處理器時脈頻率 $f = 2 \text{ GHz} = 2 \times 10^9 \text{ Hz}$：
  $\text{Execution Time}_{\text{orig}} = \frac{2850 \text{ cycles}}{2 \times 10^9 \text{ Hz}} = 1.425 \times 10^{-6} \text{ s} = 1.425 \ \mu\text{s}$

---

(b) Load 指令減半後之加速比與 CPI 計算

(a) 24A60004₁₆ → 十進位

IEEE‑754 單精度 (32 bit) 之欄位：

• 符號位 $s = 0$（正）
• 指數位 $e =$ 0x49 = $73_{10}$
  實際指數 $E = e-127 = -54$
• 尾數位 $f =$ 0x00260004

$\frac{f}{2^{23}} = \frac{2\,490\,372}{8\,388\,608}\approx 0.297058105$

• 正規化尾數 $M = 1+ \frac{f}{2^{23}} = \frac{10\,878\,980}{8\,388\,608}\approx 1.297058105$

$$\text{值}=(-1)^s \times M \times 2^{E} = 1.297058105 \times 2^{-54} = \frac{10\,878\,980}{2^{77}} \approx 7.20\times10^{-17}$$

【答案】$7.20\times10^{-17}$（約值）

---

(b) $-1609.5$ 的 IEEE‑754 雙精度 (64 bit) 二進位表示

(a) Block size (words)

• Case I：位元組位元 $[3\!-\!0]$ → $2^{4}=16$ B $=4$ words
• Case II：位元組位元 $[4\!-\!0]$ → $2^{5}=32$ B $=8$ words

(b) 總位元/資料位元比例

	Index bits	行數 $=2^{\text{index}}$	區塊大小 (bit)	資料位元 $= \text{行數}\times\text{區塊大小}$	標籤位元/行	標籤總位元	有效位元總數	總位元	比例
Case I	$[9\!-\!4]=6$	$64$	$16\text{ B}=128$	$64\times128=8192$	$[31\!-\!10]=22$	$64\times22=1408$	$64$	$8192+1408+64=9664$	$\displaystyle\frac{9664}{8192}= \frac{151}{128}\approx1.18$

核心觀念

這題考兩件事：把尾端遞迴改寫成迴圈，以及依 MIPS 指令格式填入暫存器、分支位移與跳躍目標。

函式呼叫 prod(n-2, n*acc) 是尾端呼叫：每次呼叫的結果直接作為目前函式的結果，不需要保留返回後要做的運算。因此，可直接在暫存器中更新參數並跳回 Prod。

解題方法

條件 n > 0 成立時，依序更新：

• 累積值：acc = n * acc
• n：n = n - 2
• 回到 Prod 繼續判斷

slti $t0, $a0, 1 在 $a0 < 1 時令 $t0=1；此時 n 不大於 0，分支至 Exit。所以分支條件與原程式的 if (n > 0) 相符。

依題目提供的三運算元乘法格式，完整程式為：

Prod: slti $t0, $a0, 1
      bne  $t0, $zero, Exit
      mult $a1, $a0, $a1
      addi $a0, $a0, -2
      j    Prod
Exit: add  $v0, $a1, $zero
      jr   $ra

其中 mult 的目的暫存器是 $a1，來源是 $a0 與 $a1，因此乘積更新累積值。

（a）填空答案

空格	答案
(I)	1
(II)	$a1
(III)	$a1
(IV)	$a0
(V)	$v0
(VI)	$a1
(VII)	$ra

機器碼欄位計算

（VIII）：分支位移

bne 位於位址 48004，Exit 位於 48020。分支位移以 PC+4 為基準，並以指令字為單位：

$$\frac{48020-(48004+4)}{4}=3$$

所以 (VIII) = 3。

（IX）：addi 的立即數

核心觀念

本題考查五級管線中的資料危障、插入 nop 的方法，以及管線執行時間。

指令依序經過 IF、ID、EX、MEM、WB 五個階段。沒有資料轉送時，消費者必須等到生產者將結果寫回暫存器後，才能在 ID 階段讀取該值。本題採用標準 MIPS 暫存器檔假設：同一個時脈週期內，WB 先寫入、ID 後讀取，因此消費者可在生產者 WB 的同一週期讀取結果。

若生產者與消費者相鄰，兩者之間要插入兩個 nop，讓消費者的 ID 階段延後至生產者的 WB 週期。更一般地，若兩指令之間原有 $k$ 條指令，至少需要：

$$\max(0,\ 2-k)$$

個 nop。

管線時脈週期由最慢的階段決定：

$$T_{\text{clk}}=\max(T_{\text{IF}},T_{\text{ID}},T_{\text{EX}},T_{\text{MEM}},T_{\text{WB}})$$

一段指令序列有 $N$ 條指令（包含插入的 nop），在五級管線中完成並排空管線需要 $N+4$ 個週期。

(a) 傳統管線：插入 nop

只考慮迴圈內第 2 至第 8 行。主要相依關係如下：

• sll 產生 $t2，第 3 行的 add 使用它：兩指令相鄰，插入兩個 nop。
• 第 3 行的 add 產生 $t3，第 5 行的 lw 使用它；中間已有一條第 4 行指令，因此再插入一個 nop。
• 第 6 行的 lw 產生 $t5，第 7 行的 mult 使用 $t5，插入兩個 nop。
• 第 7 行的 mult 產生 $t5，第 8 行的 add 使用它，插入兩個 nop。

改寫如下：

LOOP:
    sll   $t2, $t1, 2
    nop
    nop
    add   $t3, $s0, $t2
    add   $t2, $s1, $t2
    nop
    lw    $t4, 0($t3)
    lw    $t5, 0($t2)
    nop
    nop
    mult  $t5, $t4, $t5
    nop
    nop
    add   $s3, $t5, $s3

原本 7 條指令共插入 7 個 nop，因此序列總長度為 14 條指令。

(b) 傳統管線：完成時間

傳統管線的時脈週期為：

$$T_{\text{clk}}=\max(120,100,170,200,120)=200\text{ ps}$$

時脈頻率為：

$$f_{\max}=\frac{1}{200\text{ ps}}=5\text{ GHz}$$

14 條指令完成並排空五級管線，需要 $14+4=18

核心觀念

本題旨在考驗計算機系統結構中多處理器系統效能優化與**阿姆達爾定律（Amdahl's Law）**的應用。

1. 阿姆達爾定律（Amdahl's Law）：
   用於計算系統某一部份經平行化或優化後，整體系統所能獲得的加速比（Speedup）與優化後執行時間（Execution Time）。公式定義如下：
   $T_N = T_1 \times \left( (1 - f) + \frac{f}{N} \right)$
   $\text{Speedup} (S_N) = \frac{T_1}{T_N} = \frac{1}{(1 - f) + \frac{f}{N}}$
   其中：

   • $T_1$：單一處理器（Single Processor）執行時間。
   • $T_N$：使用 $N$ 個處理器時的平行執行時間。
   • $f$：程式中可被平行處理（Parallelizable）部分的比例。
   • $(1 - f)$：必須串行執行（Sequential）無法平行化部分的比例。
   • $N$：採用的處理器數量。

2. 理論加速極限（Speedup Bound）：
   當處理器數量增加至無限多個（$N \to \infty$）時，最大平行加速比受限於串行執行的比例：
   $S_{\max} = \lim_{N \to \infty} \frac{1}{(1 - f) + \frac{f}{N}} = \frac{1}{1 - f}$

---

解題方法

(a) 子題 (a) 求解推導

1. 給定條件：

   • 向量尺寸：$100 \times 1$。
   • 單處理器執行時間 $T_1 = t$。
   • 可平行化算術指令比例 $f = 90\% = 0.9$，串行比例 $(1 - f) = 10\% = 0.1$。
   • 處理器數量 $N = 10$。

2. 計算 10 個處理器之執行時間 $T_{10}$：
   $T_{10} = t \times \left( (1 - 0.9) + \frac{0.9}{10} \right) = t \times (0.1 + 0.09) = 0.19t$

3. 計算加速比 $S_{10}$：
   $S_{10} = \frac{T_1}{T_{10}} = \frac{t}{0.19t} = \frac{1}{0.19} = \frac{100}{19} \approx 5.2632$

---

(b) 子題 (b) 求解推導

1. 給定條件：

   • 向量尺寸擴展至 $400 \times 1$。
   • 單處理器執行時間 $T_1' = 3.8t$。
   • 延續 (a) 之系統特性，平行化比例 $f = 0.9$，串行比例 $(1 - f) = 0.1$。
   • 目標加速比：$\text{Speedup} > 8$。

2. 求解最少處理器數量 $N$：
   根據阿姆達爾定律加速比公式設定不等式：
   $\text{Speedup} = \frac{1}{(1 - f) + \frac{f}{N}} = \frac{1}{0.1 + \frac{0.9}{N}} > 8$
   求解此不等式：