108 年 國立中山大學資訊工程學系碩士班甲組《計算機結構》

核心觀念

單精度浮點數採用 IEEE 754 格式，共 32 位元：

$$\text{sign}_1\ |\ \text{exponent}_8\ |\ \text{fraction}_{23}$$

一般數值的表示式為

$$(-1)^s \times (1.f)_2 \times 2^{E-127}$$

但當 exponent 全為 $0$ 且 fraction 全為 $0$ 時，表示零。

解題方法

零沒有正負之分時，通常採用正零，因此：

• sign：$0$
• exponent：$00000000$
• fraction：$00000000000000000000000$

依照題目指定格式組合：

核心觀念

本題考查 IEEE 754 單精度浮點數格式。單精度共 32 位元，分為：

• 1 位元符號位元 $s$
• 8 位元指數欄位 $E$
• 23 位元小數欄位 $F$

對於正常化數值，其表示式為：

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

其中 $127$ 為單精度的 exponent bias。

解題方法

首先將 $0.5$ 轉成二進位：

$$0.5 = 2^{-1} = (0.1)_2$$

正常化後為：

$$(0.1)_2 = (1.0)_2 \times 2^{-1}$$

因此：

1. 符號位元

   數值為負數，所以：

   $$s=1$$

2. 指數欄位

   實際指數為 $-1$，加上 bias $127$：

   $$E=-1+127=126$$

   $126$ 的 8 位元二進位表示為：

   $$126=(01111110)_2$$

3. 小數欄位

   正常化有效數為 $1.0$，隱藏的 leading $1$ 不存入欄位，因此小數欄位全部為 $0$：

核心觀念

IEEE 754 單精度浮點數共有 32 位元：

• 1 位元符號位元
• 8 位元指數欄位，偏移值（bias）為 $127$
• 23 位元 fraction 欄位

對於一般的正規化數（ordinary normalized number），表示式為

$$(-1)^s \times (1.f)_2 \times 2^e$$

其中

$$e=E-127$$

$E$ 為指數欄位所代表的無偏移指數。指數欄位全為 $1$ 時保留給無限大與 NaN，因此最大一般數的指數欄位為：

$$11111110_2=254$$

所以實際指數為

$$e=254-127=127$$

解題方法

要使浮點數的絕對值最大，必須同時讓有效數字與指數都最大。

1. 指數最大：指數欄位取 $11111110_2$，得到實際指數 $127$。
2. 有效數字最大：23 個 fraction 位元全部取 $1$：

核心觀念

IEEE 754 單精度浮點數由以下欄位組成：

• 符號位：$1$ bit
• 指數欄位：$8$ bits，偏移值（bias）為 $127$
• 小數欄位：$23$ bits

正常化的有限數表示為：

$$(-1)^s \times (1.f)_2 \times 2^{E-127}$$

其中指數欄位 $E=1\sim254$；$E=0$ 保留給零與非正常化數，$E=255$ 保留給無限大與 NaN。

解題方法

要使數值的 magnitude（絕對值）最小，需要同時取：

1. 最小的正常化有效數字：

$$(1.000000\cdots000)_2$$

也就是小數欄位全部為 $0$。

2. 最小的實際指數：

正常化數不能使用 $E=0$，因此最小指數欄位為 $E=1$：

$$e=E-127=1-127=-126$$

核心觀念

IEEE 754 單精度浮點數包含：

• 1 位符號位元
• 8 位指數位元，偏移值（bias）為 $127$
• 23 位 fraction

當指數欄全為 $0$ 且 fraction 不為 $0$ 時，表示次正規數（subnormal number）：

$$(-1)^s \times (0.f)_2 \times 2^{1-127}$$

因此次正規數的有效指數為：

$$1-127=-126$$

次正規數沒有隱含的開頭 $1$。

解題方法

要找最小非零 magnitude：

1. 符號不影響 magnitude，因此取正數。
2. 指數欄設為全 $0$，有效指數為 $-126$。
3. 23 位 fraction 中，最小的非零值只有最低位為 $1$：

核心觀念

本題考查 IEEE 754 單精度浮點數（binary32）的格式與可表示範圍：

• 1 位元：符號位元 $s$
• 8 位元：指數欄位 $E$
• 23 位元： fraction 欄位 $F$
• 指數偏移量（bias）為 $127$

對於正規化數，其值為

$$x=(-1)^s\left(1+\frac{F}{2^{23}}\right)2^{E-127}$$

其中正規化數的指數欄位為 $1\le E\le254$。

解題方法

先求正規化數的指數範圍：

$$E-127\in[1-127,\,254-127]=[-126,127]$$

最大正規化數發生在：

• 符號位元為 $0$
• 指數欄位 $E=254$
• fraction 欄位全為 $1$

