109 年 國立中正大學電機工程學系碩士班信號與媒體通訊組《計算機組織》

核心觀念

本題比較四組計算機組織的重要名詞：

• $Pipelining$：利用不同階段的時間重疊提高吞吐量。
• $Parallelism$：利用多個硬體資源同時處理多個工作。
• $Latch$ 與 $Flip-flop$：兩種儲存一位元狀態的循序邏輯元件。
• $Wafer$ 與 $Die$：半導體製造中，整片晶圓與單一晶片單元的關係。
• $CPI$ 與 $CPU\ time$：處理器效能分析中的每指令週期數與實際執行時間。

---

(a) Pipelining 與 Parallel Processing

核心定義

**Pipelining（管線化）**是將一項工作分成多個階段，讓不同工作同時處於不同階段，以重疊時間。

以五階段處理器為例：

$$IF \rightarrow ID \rightarrow EX \rightarrow MEM \rightarrow WB$$

當第 $1$ 條指令進入 $ID$ 階段時，第 $2$ 條指令可同時進入 $IF$ 階段。管線化並非讓同一條指令同時使用多個階段，而是讓多條指令分別佔據不同階段。

**Parallel Processing（平行處理）**是使用多個處理單元、核心、ALU 或運算通道，在同一時間處理多個獨立工作。

主要差異

比較項目	Pipelining	Parallel Processing
主要概念	不同階段在時間上重疊	多個硬體資源同時運算
資源使用	將一組硬體分成多個階段	複製或增加運算資源
主要改善	提高吞吐量	縮短平行工作所需時間、提高吞吐量
單一工作延遲	通常不會明顯降低	可因多個單元共同處理而降低
典型例子	指令管線	多核心、SIMD、多工單元

假設一項工作分成 $k$ 個階段，每階段耗時 $t$，連續處理 $n$ 項工作：

未使用管線時，總時間約為

$$T_{\text{non-pipeline}}=nkt$$

使用理想管線時，第一項工作需經過 $k$ 個週期，之後每個週期完成一項，因此

$$T_{\text{pipeline}}=(k+n-1)t$$

理想加速比為

$$S=\frac{nkt}{(k+n-1)t} =\frac{nk}{k+n-1}$$

當 $n$ 很大時，最大加速比接近 $k$。這表示管線化主要改善的是整體吞吐量，不是單一指令的基本工作量。

平行處理則是增加多個處理資源。若有 $p$ 個完全獨立且負載平均的處理單元，理想執行時間可近似為

$$T_p=\frac{T_1}{p}$$

實際加速比會受到同步、通訊、負載不均及無法平行化部分的限制。

解題技巧

判斷兩者的關鍵是：

• 管線化：同一組硬體的不同階段重疊，屬於時間上的平行。
• 平行處理：多組硬體同時運作，屬於空間上的平行。

兩者可以同時存在，例如多核心處理器中的每一個核心都採用指令管線，而處理器本身又透過多核心進行平行處理。

---

(b) Latches 與 Flip-flops

核心定義

Latch（鎖存器）是電位敏感的儲存元件。在控制訊號處於有效電位期間，輸出可隨輸入變化；控制訊號失效後，鎖存最後的值。

以 $D$ latch 為例：

$$EN=1 \Rightarrow Q=D$$ $$EN=0 \Rightarrow Q\text{ 保持原值}$$

Flip-flop（正反器）是邊緣觸發的儲存元件，只在時脈的上升邊緣或下降邊緣取樣輸入，其他時間維持輸出不變。

以正緣觸發的 $D$ flip-flop 為例：

$$Q(t^+)=D(t_{\text{rising edge}})$$

主要差異

比較項目	Latch	Flip-flop
觸發方式	Level-sensitive，電位敏感	Edge-triggered，邊緣觸發
取樣時間	有效電位的整段期間	上升邊緣或下降邊緣瞬間
輸入變化	開啟期間可傳到輸出	通常只在觸發邊緣取樣
時序控制	可進行 time borrowing	時序界線較明確
常見用途	低階儲存、時序電路	暫存器、同步式循序電路

常見的 edge-triggered flip-flop 可由兩個相反相位工作的 latch 組成，稱為 master-slave 結構。前級 latch 在一個時脈相位取樣，後級 latch 在另一個相位更新，因此對外表現為只在時脈邊緣改變輸出。

時序要求

兩者都必須符合 setup time 與 hold time：

• Setup time：觸發前，輸入需維持穩定的最短時間。
• Hold time：觸發後，輸入仍需維持穩定的最短時間。

Latch 因為在一段電位期間內開啟，具有較大的時序彈性，可讓資料在某些情況下跨越部分階段傳遞，稱為 time borrowing。Flip-flop 的取樣邊緣明確，設計與分析較容易，但每個階段通常必須在固定時脈週期內完成。

解題技巧

快速判斷方式如下：

• 題目出現「enable 有效期間內輸出跟隨輸入」：答案是 latch。
• 題目出現「只在 clock edge 取樣」：答案是 flip-flop。
• 兩者都能儲存狀態，也都屬於循序邏輯；差異不在於是否具有記憶能力，而在於取樣控制方式。

---

(c) Wafers 與 Dies

核心定義

**Wafer（晶圓）**是由矽晶棒切割、研磨而成的大型圓形半導體基板。晶圓表面會經過微影、蝕刻、離子佈植、金屬連線等製程，形成大量重複排列的積體電路圖樣。

