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

核心觀念

本題是由 NAND 閘與交互回授構成的暫存器，不能把它當成「時脈為高電位時，輸出直接跟隨 $D$」的電路。判斷各節點時，必須保留回授所儲存的狀態。

NAND 閘的運算為：

$$Y=\overline{X_1X_2\cdots X_n}$$

圖中的 Reset 為低電位有效：正常時為 $1$，重置時拉低為 $0$。

解題方法

依原圖，六個邏輯閘皆為 NAND 閘；左側四個閘具有交互回授，右側兩個閘構成輸出鎖存器。$(1)$ 是 $S$，$(2)$ 是 $R$，$(3)$ 是 $Q'$，$(4)$ 是 Reset，$(5)$ 是左下方 NAND 閘的輸出及其回授線。

令左上方 NAND 閘的輸出為 $A$、$(5)$ 為 $B$，並以 $C$ 表示 Clock、$N$ 表示 Reset。依接線可寫成：

$$\begin{aligned} A&=\overline{BS},\\ S&=\overline{ACN},\\ R&=\overline{SCB},\\ B&=\overline{RDN},\\ Q&=\overline{SQ'},\\ Q'&=\overline{RQN}. \end{aligned}$$

因此，題目要求的順序為：

$$\bigl((1),(2),(3),(4),(5)\bigr)=(S,R,Q',N,B).$$

以下將（a）至（c）的正常起始狀態，取為題目所給的 $D$ 值已經被有效時脈邊緣鎖存。

（a）原先 $D=0$、Clock $=1$，接著 $D=1$、Clock $=0$

原先儲存 $0$，各節點為：

$$(A,S,R,B,Q,Q')=(0,1,0,1,0,1).$$

Clock 降為 $0$ 後，兩個包含 Clock 輸入的 NAND 閘皆輸出 $1$：

$$S=R=1.$$

此時 $D=1$、$N=1$，所以：

$$B=\overline{1\cdot1\cdot1}=0.$$

右側在 $S=R=1$ 時保持原值，故 $Q=0$、$Q'=1$。代回輸出方程式亦成立。

$$\boxed{(1),(2),(3),(4),(5)=(1,1,1,1,0)}$$

（b）原先 $D=1$、Clock $=1$，接著 $D=0$、Clock 仍為 $1$

原先儲存 $1$，各節點為：

$$(A,S,R,B,Q,Q')=(1,0,1,0,1,0).$$

$D$ 改為 $0$ 後，左下方輸出變成：

$$B=\overline{R\cdot0\cdot1}=1.$$

但 $S$ 原先為 $0$，上方回授仍維持：

$$A=\overline{1\cdot0}=1,\qquad S=\overline{1\cdot1\cdot1}=0.$$

接著：

$$R=\overline{0\cdot1\cdot1}=1.$$

因此 $S=0$、$R=1$，右側仍為 $Q=1$、$Q'=0$。Clock 持續為 $1$，沒有新的有效邊緣，因此不會改存 $D=0$。

核心觀念

本題考查：

• 全域 CPI（global CPI）的加權平均
• CPU 所需時脈週期數的計算

全域 CPI 必須依各類指令所占比例加權：

$$\text{Global CPI} = \sum_i \left( \text{第 }i\text{ 類指令比例} \times \text{第 }i\text{ 類 CPI} \right)$$

程式執行所需的總時脈週期數為：

$$\text{Clock Cycles} = \text{Instruction Count} \times \text{Global CPI}$$

題目未要求執行時間，因此時脈頻率不直接影響時脈週期數；時脈頻率只有在計算執行時間時才會使用。

解題方法

（a）各實作的全域 CPI

各類指令比例為：

• Class A：$10\% = 0.1$
• Class B：$20\% = 0.2$
• Class C：$50\% = 0.5$
• Class D：$20\% = 0.2$

實作 P1

P1 的各類 CPI 為 $1,2,3,3$，因此：

$$\begin{aligned} \text{Global CPI}_{P1} &=0.1(1)+0.2(2)+0.5(3)+0.2(3)\\ &=0.1+0.4+1.5+0.6\\ &=2.6 \end{aligned}$$

所以：

$$\boxed{\text{Global CPI}_{P1}=2.6}$$

實作 P2

P2 的四類 CPI 皆為 $2$：

$$\begin{aligned} \text{Global CPI}_{P2} &=0.1(2)+0.2(2)+0.5(2)+0.2(2)\\ &=2(0.1+0.2+0.5+0.2)\\ &=2 \end{aligned}$$

核心觀念

slt $t2, $0, $t1 會在 $t1 > 0 時將 $t2 設為 1，否則設為 0。接著 beq $t2, $0, DONE 在 $t2=0 時跳出迴圈；只有 $t1>0 時，才會執行遞減 $t1 與累加 $s2。

解題方法

每次迴圈先檢查 $t1 是否大於 0。若成立，執行：

• $t1 \leftarrow $t1 - 1
• $s2 \leftarrow $s2 + 2

初始 $t1=10，因此更新與累加各執行 10 次。由 $s2=0$ 開始：

$s2 = 0 + 10 \times 2 = 20

迴圈結束時 $t1=0$，下一次檢查使 $t2=0$，程式跳至 DONE。

等價 C 程式與複雜度

本題考查浮點數的二進位轉換與 IEEE 754 單精度格式表示。

核心觀念：

1. 十進位轉二進位：
   • 整數部分：使用除以 2 取餘數法。
   • 小數部分：使用乘以 2 取整數部分法。
2. IEEE 754 單精度格式：
   • 共 32 位元。
   • 符號位元 (Sign bit, S)：1 位元。0 為正，1 為負。
   • 指數位元 (Exponent bits, E)：8 位元。採用偏移表示法 (biased representation)，偏移值為 127。實際指數 $e = E - 127$。
   • 尾數/分數位元 (Mantissa/Fraction bits, F)：23 位元。表示規格化數字時，隱含一個前導的 '1'。數字形式為 $(-1)^S \times (1.F)_2 \times 2^e$。
3. 浮點數乘法與除法：
   • 乘法:
     • 符號：相乘。
     • 指數：相加 (加上偏移值)。
     • 尾數：相乘。
   • 除法:
     • 符號：相除。
     • 指數：相減 (減去偏移值)。
     • 尾數：相除。
   • 結果正規化：乘法或除法後，結果的尾數可能需要正規化，調整指數。

---

(a) -0.4375 × 0.75

步驟 1：將十進位數轉換為二進位

• -0.4375

  • 符號：負數，S = 1。
  • 0.4375：
    • $0.4375 \times 2 = 0.875$ (整數部分 0)
    • $0.875 \times 2 = 1.75$ (整數部分 1)
    • $0.75 \times 2 = 1.5$ (整數部分 1)
    • $0.5 \times 2 = 1.0$ (整數部分 1)
  • 所以，$0.4375_{10} = 0.0111_2$。
  • 正規化：$0.0111_2 = 1.11_2 \times 2^{-2}$。
  • 指數 $e = -2$。
  • 偏移指數 $E = e + 127 = -2 + 127 = 125$。
  • 二進位表示 $125_{10}$：$125 = 64 + 32 + 16 + 8 + 4 + 1 = 01111101_2$。
  • 尾數 $F$：$1.11_2$ 的小數部分是 $11000000000000000000000_2$ (共 23 位)。
  • 所以，$-0.4375_{10}$ 的 IEEE 754 表示為：1 01111101 11000000000000000000000

• 0.75

  • 符號：正數，S = 0。
  • 0.75：
    • $0.75 \times 2 = 1.5$ (整數部分 1)
    • $0.5 \times 2 = 1.0$ (整數部分 1)
  • 所以，$0.75_{10} = 0.11_2$。
  • 正規化：$0.11_2 = 1.1_2 \times 2^{-1}$。
  • 指數 $e = -1$。
  • 偏移指數 $E = e + 127 = -1 + 127 = 126$。
  • 二進位表示 $126_{10}$：$126 = 64 + 32 + 16 + 8 + 4 + 2 = 01111110_2$。
  • 尾數 $F$：$1.1_2$ 的小數部分是 $10000000000000000000000_2$ (共 23 位)。
  • 所以，$0.75_{10}$ 的 IEEE 754 表示為：0 01111110 10000000000000000000000

步驟 2：計算乘法

• 符號 (S)：負數 $\times$ 正數 = 負數。所以結果的 S = 1。
• 指數 (E)：
  • 結果的實際指數 $e_{res} = e_1 + e_2 = (-2) + (-1) = -3$。
  • 結果的偏移指數 $E_{res} = e_{res} + 127 = -3 + 127 = 124$。
  • 二進位表示 $124_{10}$：$124 = 64 + 32 + 16 + 8 + 4 = 01111100_2$。
• 尾數 (F)：
  • 兩個數的尾數部分是 $1.11_2$ 和 $1.1_2$。
  • 將它們乘以：$1.11_2 \times 1.1_2$。
  • $1.11_2 = 1 + 1/2 + 1/4 = 1.75_{10}$。
  • $1.1_2 = 1 + 1/2 = 1.5_{10}$。
  • $1.75 \times 1.5 = 2.625_{10}$。
  • 將 $2.625_{10}$ 轉換為二進位：
    • $2_{10} = 10_2$。
    • $0.625 \times 2 = 1.25$ (整數部分 1)
    • $0.25 \times 2 = 0.5$ (整數部分 0)
    • $0.5 \times 2 = 1.0$ (整數部分 1)
  • 所以，$2.625_{10} = 10.101_2$。
  • 正規化：$10.101_2 = 1.0101_2 \times 2^1$。
  • 結果的實際指數是 $e_{res} = 1$。
  • 檢查指數計算是否一致：我們之前計算的 $e_{res} = -3$。這裡計算出 $e_{res} = 1$。這是因為尾數相乘後需要正規化，這會改變指數。
  • 正確的指數計算方法：
    • $e_1 = -2$, $e_2 = -1$。
    • 相乘的尾數是 $1.11_2$ 和 $1.1_2$。
    • $(1.11_2 \times 2^{-2}) \times (1.1_2 \times 2^{-1}) = (1.11_2 \times 1.1_2) \times 2^{-2 + (-1)}$
    • $1.11_2 \times 1.1_2 = 10.101_2$。
    • 正規化 $10.101_2 = 1.0101_2 \times 2^1$。
    • 所以，結果是 $(1.0101_2 \times 2^1) \times 2^{-3} = 1.0101_2 \times 2^{-2}$。
    • 實際指數 $e_{res} = -2$。
    • 偏移指數 $E_{res} = e_{res} + 127 = -2 + 127 = 125$。
    • 二進位表示 $125_{10}$：$01111101_2$。
  • 尾數 $F$：$1.0101_2$ 的小數部分是 $01010000000000000000000_2$ (共 23 位)。

步驟 3：組合 IEEE 754 表示

• S = 1
• E = 01111101
• F = 01010000000000000000000

最終結果：1 01111101 01010000000000000000000

核心觀念

五級 MIPS 管線依序為 IF（取指）、ID（解碼與讀暫存器）、EX（運算）、MEM（記憶體存取）、WB（寫回）。

本題須同時處理三件事：

1. 載入後立即使用的資料相依：即使有完整轉送，lw 的資料仍要到 MEM 結束才產生。因此緊接著使用載入結果的 beq，必須停滯一個週期。
2. 預測跳躍與誤預測：分支在 EX 結束時確認結果；若預測錯誤，清除錯誤路徑，下一個週期就取正確路徑的指令。
3. 分支延遲槽：有延遲槽時，分支後面緊接的一條指令，不論分支是否跳躍都必須執行；預測的目標指令在延遲槽之後取指。

解題方法

原卷指定：第一個 beq r2, r0, label2 第一次不跳、第二次跳；第二個 beq r3, r0, label1 跳躍。第二個分支的目標是 label1，其後指令是 and r1, r3, r1。

採用分支目標可立即供取指使用的時序：無延遲槽時，分支取指後下一週期取預測目標；有延遲槽時，先取延遲槽，再取預測目標。假設指令與資料記憶體不發生結構冒險。

以下用代號表示指令：

代號	指令
$A$	lw r2, 0(r1)
$B_1、B_2$	第一次、第二次執行 beq r2, r0, label2
$C_1、C_2$	第一次、第二次執行 lw r3, 0(r2)
$D$	beq r3, r0, label1
$E$	and r1, r3, r1
$S$	正確路徑的 sw r1, 0(r2)
$S_{\mathrm{錯}}$	誤預測路徑的 sw r1, 0(r2)

表中的「停」表示停滯或保持，「×」表示該指令於該週期結束被清除；分支列中的 MEM、WB 僅表示通過管線階段，沒有記憶體存取或暫存器寫回。

(a) 無延遲槽

實際執行的指令順序為：

$$A \rightarrow B_1 \rightarrow C_1 \rightarrow D \rightarrow B_2 \rightarrow S$$

• $A$ 的載入結果於 cycle 4 的 MEM 結束產生，故 $B_1$ 在 cycle 4 停留於 ID，於 cycle 5 的 EX 使用轉送資料。
• $B_1$ 被預測為跳躍，先取到 $S_{\mathrm{錯}}$；cycle 5 確認不跳後，清除錯誤路徑，cycle 6 立即取 $C_1$。
• $C_1$ 與 $D$ 又形成載入後立即使用的相依，因此 $D$ 停滯一個週期，在 cycle 10 的 EX 判定跳躍。
• $D$ 預測正確，已取到目標 $B_2$；$B_2$ 也預測正確，最後執行 $S$。and 不會執行。

指令＼週期	1	2	3	4	5	6	7	8	9	10	11	12	13
$A$	IF	ID	EX	MEM	WB	—	—	—	—	—	—	—	—
$B_1$	—	IF	ID	ID停	EX	MEM	WB	—	—	—	—	—	—
$S_{\mathrm{錯}}$	—	—	IF	IF停	ID×	—	—	—	—	—	—	—	—
$C_1$	—	—	—	—	—	IF	ID	EX	MEM	WB	—	—	—
$D$	—	—	—	—	—	—	IF	ID	ID停	EX	MEM	WB	—
$B_2$	—	—	—	—	—	—	—	IF	IF停	ID	EX	MEM	WB
$S$	—	—	—	—	—	—	—	—	—	IF	ID	EX	MEM

因此，最後的 sw 於 cycle 13 的 MEM 完成寫入。

(b) 使用一個分支延遲槽