此時有效數字為

$$1.111\ldots111_2=2-2^{-23}$$

因此最大有限值為

$$(2-2^{-23})2^{127} =2^{128}-2^{104} \approx 3.402823466\times10^{38}$$

最小正規化正數發生在：

• 指數欄位 $E=1$
• fraction 欄位全為 $0$

因此為

$$1.0_2\times2^{-126}=2^{-126} \approx1.175494351\times10^{-38}$$

負數範圍由符號位元取得對稱結果。

IEEE 754 另有非正規化數（subnormal numbers）。當 $E=0$ 且 $F\ne0$ 時，沒有隱含的前導 $1$，其值為

$$x=(-1)^s\left(\frac{F}{2^{23}}\right)2^{-126}$$

最小正非正規化數為

核心觀念

本題考查 IEEE 754 單精度浮點數的表示方式與「相鄰浮點數間距」的變化。

以 IEEE 754 binary32 為例：

• 1 個符號位元
• 8 個指數位元
• 23 個 fraction 位元
• 正規化數實際具有 24 位有效二進位數字，因為隱含最前面的 $1$

正規化浮點數可表示為

$$x=(1.f)_2\times 2^e$$

其中有效數字固定有 24 位，但指數 $e$ 會改變數值的尺度。

解題方法

先固定指數 $e$。相鄰的有效數字相差

$$2^{-23}$$

因此，當指數固定時，相鄰浮點數的絕對距離為

$$2^e\times 2^{-23}=2^{e-23}$$

所以在同一個區間

$$[2^e,2^{e+1})$$

內，相鄰浮點數的間距相同；但當指數增加 $1$ 時，間距也會增加為原來的 $2$ 倍。

例如：

在 $1$ 附近，下一個可表示的單精度浮點數為

$$1+2^{-23}$$

兩者距離為

核心觀念

本題考查二補數固定小數點表示法中，最小有效位元（Least Significant Bit, LSB）所代表的數值，以及可表示數值之間的間距。

16 個小數位表示小數點後最末位的權重為

$$2^{-16}$$

因此，每增加一個最低位元，所表示的數值就增加 $2^{-16}$。

---

解題方法

將 32 位元二補數固定小數表示值視為一個帶符號的 32 位元整數 $I$，再將小數點向左移 16 位：

$$\text{數值}=I\times 2^{-16}$$

其中 $I$ 的相鄰整數值相差 $1$。若兩個相鄰可表示數值分別對應到 $I$ 與 $I+1$，則其距離為

$$(I+1)2^{-16}-I2^{-16} =2^{-16}$$

所以所有相鄰可表示數值的距離皆為

核心觀念

本題考查二補數有號定點數的可表示範圍。

依前一題常用的 32 位元格式，假設配置為：

• 1 位元符號位元
• 15 位元整數部分
• 16 位元小數部分

因此每一個可表示數值的最小間距為

$$2^{-16}$$

二補數的 32 位元原始整數範圍為

$$-2^{31}\leq C\leq 2^{31}-1$$

定點數的實際值為

$$x=C\times 2^{-16}$$

解題方法

最小值由二補數位元型態

$$100\cdots 0$$

表示，其原始整數值為 $-2^{31}$，所以

$$x_{\min}=-2^{31}\times 2^{-16}=-2^{15}$$

最大值由

$$011\cdots 1$$

表示，其原始整數值為 $2^{31}-1$，所以

$$x_{\max}=(2^{31}-1)\times 2^{-16}$$

整理得

$$x_{\max}=2^{15}-2^{-16}$$

因此數值範圍為

核心觀念

本題考查「固定小數點加法」與「浮點數加法」的硬體運算流程差異。

對於正常化的單精度浮點數，可表示為

$$X=(-1)^s(1.f)_2\times 2^E$$

其中包含：

• $s$：符號位元
• $E$：實際指數，儲存時使用 bias $127$
• $f$： fraction 欄位；正常數的有效尾數實際上有隱含的最高位 $1$，因此通常為 $24$ 位有效精度

浮點數相加不只是將兩個 32 位元數字直接送入加法器，而是必須先處理指數與有效尾數。

解題方法

32 位元固定小數點數相加時，兩個數的二進位小數點位置固定且相同，因此可直接進行整數式加法：

$$A+B$$

每一位只需計算和與進位。硬體可使用 carry-lookahead adder、carry-select adder 或 prefix adder，使進位傳遞延遲縮短，在一個時脈週期內完成。若使用二補數，溢位也只需檢查最高位附近的進位：

$$\text{Overflow}=C_{31}\oplus C_{32}$$

浮點數加法則通常包含下列步驟：