**Die（裸晶片單元）**是晶圓上其中一個獨立的積體電路區域。完成晶圓製程後，會沿著切割道將晶圓切割成許多矩形 die。

製造流程可表示為：

核心觀念

這題考 JK 正反器構成的同步二進位計數器。JK 正反器在 $J=K=1$ 時，會在時脈有效邊緣翻轉；$J=K=0$ 時維持原狀。圖中的正反器共用時脈，因此是同步計數器。

圖中標記 (1) 是第一個 AND 閘的輸出，亦即 $Enable\land A_0$；(2) 標在 $A_2$ 輸出旁，因此代表 $A_2$。各級的翻轉條件為：

$$T_0=Enable,\qquad T_1=Enable\land A_0,\qquad T_2=Enable\land A_0\land A_1$$

Clear 接到帶反相泡泡的低有效清除端，因此 $Clear=0$ 時清為 $A_3A_2A_1A_0=0000$。

解題方法

題目沒有指定 $Enable$ 與 $Clear$ 的輸入波形。以下採用計數器常見的操作假設：初始清除已完成，接著 $Clear=1$（不清除）、$Enable=1$（持續計數）。每個上升沿後，計數值加一。

依序計數：

$$0000\rightarrow0001\rightarrow0010\rightarrow0011\rightarrow0100\rightarrow0101$$

其中狀態以 $A_3A_2A_1A_0$ 表示；$(1)=Enable\land A_0$，$(2)=A_2$。

核心觀念

本題考單週期 CPU 的控制訊號：根據指令的資料路徑，判斷各個多工器選擇、暫存器寫入及記憶體讀寫是否需要啟用。

以下以 $1$ 表示訊號致能、$0$ 表示訊號不致能、$X$ 表示不必在意。Mem to Reg 只有在 RegWrite=1 時才會影響結果；若指令不寫回暫存器，該訊號就是 $X$。

解題方法

逐一追蹤指令需要的資料路徑：

• AluSrc：選擇 ALU 第二個運算元。選暫存器資料為 $0$，選立即數為 $1$。
• Mem to Reg：選擇寫回暫存器的資料來源。選 ALU 結果為 $0$，選記憶體讀取資料為 $1$。
• RegWrite：是否寫入暫存器。
• MemRead、MemWrite：是否讀取或寫入資料記憶體。
• PCSrc：是否選擇分支目標位址。beq 只有在比較結果相等時才跳轉，因此此訊號取決於 ALU 的 Zero。

各指令訊號判斷

指令	AluSrc	Mem to Reg	RegWrite	MemRead	MemWrite	PCSrc
beq	0	X	0	0	0	Zero
sub	0	0	1	0	0	0

解題步驟

1. 程式總指令數
   $I = 1.2\!\times\!10^6 + 2.2\!\times\!10^6 + 0.5\!\times\!10^6 = 3.9\!\times\!10^6\;\text{指令}$

2. 執行時間公式
   $\text{Time}= \frac{I \times \text{CPI}}{\text{Clock\;Rate}}$
   （Clock Rate 以 GHz 為單位，需除以 $10^9$ 轉為 Hz）

3. 各 CPU 執行時間

CPU	CPI	Clock (GHz)	Time (ms)
P1	3	2	$\displaystyle\frac{3.9\times10^6 \times 3}{2\times10^9}=5.85$
P2	1.5	1	$\displaystyle\frac{3.9\times10^6 \times 1.5}{1\times10^9}=5.85$

組合語說明

• $x5$：累加結果 $result$ → 初始為 $0$
• $x6$：迴圈變數 $i$ → 初始為 $0$
• $x10$：指向 $MemArray$ 首元素的指標
• $x2$（或 $x29$）：迴圈上界 $100$

缺少的指令（放在迴圈前）：

    li   x5, 0          # result = 0
    li   x6, 0          # i = 0
    la   x10, MemArray  # x10 = &MemArray[0]
    li   x2, 100        # 上界 100 (或 li x29,100 若使用 x29)

迴圈內部修正（將 “?” 位置換成正確操作）：

核心觀念

Direct-mapped cache 的 64 位元記憶體位址分成三部分：

$$\text{Address}= \boxed{\text{Tag}}\;|\;\boxed{\text{Index}}\;|\;\boxed{\text{Block offset}}$$

其中：

• Block offset：指出資料位於一個 cache block 內的哪個 byte。
• Index：選擇 cache 中的哪一列。
• Tag：辨識該列目前存放的是哪一個主記憶體區塊。

依題意，每個 cache block 儲存一個 doubleword，且採用 byte addressing。

---

解題方法

doubleword 大小

一個 doubleword 為 $64$ bits：

$$64\text{ bits}=8\text{ bytes}$$

Cache 共容納 $2048$ 個 doubleword，因此共有 $2048$ 個 cache line：

$$2048=2^{11}$$

所以 Index 需要 $11$ bits。

每個 cache block 有 $8$ bytes，因此 Block offset 需要：

$$\log_2 8=3\text{ bits}$$

---

（a）Tag bits

64 位元位址扣除 Index 與 Block offset：

$$\text{Tag bits} =64-11-3 =50\text{ bits}$$

因此：

$$\boxed{\text{Tag}=50\text{ bits}}$$

位址格式為：

$$\boxed{50\text{ bits Tag}}\;|\;\boxed{11\text{ bits Index}}\;|\;\boxed{3\text{ bits Offset}}$$

---

（b）Cache 的總位元數

每個 cache line 包含：