1. 拆解欄位：取出符號、指數與有效尾數，並補上正常數的隱含最高位 $1$。

2. 比較指數：計算兩個指數的差值

   $$\Delta E=|E_1-E_2|$$

3. 對齊有效尾數：將指數較小的數，其有效尾數向右位移 $\Delta E$ 位，使兩數具有相同指數。例如：

   $$1.100_2\times 2^5 + 1.010_2\times 2^2$$

   必須先將第二項改寫為

   $$1.100_2\times 2^5 + 0.001010_2\times 2^5$$

4. 有效尾數相加或相減：符號相同時做加法，符號不同時做大小數相減。

5. 正規化：結果必須重新調整為 $1.f\times 2^E$ 的形式。若加法產生進位，需將尾數右移一位並將指數加一；若減法產生前導零，需將尾數左移若干位並將指數減少相同數值。

核心觀念

本題考查 Amdahl 定律：整體效能提升受限於未被加速的部分。

原執行時間中：

• 計算部分：$40\%$，可因新處理器而加速 $10$ 倍。
• I/O 等待部分：$60\%$，不受處理器速度提升影響。

Amdahl 定律為：

$$S_{\text{overall}} = \frac{1}{\text{未加速比例}+\frac{\text{可加速比例}}{\text{加速倍數}}}$$

解題方法

設舊處理器的總執行時間為 $T$。

計算部分原本耗時：

$$T_{\text{compute}}=0.4T$$

新處理器快 $10$ 倍，因此計算部分變為：

$$T'_{\text{compute}}=\frac{0.4T}{10}=0.04T$$

I/O 等待部分未被加速，仍為：

$$T_{\text{I/O}}=0.6T$$

所以新處理器的總執行時間為：

$$T'=0.04T+0.6T=0.64T$$

整體 speedup 為：

核心觀念

本題考查 Amdahl’s law（阿姆達定律），用來描述平行化後的理論加速比。

設：

• $f$：原始計算中必須循序執行的比例
• $1-f$：可平行執行的比例
• $N$：處理器數量
• $S$：整體加速比

使用 $N$ 個處理器時，正規化後的執行時間為

$$T_N=f+\frac{1-f}{N}$$

因此加速比為

$$S=\frac{1}{f+\frac{1-f}{N}}$$

解題方法

題目給定：

$$S=80,\qquad N=100$$

代入 Amdahl 定律：

$$80=\frac{1}{f+\frac{1-f}{100}}$$

取倒數：

$$\frac{1}{80}=f+\frac{1-f}{100}$$

整理右式：

$$\frac{1}{80}=f+\frac{1}{100}-\frac{f}{100}$$ $$\frac{1}{80}=\frac{99}{100}f+\frac{1}{100}$$

移項得：

核心觀念

當程式進行遠端記憶體存取（Remote Memory Access）時，處理器會產生停頓（Stall）。總 $\text{CPI}$ 為基底 $\text{CPI}_{\text{base}}$ 加上遠端存取所造成的額外停頓 $\text{CPI}$。無通訊相較於有通訊的加速比（Speedup），即為兩者 $\text{CPI}$ 之比值（$\frac{\text{CPI}_{\text{new}}}{\text{CPI}_{\text{base}}}$）。

---

詳細推導與計算

1. 計算每次遠端記憶體存取之停頓週期數（Stall Cycles）：
   $\text{Stall Cycles} = \text{Remote Memory Latency} \times \text{Clock Frequency}$

核心觀念

本題使用處理器效能方程式：

$$\text{CPU Time} = \text{Instruction Count}\times \text{CPI}\times \text{Clock Cycle Time}$$

兩種設計的指令數與時脈週期時間皆視為相同，因此只需比較整體平均 CPI；整體 CPI 必須依各類指令比例加權平均。

---

基準設計的 CPI

浮點運算占全部操作的 $25\%$，其他操作占 $75\%$：

$$\text{CPI}_{\text{base}} =0.25(4.0)+0.75(1.33) =1.9975$$

原本的浮點平均 CPI $4.0$ 已包含浮點除法。設非浮點除法的浮點運算 CPI 為 $x$，則：

$$0.02(20)+0.98x=4.0$$ $$x=\frac{4.0-0.4}{0.98} =\frac{3.6}{0.98} \approx 3.6735$$

---

方案一：將浮點除法 CPI 降至 2

新的浮點平均 CPI 為：

$$\text{CPI}_{\text{FP,1}} =0.02(2)+0.98(3.6735) =0.04+3.6 =3.64$$

因此整體 CPI：

$$\text{CPI}_{1} =0.25(3.64)+0.75(1.33) =0.91+0.9975 =1.9075$$

---

方案二：將所有浮點運算的平均 CPI 降至 2.5

新的整體 CPI 為：

核心觀念

本題考查同步 CPU 的最小時脈週期與最大工作頻率。資料必須在下一個時脈邊緣前，完成暫存器輸出、組合邏輯運算，並滿足目的暫存器的 setup time。

對任一條暫存器到暫存器的路徑：

$$T_{\text{clk}} \ge t_{\text{cq,max}} + t_{\text{logic,max}} + t_{\text{setup}} + t_{\text{margin}}$$

其中：

• $t_{\text{cq,max}}$：來源暫存器的 clock-to-Q 最大延遲。
• $t_{\text{logic,max}}$：該路徑上組合邏輯的最大延遲。
• $t_{\text{setup}}$：目的暫存器的 setup time。
• $t_{\text{margin}}$：時脈偏移與時脈不確定性所需的安全裕度。

因此，最大工作頻率為：

$$f_{\max}=\frac{1}{T_{\text{clk,min}}}$$

解題方法

題幹所稱的「above CPU」架構圖、各元件延遲與暫存器參數未附上，因此無法得到唯一的數值頻率；以下以標準同步 CPU 模型表示答案。

先找出 CPU 中所有從狀態元件出發、到下一個狀態元件結束的資料路徑，分別計算每條路徑的延遲：

$$T_i= t_{\text{cq},i} + t_{\text{logic},i} + t_{\text{setup},i} + t_{\text{margin},i}$$

CPU 的時脈週期必須滿足最慢路徑，因此：

核心觀念

本題考查理想管線（pipeline）的 throughput、整體 latency 與平均 CPI。題目單獨提供的內容未明示管線級數 $k$ 與時脈週期 $T_c$，以下採用計算機結構常見的理想 $k$ 級管線模型：

• 共 $N=100$ 條指令。
• 每個管線級耗用一個 clock cycle。
• 沒有 hazard，因此不會產生 stall 或 bubble。
• 管線填滿後，每個 cycle 完成一條指令。

解題方法

第一條指令必須經過全部 $k$ 個管線級，因此在第 $k$ 個 cycle 完成。之後每個 cycle 完成一條指令，所以第 $100$ 條指令在

$$k+(100-1)=k+99$$

個 cycle 完成。

因此，整個任務的總執行 cycle 數為

$$C_{\text{total}}=k+99$$

總 latency 為

$$L_{\text{task}}=(k+99)T_c$$

平均 CPI 為總 cycle 數除以指令數：

$$\text{CPI}_{\text{avg}} =\frac{C_{\text{total}}}{N} =\frac{k+99}{100} =1+\frac{k-1}{100}$$

管線填滿後的穩態 throughput 為每個 cycle 完成一條指令：

$$\text{Throughput}_{\text{steady}}=\frac{1}{T_c}$$

若把「這 100 條指令從開始到全部完成」計算成整體平均 throughput，則為

$$\text{Throughput}_{\text{task}} =\frac{100}{(k+99)T_c}$$

以「每 cycle 完成幾條指令」表示時：

核心觀念

本小題單獨摘錄時缺少前文的五段延遲資料；依原題前文，五個管線階段延遲為：IF $20\text{ ns}$、ID $20\text{ ns}$、EX $50\text{ ns}$、MA $40\text{ ns}$、WB $30\text{ ns}$。原題 PDF

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

$$T_{\text{cycle}}=\max(t_1,t_2,\ldots,t_n)$$

因此最大工作頻率為：

$$f_{\max}=\frac{1}{T_{\text{cycle}}}$$

合併兩個相鄰階段時，新階段延遲等於兩者延遲相加。為維持原本的資料流順序，只需比較四種相鄰階段的合併方式。

解題方法與候選設計比較

合併階段	新階段延遲	最大階段延遲	最大工作頻率
IF＋ID	$20+20=40\text{ ns}$	$50\text{ ns}$	$20\text{ MHz}$
ID＋EX	$20+50=70\text{ ns}$	$70\text{ ns}$	$14.29\text{ MHz}$
EX＋MA	$50+40=90\text{ ns}$	$90\text{ ns}$	$11.11\text{ MHz}$

核心觀念

資料危障（data hazard）是指在管線化處理器中，後續指令依賴前一指令產生的資料，但前一指令尚未完成寫入，導致後續指令在錯誤時間讀取資料的情況。

常見類型如下：

• RAW（Read After Write）：後指令要讀取前指令寫入的資料，亦稱真正資料相依。
• WAR（Write After Read）：後指令寫入資料，但前指令尚未讀取完畢。
• WAW（Write After Write）：兩個指令寫入同一目的位置，寫入順序可能錯亂。

在一般依序發射的五級管線中，最常見的是 RAW。

解題方法與組合語言範例

以下使用類似 MIPS 的組合語言：

LW   R1, 0(R2)      ; R1 ← Memory[R2 + 0]
ADD  R3, R1, R4     ; R3 ← R1 + R4

分析資料流：

1. LW 指令將記憶體資料寫入暫存器 R1。
2. 下一個 ADD 指令需要讀取 R1。
3. LW 的資料要到 MEM 階段結束後才取得，但 ADD 在 EX 階段就需要使用 R1。
4. 因此，ADD 可能在 R1 尚未準備好時讀取資料，形成 RAW data hazard，又稱 load-use hazard。

以五級管線 IF → ID → EX → MEM → WB 為例：

核心觀念

Super-pipeline（超級管線化）是將傳統 pipeline 的每個階段再細分成更小的子階段，使每個階段所需的組合邏輯延遲縮短，進而提高時脈頻率。

例如，原本的五級管線：

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

可再細分為更多級，使單一時脈週期能完成的工作量變少，但整體時脈變快。其重點是「增加 pipeline 深度」，不是增加同時發射的指令數，因此與 superscalar architecture 不同。

傳統管線的時脈週期約為：

$$T_{\text{cycle}} \approx \max(t_{\text{logic}})+t_{\text{register}}$$

其中 $t_{\text{logic}}$ 是最慢階段的組合邏輯延遲，$t_{\text{register}}$ 包含 pipeline register 的 setup time、clock-to-Q delay 與 clock skew。

若將邏輯階段細分為 $k$ 個子階段，理想情況下：

$$T'_{\text{cycle}} \approx \frac{t_{\text{logic}}}{k}+t_{\text{register}}$$

因此時脈頻率可提高：

$$f'=\frac{1}{T'_{\text{cycle}}}$$

但由於每增加一級就會增加暫存器與時脈控制成本，實際加速通常小於理想的 $k$ 倍。

解題方法

本題要求說明超級管線化的定義，以及其優缺點。作答時可依照「切細管線階段 → 時脈變快 → 效能收益與額外代價」的順序說明。

1. 先指出 super-pipeline 是將原有管線階段細分，增加管線深度。
2. 再說明階段變短後，時脈週期縮短，指令完成吞吐量提高。
3. 最後分別列出效能上的優點，以及深管線帶來的硬體與控制成本。

優點

• 提高時脈頻率與指令吞吐量

  每一級只需處理較少的組合邏輯，因此可以縮短時脈週期、提高 clock rate。當管線填滿後，理想狀況下仍可每個 clock cycle 完成一條指令，故單位時間完成的指令數增加。

• 提高管線階段的平衡性

  若原本某個 pipeline stage 特別慢，可以再將其細分，使各階段延遲更接近，減少最慢階段對整體時脈週期的限制。

• 不必主要依靠多重功能單元

  Super-pipeline 主要透過增加管線深度提升效能，不必像 superscalar 一樣大量複製執行單元並在同一週期發射多條指令，因此在某些設計中可降低功能單元複製的需求。

缺點

• 管線暫存器與時脈控制成本增加

核心觀念

直接對映快取（direct-mapped cache）中，每個主記憶體位址分為三個欄位：

• 區塊內位移（block offset）：指出資料位於一個區塊中的哪個位元組。
• 索引（index）：指出該資料應放入哪一條快取列。
• 標籤（tag）：辨識目前快取列所儲存的記憶體區塊。

快取總位元數包含：

$$\text{資料位元}+\text{標籤位元}+\text{有效位元}$$

解題方法

快取資料容量為 $16\text{K bytes}=16\times 1024=16384$ bytes，每個區塊大小為 $16$ bytes，因此快取共有：

$$\frac{16384}{16}=1024=2^{10}$$

條快取列。

每個區塊大小為 $16=2^4$ bytes，所以區塊內位移需要：

$$\log_2 16=4\text{ bits}$$

快取共有 $1024=2^{10}$ 條列，因此索引需要：

$$\log_2 1024=10\text{ bits}$$

地址長度為 $32$ bits，故標籤位元數為：

$$32-10-4=18\text{ bits}$$

每條快取列包含：

• 資料：$16$ bytes $=128$ bits
• 標籤：$18$ bits
• 有效位元：$1$ bit

因此每條快取列需要：

$$128+18+1=147\text{ bits}$$

核心觀念

本題承接 4.1 的條件：資料快取容量為 $16\text{K bytes}$、每個區塊大小為 $16\text{ bytes}$、位址長度為 $32$ 位元，每個 cache block 配置一個 valid bit。原試題 PDF

二路組合快取中，每個 set 包含兩個 cache block。位址格式分為：

$$\text{Tag} \mid \text{Set index} \mid \text{Block offset}$$

總位元數為：

$$\text{資料位元}+ \text{所有 cache block 的 Tag 位元}+ \text{所有 cache block 的 Valid 位元}$$

解題方法

1. 計算 cache block 數量：

$$16\text{K bytes}=16\times 1024=2^{14}\text{ bytes}$$ $$16\text{ bytes}=2^4\text{ bytes}$$

因此：

$$\text{Cache blocks}=\frac{2^{14}}{2^4}=2^{10}=1024$$

2. 計算 set 數量：

因為是二路組合，每個 set 有兩個 block：

$$\text{Sets}=\frac{1024}{2}=512=2^9$$

3. 計算位址欄位：

• Block offset：每個 block 為 $16$ bytes，因此需要

$$\log_2 16=4\text{ bits}$$

• Set index：共有 $512$ 個 sets，因此需要

$$\log_2 512=9\text{ bits}$$

• Tag：

核心觀念

本題要求將上一題的快取記憶體配置改為「全相聯快取」重新分析。全相聯快取的核心特性是：

• 主記憶體的任一區塊可以放入快取中的任一列。
• 位址不再切成索引欄位（index）。
• 每次存取時，將位址中的標籤（tag）與快取內所有有效列的標籤同時比較。
• 若任一列比對成功，即為快取命中（hit）；全部失敗則為未命中（miss）。

由於題目只提供「Repeat the above problem」，但未附上上一題的快取大小、區塊大小、位址長度與存取序列，因此無法產生上一題所要求的特定數值結果。以下以一般參數完整推導。

---

位址欄位的推導

設：

• 主記憶體位址長度為 $A$ 位元
• 每個快取區塊大小為 $B$ bytes
• 快取共有 $C$ 個區塊或快取列
• 記憶體採 byte-addressable

每個區塊內的 byte 數為 $B$，因此區塊內位移量需要：

$$\text{block offset}=\log_2 B$$

全相聯快取沒有 index 欄位，所以其位址格式為：

$$\boxed{\text{Tag}\ |\ \text{Block offset}}$$

標籤欄位長度為：

$$\text{tag bits}=A-\log_2 B$$

若每個區塊包含 $W$ 個 word，且每個 word 有 $K$ bytes，則：

$$B=W\times K$$

因此：

$$\text{block offset}=\log_2(WK)$$

---

解題方法

1. 將位址換算成記憶體區塊編號

對 byte 位址 $x$，其記憶體區塊編號為：

$$\text{block number}=\left\lfloor \frac{x}{B}\right\rfloor$$

區塊內位移量為：

$$\text{offset}=x\bmod B$$

在全相聯快取中，區塊編號的高位部分作為 tag。由於沒有 index，因此不需要計算固定的快取列位置。

---

2. 判斷命中或未命中

每次存取某一記憶體區塊時：

1. 將該區塊的 tag 與快取內所有有效列的 tag 比較。
2. 若任一列相等，則為 hit。
3. 若所有列都不相等，則為 miss。
4. 發生 miss 時，可將新區塊放入任何空的快取列。
5. 若快取已滿，必須依照替換策略選擇一列，例如 LRU、FIFO 或 random。

全相聯快取的判斷條件可寫成：

$$\text{hit} \iff \exists i\in\{0,1,\ldots,C-1\}, \quad \text{valid}_i=1 \ \land\ \text{tag}_i=\text{requested tag}$$

---

與直接映射快取的差異

若上一題為直接映射快取，通常位址格式為：

$$\text{Tag}\ |\ \text{Index}\ |\ \text{Block offset}$$

其中：

$$\text{index bits}=\log_2 C$$

核心觀念

本題比較三種快取配置方式：

1. 直接對映（direct-mapped）
2. 全相聯（fully associative）
3. 組相聯（set-associative）

設快取共有 $C$ 個 cache lines，每個主記憶體區塊編號為 $b$，組相聯路數為 $A$，則組數為

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

區塊通常先依索引決定可放置的位置，再以 tag 比較是否命中。三種設計的主要差異，在於「一個記憶體區塊可以放在哪些 cache lines」。

---

一、直接對映快取

每個記憶體區塊只能放入唯一的一個 cache line：

$$\text{line index}=b\bmod C$$

查找時，利用 index 直接選出一個 cache line，再比較其 tag。

優點

• 硬體最簡單，只需一組 tag 比較器。
• 查找速度快，索引後只需檢查一個位置。
• 成本、面積與功率消耗最低。
• 不需要執行複雜的替換決策，因為每個區塊的位置已經固定。

缺點

• 衝突遺失（conflict miss）嚴重。
• 若兩個經常使用的區塊對映到同一個 line，即使快取仍有其他空間，也會互相替換，形成反覆失誤（thrashing）。
• 快取使用彈性最低，整體命中率通常不如組相聯與全相聯設計。

---

二、全相聯快取

任何記憶體區塊都可以放入快取中的任意一個 cache line，不使用固定的 index：

$$\text{可放置位置}=\text{所有 }C\text{ 個 cache lines}$$

查找時，將輸入位址的 tag 同時與所有有效 cache lines 的 tag 比較。

優點

• 完全避免由配置位置造成的衝突遺失。
• 快取空間利用率最高，任何空閒 line 都可以存放新區塊。
• 在快取容量固定時，通常具有最高的命中率。
• 適合項目數量少、但每次查找都必須快速完成的結構。

缺點

• 需要同時比較最多 $C$ 個 tags，必須使用大量平行比較器。
• tag 比較、結果選擇與替換硬體較複雜。
• 面積、功率與製造成本較高。
• 快取容量增大時，硬體成本與配線複雜度會快速上升。
• 當快取滿載時，必須使用替換策略，例如 LRU、FIFO 或 pseudo-LRU。

全相聯仍可能發生強制遺失（compulsory miss）與容量遺失（capacity miss），但不會發生因固定對映位置造成的衝突遺失。

---

三、組相聯快取

快取被分成 $S$ 組，每組有 $A$ 個 cache lines。記憶體區塊先對映到唯一的一組：

$$\text{set index}=b\bmod S$$

但在該組內，可以放入任意一個 cache line。查找時，先由 set index 找到該組，再平行比較該組內 $A$ 個 tags。

直接對映與全相聯可視為組相聯的兩個極端：

• 直接對映：$A=1$
• 全相聯：$A=C$，只有一組
• $A$ 路組相聯：$1<A<C$

優點

• 比直接對映大幅降低衝突遺失。
• 比全相聯需要的比較器少，硬體成本與功率較低。
• 查找速度、命中率與硬體複雜度之間具有良好折衷。
• 可在每組內採用替換策略，增加配置彈性。

缺點

核心觀念

平均記憶體存取時間可用下式表示：

$$\text{AMAT} = \text{命中時間} + \text{未命中率}\times\text{未命中代價}$$

其中：

• 命中時間：快取存取並完成命中判斷所需時間。
• 未命中率：每一個指令平均發生的 cache miss 次數。
• 未命中代價：一次 cache miss 額外花費的處理時間。

本題已說明讀取與寫入的 miss penalty 相同，且忽略其他寫入停頓，因此只需直接套用公式。

解題方法

處理各項數值的單位：

$$\text{命中時間}=1\text{ clock cycle}$$ $$\text{未命中代價}=20\text{ clock cycles}$$ $$\text{未命中率}=0.05\text{ misses/instruction}$$

先以 clock cycle 為單位計算：

$$\begin{aligned} \text{AMAT} &=1+0.05\times20\\ &=1+1\\ &=2\text{ clock cycles/instruction} \end{aligned}$$

核心觀念

本題考查快取未命中造成的記憶體停頓，以及 CPI 與加速比的計算。

記憶體停頓造成的額外 CPI 為：

$$\text{Memory Stall CPI} = \text{每指令存取次數} \times \text{Miss Rate} \times \text{Miss Penalty}$$

實際 CPI 為：

$$\text{實際 CPI} = \text{基本 CPI} + \text{各類快取未命中停頓 CPI}$$

完美快取完全不會 miss，因此不產生 miss penalty。

解題方法

設處理器執行 $N$ 條指令。

1. 指令快取停頓

每條指令都需進行一次指令快取存取，因此指令快取未命中次數為：

$$N \times 2\% = 0.02N$$

造成的停頓週期為：

$$0.02N \times 100 = 2N$$

換算成每指令的額外 CPI：

$$\text{I-Cache Stall CPI}=2\%\times100=2$$

2. 資料快取停頓

Load 與 Store 指令比例為 $36\%$，因此資料快取存取次數為：

$$0.36N$$

資料快取 miss 次數為：

$$0.36N \times 4\%=0.0144N$$

造成的停頓週期為：

$$0.0144N \times 100=1.44N$$

因此：

核心觀念

本題考查兩層快取的平均記憶體存取時間（Average Memory Access Time, AMAT）。

• $L1$ 快取未命中率：

$$L1\text{ miss rate}=\frac{L1\text{ misses}}{\text{memory references}}$$

• $L2$ 的區域未命中率（local miss rate）是以「實際存取 $L2$ 的次數」為分母，而不是全部記憶體參考次數：

$$L2\text{ local miss rate} =\frac{L2\text{ misses}}{L2\text{ accesses}}$$

題目給定公式：

$$AMAT=L1\text{ hit time} +L1\text{ miss rate}\times \left(L2\text{ hit time} +L2\text{ local miss rate}\times L2\text{ miss penalty}\right)$$

解題方法

1. 計算 $L1$ 未命中率

1000 次記憶體參考中，$L1$ 發生 40 次未命中：

$$L1\text{ miss rate}=\frac{40}{1000}=0.04$$

2. 計算 $L2$ 的存取次數

只有 $L1$ 未命中的記憶體參考才會繼續查詢 $L2$，因此：

$$L2\text{ accesses}=40$$

解題觀念與推導

計算每條指令的平均記憶體停頓週期（Average Memory Stall Cycles per Instruction）需結合每條指令的記憶體存取次數與各級快取的缺失率（Miss Rate）及缺失懲罰（Miss Penalty）：

1. 基本公式：
   $\text{Average Memory Stall} = \text{L1\_misses\_per\_instruction} \times \text{L1\_miss\_penalty} + \text{L2\_misses\_per\_instruction} \times \text{L2\_miss\_penalty}$

2. 單位指令缺失數拆解：

   • $\text{L1\_misses\_per\_instruction} = \text{Memory references per instruction} \times \text{L1\_miss\_rate}_{\text{local}}$
   • $\text{L2\_misses\_per\_instruction} = \text{Memory references per instruction} \times \text{L1\_miss\_rate}_{\text{local}} \times \text{L2\_miss\_rate}_{\text{local}}$

3. 代入公式：
   $\text{Average Memory Stall} = 1.5 \times \left( \text{L1\_miss\_rate}_{\text{local}} \times \text{L1\_miss\_penalty} + \text{L1\_miss\_rate}_{\text{local}} \times \text{L2\_miss\_rate}_{\text{local}} \times \text{L2\_miss\_penalty} \right)$

---

參數假設與數值計算

核心觀念

本題考查 Flynn 系統分類法中的 SIMD（Single Instruction, Multiple Data，單指令多資料） 架構，著重於以下核心觀念：

1. 資料級平行（Data-Level Parallelism, DLP）：透過單一控制單元抓取與解碼指令，將相同的操作廣播至多個算術邏輯單元（ALU），同時處理向量或陣列中的多個資料元素。
2. 傳統 CPU 的 SIMD 架構：採用以向量暫存器（Vector Registers）為核心的媒體擴充指令集（如 x86 的 SSE/AVX、ARM 的 NEON）。
3. GPU 的 SIMD 實作（SIMT 模式）：以單指令多執行緒（Single Instruction, Multiple Threads, SIMT）為程式抽象介面，結合硬體 Warp / Wavefront 動態排程機制所實現的大規模平行 SIMD 執行架構。

---

解題方法

一、 SIMD 的核心優勢（Advantages of SIMD）

1. 極高的計算吞吐量（High Throughput）：
   單一指令即可同時對長度為 $N$ 的向量或陣列資料執行相同運算，使每個時脈週期（Clock Cycle）完成的運算次數擴增為原本純量（Scalar）執行的 $N$ 倍，顯著提升資料平行應用的執行速度。
2. 降低指令提取與解碼開銷（Low Control Overhead）：
   相較於 MIMD（多指令多資料）需要多個獨立的控制單元，SIMD 僅需一組控制邏輯負責指令提取（Instruction Fetch）與解碼（Instruction Decode）。晶片大幅節省了指令快取（I-Cache）頻寬與控制電路的晶片面積。
3. 優秀的晶片面積與能源效率（Energy & Area Efficiency）：
   將省下的控制邏輯與分支預測電路面積，轉而配置給更多的 ALUs 與暫存器檔案（Register File），極大地提高了每瓦特效能（Performance per Watt）與單位面積運算密度。

---

二、 傳統 CPU SIMD 與 GPU SIMD 之差異比較

比較項目	傳統 CPU 中的 SIMD	GPU 中的 SIMD (SIMT)
硬體執行模型	向量暫存器型 SIMD<br>(Vector-based SIMD)	單指令多執行緒<br>(SIMT: Single Instruction, Multiple Threads)
程式設計模型	顯式向量化（Explicit Vectorization）<br>工程師需直接呼叫向量 Intrinsics（如 __m256）或仰賴編譯器自動向量化，程式員顯式操控向量暫存器。	純量執行緒模型（Scalar Thread Model）<br>工程師撰寫單一純量執行緒（Thread）的 Kernel 邏輯，由硬體自動將多個執行緒（如 32 個）編組為 Warp/Wavefront 並以 SIMD 方式執行。
向量寬度與規模	較窄（Narrow Vector Width）<br>暫存器寬度通常為 128-bit 至 512-bit（例如 AVX-512 單一指令同時處理 16 個 32-bit 單精度浮點數）。