大二下計算機結構

一、 指令總數 (Instruction Count, IC)#

• 定義：執行完某個特定程式，CPU 總共需要執行的機械碼（機器指令）總條數。
• 物理意義：代表該任務的工作量大小。
• 決定因素：主要由軟體層面決定，包含演算法效率、原始碼寫法、程式語言特性，以及編譯器（Compiler）的優化能力。

二、 每條指令平均週期數 (Cycles Per Instruction, CPI)#

• 定義：程式執行期間，平均每執行一條硬體指令所需要消耗的時脈週期（Clock Cycle）數量。
• 物理意義：反映了硬體架構執行指令的效率。
• 計算特性：因為不同的指令（例如整數加法與浮點數除法）其複雜度與所需週期大不相同，工程實務上必須採用加權平均法計算： $\text{平均 CPI} = \sum_{i=1}^{n} (\text{該指令型態所需的 CPI}_i \times \text{該指令在程式中所佔的比例}_i)$
• 決定因素：主要由指令集架構（ISA）與處理器的微架構（Microarchitecture，如管線化、快取記憶體設計、超純量等）決定。

三、 時脈週期時間 (Clock Cycle Time, $T_c$)#

• 定義：處理器內部時鐘（振盪器）每跳動一下（一個電位脈衝）所花費的實際時間，通常以奈秒（$ns$, $10^{-9}$ 秒）或皮秒（$ps$, $10^{-12}$ 秒）為單位。
• 物理意義：代表 CPU 執行最基本硬體動作的最小時間單位（節拍）。

四、 時脈頻率 / 主頻 (Clock Rate, $f$)#

• 定義：處理器內部的時鐘在單位時間（通常為一秒）內跳動的次數，單位為赫茲（Hz），目前主流處理器多以吉赫茲（GHz, $10^9$ Hz）度量。
• 物理意義與關係：時脈頻率 $f$ 與時脈週期時間 $T_c$ 互為倒數關係。 $f = \frac{1}{T_c}$ 例如：若 $T_c = 0.2 \text{ ns}$，則其時脈頻率 $f = \frac{1}{0.2 \times 10^{-9}} = 5 \times 10^9 \text{ Hz} = 5 \text{ GHz}$。
• 決定因素：由硬體電路設計、流水線切分的深度，以及半導體晶圓製程（如 3nm, 2nm 工藝）共同決定。

【解析】#

$\text{最終整體 Speedup} = \text{純架構優化 Speedup (阿姆達爾定律)} \times \text{時脈頻率變動率}$

第一步：套用阿姆達爾定律，計算「純架構優化」的倍率 根據題目條件，提取公式參數：

• 可被優化的比例 $F = 60\% = 0.6$
• 該局部的加速倍率 $S = 4$

代入阿姆達爾定律公式，求出若在「頻率不變」的前提下，單靠加速器帶來的架構內在加速比： $\text{純架構 Speedup} = \frac{1}{(1 - F) + \frac{F}{S}} = \frac{1}{(1 - 0.6) + \frac{0.6}{4}} = \frac{1}{0.4 + 0.15} = \frac{1}{0.55}$

第二步：乘上「整體降頻 10%」的修正因子 時脈頻率（Clock Rate）降低 10%，代表新頻率變為原來的 $90\%$（即 $0.9$ 倍）。 因為效能與頻率成正比，頻率變慢會對效能帶來 $0.9$ 倍的無差別懲罰，故將第一步的結果乘以頻率變動率：

$\text{最終整體 Speedup} = \text{純架構 Speedup} \times \text{新頻率比例}$ $\text{最終整體 Speedup} = \frac{1}{0.55} \times 0.9 = \frac{0.9}{0.55} = \frac{18}{11} \approx \mathbf{1.64 \text{ 倍}}$

觀念與公式#

• 核心公式： $\text{Architecture} = \text{ISA} + \text{Machine Organization}$
• ISA (指令集架構)： 硬體與軟體的「合約」。規定了暫存器、指令格式、定址模式。
• Organization (機組組織)： 硬體的「實現」。例如 Pipeline 長度、Cache 大小。
• 設計原則 1： $\text{Simplicity favors regularity}$ (簡單源於規律性)。為了讓硬體解碼變快，MIPS 堅持指令格式必須整齊。

實戰演練#

Q：Intel i9 與 AMD Ryzen 設計不同，為何能跑同一個執行檔？ A： 因為它們擁有相同的 ISA (x86-64)，即硬體接口合約相同；但它們的內部 Organization (微架構) 不同，所以效能表現有異。

觀念與公式#

• 語法規矩： op dst, src1, src2 (1 個操作碼，3 個運算元)。
• 硬體限制： 即使 C 語言寫 f = g + h + i，MIPS 也必須拆成兩行。

實戰演練#

Q：將 f = (g + h) - (i + j) 翻譯為 MIPS。 Step-by-step：

1. add $t0, $s1, $s2 # $t0 = g + h$
2. add $t1, $s3, $s4 # $t1 = i + j$
3. sub $s0, $t0, $t1 # $f = t0 - t1$

觀念與公式#

• 門牌邏輯： MIPS 是 Byte-addressable。1 個 Word = 4 Bytes。
• 對齊限制 (Alignment)： Word 的地址必須是 4 的倍數。
• 陣列偏移公式： $\text{Effective Address} = \text{Base Register} + (\text{Index} \times \text{Element Size})$

實戰演練#

Q：int Arr[7]，其 Base Address 在 $s0 = 0x10008000。求 Arr[7] 的實際地址與 lw 指令。 Step-by-step：

1. $\text{Offset} = 7 \times 4 = 28$ (十進位)。
2. 將 28 轉為十六進位：$28 = 1 \times 16 + 12 \implies 0x1C$。
3. $\text{實際位址} = 0x10008000 + 0x1C = 0x1000801C$。
4. 指令：lw $t0, 28($s0)。

觀念與公式#

• lw (Load Word)：Memory $\rightarrow$ Register。
• sw (Store Word)：Register $\rightarrow$ Memory。
• 記憶口訣： lw 目的地在暫存器；sw 目的地在括號裡的記憶體。

實戰演練#

Q：翻譯 A[6] = B[3] + h; ($s0=A, s1=B, s2=h$) Step-by-step：

1. lw $t0, 12($s1) # 讀取 $B[3]$ ($3 \times 4 = 12$)
2. add $t0, $t0, $s2 # $B[3] + h$
3. sw $t0, 24($s0) # 寫回 $A[6]$ ($6 \times 4 = 24$)

觀念與公式#

• R-Format (暫存器型)： 用於 add, sub, and 等。 [op:6 | rs:5 | rt:5 | rd:5 | shamt:5 | funct:6]
• I-Format (立即值型)： 用於 addi, lw, sw, beq 等。 [op:6 | rs:5 | rt:5 | immediate:16]
• 暫存器編號： $t0–$t7 = 8–15，$s0–$s7 = 16–23。

實戰演練#

Q：將 sub $s1, $t2, $t0 轉為 Hex。($s1=17, t2=10, t0=8, op=0, funct=34$) Step-by-step：

1. op=0, rs=10, rt=8, rd=17, shamt=0, funct=34
2. 二進位：000000 01010 01000 10001 00000 100010
3. 合併：0000 0001 0100 1000 1000 1000 0010 0010
4. Hex：0x01488822

觀念與公式#

• 硬體設計： 分支指令使用「相對位址」以節省空間。
• 核心公式： $\text{Target Address} = (\text{PC} + 4) + (\text{Offset} \times 4)$
• 計算 Offset 公式： $\text{Offset} = \frac{\text{Target} - (\text{PC} + 4)}{4}$

實戰演練#

Q：bne $t0, $zero, Loop 位於 0x40，Loop 位於 0x20。求 Offset。 Step-by-step：

1. $\text{PC} = 0x40$，$\text{PC} + 4 = 0x44$。
2. $\text{位址差} = 0x20 - 0x44 = -0x24$ (即十進位 -36)。
3. $\text{Offset} = -36 / 4 = -9$。

觀念與公式#

• 反向邏輯： 為了跳過 code 塊，通常使用「相反的條件」來跳轉。

實戰演練#

Q：將 if (i != j) f = g + h; 優化。 A：

1
beq $s3, $s4, Exit  # 若 i == j (反向條件) 則跳過
2
add $s0, $s1, $s2   # f = g + h
3
Exit:

觀念與公式#

• jal (Jump and Link)：存下回家的路到 $ra 並跳轉。
• jr $ra (Jump Register)：讀取 $ra 飛回家。
• 暫存器約定： $a0–$a3 傳參數；$v0–$v1 傳回傳值。
• J-Format (跳躍型)：** 用於無條件長距離跳躍 j (Jump) 與 jal (Jump and Link)。 [op:6 | target address:26]

觀念與公式#

• Stack 特性： 往 低位址 (Low Address) 生長。
• Push (存檔)： addi $sp, $sp, -4 接著 sw。
• Pop (還原)： lw 接著 addi $sp, $sp, 4。

實戰演練 (遞迴/非葉函數)#

Q：翻譯 res = func(a); return res + b; (a=$a0, b=$a1) A：

1
addi $sp, $sp, -8   # 騰空間
2
sw   $ra, 4($sp)    # 存 $ra (必存，因為 jal 會蓋掉它)
3
sw   $a1, 0($sp)    # 存 $a1 (因呼叫函數可能會弄髒它)
4
jal  func
5
lw   $a1, 0($sp)    # 還原 b
6
lw   $ra, 4($sp)    # 還原回家地址
7
addi $sp, $sp, 8    # 歸還空間
8
add  $v0, $v0, $a1  # res + b
9
jr   $ra

觀念與公式#

• 兩步走： lui 載入高 16 位，ori 載入低 16 位。

實戰演練#

Q：載入 0x12345678。 A：

1. lui $s0, 0x1234 # $s0 = 0x12340000
2. ori $s0, $s0, 0x5678 # $s0 = 0x12345678

觀念與公式#

• 流程： $\text{C} \xrightarrow{\text{Compiler}} \text{ASM} \xrightarrow{\text{Assembler}} \text{Object} \xrightarrow{\text{Linker}} \text{Exec} \xrightarrow{\text{Loader}} \text{Memory}$
• Object Module 包含： Header, Text (Code), Data, Relocation Info, Symbol Table, Debug Info.

實戰演練#

Q：外部函數的名稱存放在哪？何時修正地址？ A： 名稱存放在 Symbol Table；由 Linker 在 Relocation 階段修正地址。

【解析】#

第一步：計算 $7 + 3$

• 二進位：$0111_2$ (7) + $0011_2$ (3)
• 運算過程：相加後得到 $1010_2$。
• 判定：正數加正數，符號位變成 1（負數，數值為 -6），發生溢位！
• 硬體檢驗：最高位 (MSB) 的 $C_{in} = 1$，$C_{out} = 0$。$1 \oplus 0 = 1$ (Overflow 成立)。

第二步：計算 $-4 - 5$

• 二進位：$1100_2$ (-4) + $1011_2$ (-5)
• 運算過程：相加得到 $(1)0111_2$。
• 判定：負數加負數，符號位變成 0（正數，數值為 7），發生溢位！
• 硬體檢驗：最高位 (MSB) 的 $C_{in} = 0$，$C_{out} = 1$。$0 \oplus 1 = 1$ (Overflow 成立)。

【解析】#

1. 第一階 ($C_1$)：$C_1 = g_0 + (p_0 \cdot C_0)$
2. 第二階 ($C_2$)：將 $C_1$ 帶入 $C_2 = g_1 + p_1 \cdot C_1$

• 展開得：$C_2 = g_1 + (p_1 \cdot g_0) + (p_1 \cdot p_0 \cdot C_0)$

3. 第三階 ($C_3$)：將 $C_2$ 帶入 $C_3 = g_2 + p_2 \cdot C_2$

• 展開得：$C_3 = g_2 + (p_2 \cdot g_1) + (p_2 \cdot p_1 \cdot g_0) + (p_2 \cdot p_1 \cdot p_0 \cdot C_0)$

物理意義：$C_3$ 會產生 1，代表要麼是在 Bit 2 產生進位 ($g_2$)；要麼是在 Bit 1 產生並由 Bit 2 傳遞 ($p_2 \cdot g_1$)；或者是更低階產生並一路暢通傳遞上來。所有因子都不依賴先前的 Carry 結果，可以直接從 A 與 B 的輸入訊號平行算出！

【解析】#

被乘數 $M = 0010_2$ (2)，$-M = 1110_2$ (-2)。 初始狀態：左半部補 0，右半部放乘數，最右方補一個隱藏位元 0 $\to$ 0000 1101 0。

1. Step 1：看末兩位 10 $\to$ 代表 1 的開始，執行減法 (加上 $-M$)。

• 左半部 0000 + 1110 = 1110 $\to$ Product 變為 1110 1101 0。
• 算術右移 1 bit $\to$ 1111 0110 1。

2. Step 2：看末兩位 01 $\to$ 代表 1 的結束，執行加法 (加上 $M$)。

• 左半部 1111 + 0010 = 0001 $\to$ Product 變為 0001 0110 1。
• 算術右移 1 bit $\to$ 0000 1011 0。

3. Step 3：看末兩位 10 $\to$ 執行減法 (加上 $-M$)。

• 左半部 0000 + 1110 = 1110 $\to$ Product 變為 1110 1011 0。
• 算術右移 1 bit $\to$ 1111 0101 1。

4. Step 4：看末兩位 11 $\to$ 不做事 (None)。

• 算術右移 1 bit $\to$ 1111 1010 1。

結論：結束循環，捨棄最後一個隱藏位元。最終答案前 8 bits 為 1111 1010，轉換為十進位即為 $-6$。完全正確！

【解析】#

初始狀態：Divisor = 0010，Remainder = 0000 0111。

1. Iteration 1:

• Remainder 左移 1 bit $\to$ 0000 1110。
• 左半部減去 Divisor (0000 - 0010 = 1110，小於 0) $\to$ 1110 1110。
• 發現小於 0：還原 (Restore) 加回 0010，變成 0000 1110，然後左移並將最低位置 0 (實際上是將 LSB 設為 0) $\to$ 0001 1100。

2. Iteration 2:

• 若減完 $\ge 0$，就不須還原，且把商的位元設為 1 (依此類推)。
• 最終 Remainder 的左半部是真餘數 0001 (1)，右半部是商數 0011 (3)。

【解析】#

1. Sign：負數，所以 $S = 1$。
2. 轉換為二進位科學記號：

• $0.75 \times 2 = 1.5$ (取 1)
• $0.5 \times 2 = 1.0$ (取 1)
• 科學記號表示法：$-0.11_2 \times 2^0 = -1.1_2 \times 2^{-1}$ (正規化，將 1 移到小數點前)

3. 計算 Exponent：

• 實際指數為 $-1$。加上 Bias 127：$E = -1 + 127 = 126$。
• 126 的二進位：0111 1110。

4. 計算 Fraction (Significand)：

• 取小數點後面的部分：1。補滿 23 bits：100 0000 0000 0000 0000 0000。

5. 組合：1 01111110 10000000000000000000000。

經典考題二 (進階)： 將無限循環小數 $1/3$ 轉換為單精度 IEEE 754 格式。

【解析】#

1. $1/3 = 0.333333_{10}$。不斷乘以 2 取整數部分，得到二進位小數為 $0.01010101..._2$。
2. 正規化：$0.010101... \times 2^0 = 1.010101... \times 2^{-2}$。
3. $S = 0$。
4. $E = -2 + 127 = 125_{10} = 0111 1101_2$。
5. Fraction = 0101 0101 0101 0101 0101 010 (截斷至 23 位)。

【解析】#

1. 對齊小數點 (Align binary points)： $-1 > -2$，所以要把較小的數字的指數變成 $-1$。 $-1.110_2 \times 2^{-2}$ 右移變成 $-0.111_2 \times 2^{-1}$。
2. 尾數相加 (Add mantissa)： $1.000_2 + (-0.111_2) = 0.001_2$。目前結果為 $0.001_2 \times 2^{-1}$。
3. 正規化 (Normalize)： 向左移 3 位，指數減 3：$1.000_2 \times 2^{-4}$。沒有 Over/Underflow。
4. 捨入 (Rounding)： $1.000_2 \times 2^{-4}$ 不需更改。此即十進位的 $0.0625$ ($0.5 - 0.4375 = 0.0625$)，正確。

【解析】#

• Step 1（核心觀念）：這在單週期架構下是完全允許且不會造成衝突的。
• Step 2（時序行為）：單週期架構採用的是邊緣觸發（Edge-triggered）機制。當一個時脈週期的上升緣到達時，暫存器 $R_1$ 內部原本穩定的舊資料會被讀出到輸出端線路上。接著，這個舊資料會通過外部的組合邏輯電路（如 ALU）進行運算，並在該時脈週期中持續往後傳遞，最後到達暫存器 $R_1$ 的輸入端。此時，輸入端的新資料只要在下一個時脈上升緣到來之前保持穩定，就會在下一個上升緣被鎖存（Write）進暫存器中。
• Step 3（結論）：由於讀出的是「舊值」，寫入的是「新值」，且寫入動作要等到週期末端的下一個時脈邊緣才會發生，因此在同一個時脈週期內，讀出後又寫回同一個暫存器並不會造成干擾或回授。

💡 補充變化考法 若考試改問「若是電平觸發（Level-sensitive）而不是邊緣觸發會發生什麼事？」 答案是：暫存器在整個高電平期間皆具備穿透性，只要時脈訊號一直維持在高電平，輸出與輸入就會產生不間斷的即時回授，導致訊號進入無法預測的震盪與數據破壞狀態。

【解析】#

• (A) 錯誤：讀取時如同組合邏輯行為，給定編號即輸出，不需要時脈邊緣觸發。
• (B) 正確：讀取是組合電路行為，寫入必須在時脈邊緣抵達且 Write Enable = 1 時才會發生。
• [C] 錯誤：擁有兩個 32-bit 的輸出埠（busA, busB）以及一個 32-bit 的輸入埠（busW）。
• (D) 錯誤：當 Write Enable = 0 時，暫存器內數值保持不變，輸出端依然輸出原本鎖存的內容，不會變成 0。
• 答案：選 (B)

💡 補充變化考法 考試常結合微架構圖問：「記憶體（Memory）的 Read 控制訊號在單週期中是否為必須？」 答案是：在理想單週期中，記憶體讀取被視為組合邏輯，傳入有效 Address 後 Data Out 隨後即有效，因此不需要讀取控制訊號（No need for read control）。

【解析】#

• Step 1（符號擴充的必要性）：MIPS 立即數欄位只有 16 位元，但 CPU 內部資料路徑與主記憶體定址皆為 32 位元。為了支援正向與負向的分支偏移植，必須透過符號擴充將 16 位元填滿至 32 位元，維持正負號實質意義。
• Step 2（左移 2 位的物理意義）：MIPS 架構採用字組對齊（Word Alignment），每條指令長度固定為 4 Bytes，因此記憶體起始地址最後兩個位元固定是 00。為了擴大跳躍範圍，立即數儲存的是「指令條數偏移量」。將其乘以 4（左移 2 位），就能還原為真實的位元組偏移量（Byte Offset），使跳躍能力擴大 4 倍。
• Step 3（與 PC 結合）：分支目標地址是相對於下一條指令的地址（$\text{PC}+4$）進行偏移計算。公式為：

$\text{Branch Target Address} = (\text{PC} + 4) + (\text{SignExt}(\text{imm16}) \times 4)$

💡 補充變化考法 若考試考全新的指令，例如 bne（不相等時跳躍），其資料路徑與 beq 完全相同，唯一差別在於控制邏輯中，判斷 PC 軌道多工器切換的條件由 ALU Zero = 1 變成了 ALU Zero = 0。

【解析】#

• Step 1（定位錯誤意義）：MemtoReg = 0 代表寫回暫存器檔案的 MUX 永久鎖定在「選擇 ALU 運算結果」通道。

• Step 2（逐一檢視指令）：

• R-type 指令：本就要求 MemtoReg = 0，故障值與期望值相符，正常執行。

• Store (sw)：不寫回暫存器，RegWrite = 0。MUX 切到哪都沒差，正常執行。

• Branch (beq)：同上，RegWrite = 0，正常執行。

• Load (lw)：正常需設定 MemtoReg = 1。卡在 0 會導致寫回暫存器的資料變成「ALU 算出的記憶體地址」，而非真實數據，因此發生錯誤。

• Step 3（結論）：

• 正常執行：R-type, sw, beq。

• 發生錯誤：lw。

💡 補充變化考法 如果是 RegWrite 發生 Stuck-at-0 錯誤呢？答案是所有需要修改暫存器內容的指令（R-type, lw）全部報銷，只有 sw 與 beq 能存活。這類 Stuck-at 題型是各大資工所必考！

【解析】#

• Step 1（最差時序路徑）： 代入 lw 路徑：Fetch $\rightarrow$ RegRead $\rightarrow$ MUX $\rightarrow$ ALU $\rightarrow$ D-Mem $\rightarrow$ MUX $\rightarrow$ RegWrite。

$T_c = 250\text{ ps} + 150\text{ ps} + 30\text{ ps} + 200\text{ ps} + 300\text{ ps} + 30\text{ ps} + 150\text{ ps}$

$T_c = 1110\text{ ps} = 1.11\text{ ns}$

最高主頻：

$f = \frac{1}{T_c} = \frac{1}{1.11 \times 10^{-9}\text{ s}} \approx 900.9\text{ MHz}$

• Step 2（add 指令時間分析）：

• add 實際路徑：Fetch (250 ps) $\rightarrow$ RegRead (150 ps) $\rightarrow$ MUX (30 ps) $\rightarrow$ ALU (200 ps) $\rightarrow$ MUX (30 ps) $\rightarrow$ RegWrite (150 ps)。

• 實際所需時間 = 810 ps。

• 被分配時間：強行分配 1110 ps。

• Step 3（缺點總結）： 這導致 add 指令在 810 ps 時就做完事情了，但在接下來的 300 ps 內，整個硬體電路只能處於閒置狀態，浪費晶片效能。

(1) 快取缺失三元模型 (3C Miss Model)#

快取缺失（Cache Miss）依其底層硬體成因，可精準分類為以下三種模型（常考於觀念情境辨析）：

• 強制性缺失 (Compulsory Miss / Cold-start Miss)：當程式剛啟動或首次存取某個記憶體區塊時，該資料從未進入過快取，因而必然發生的第一次缺失。
• 容量性缺失 (Capacity Miss)：當程式在某段時間內頻繁存取的工作集（Working Set）體積，大於快取的總容量時。即使快取採用完全相聯（Fully-Associative）完美擺放，資料仍會因空間不足被輪流踢出而導致缺失。
• 衝突性缺失 (Conflict Miss / Collision Miss)：專門發生在直接映射（Direct-Mapped）或組相聯（Set-Associative）快取中。當多個不同的記憶體位址因餘數映射公式，同時爭奪同一個快取組（Set），導致彼此瘋狂交替踢走對方，此時快取的其餘空間可能多數仍是空的。

(2) 寫入策略與缺失分配 (Write Strategy)#

當 CPU 執行寫入指令（如 sw）時，硬體必須權衡速度與資料一致性：

• 寫透策略 (Write-Through)：不論快取是否命中，資料同時且立刻寫入快取與主記憶體。缺點是每次寫入都要同步忍受慢速的 DRAM 延遲。

• 黃金搭檔：寫繞過 (No-Write Allocate)。當寫入缺失時，直接繞過快取去修改主記憶體，不把區塊搬上快取，省下頻寬。

• 寫回策略 (Write-Back)：寫入命中時，只將新資料更新到快取中，並將該列快取線（Cache Line）標記為 Dirty bit = 1（髒污位元），不立刻修改主記憶體。只有當這列資料未來被 LRU 演算法選中、準備被踢出（Evict）時，硬體才會檢查 Dirty bit 並將其整條寫回主記憶體。

• 黃金搭檔：寫分配 (Write Allocate)。當寫入缺失時，大費周章將該 Block 從主記憶體載入到快取，隨後再執行快取寫入。核心理念是利用時間局部性，打賭未來對該區塊的無數次讀寫都能在快取中以 1 cycle 爆發命中。

(3) 架構師的硬體權衡參數 (Cache Trade-offs)#

• 固定總容量，放大區塊大小 (Block Size $\uparrow$)：
• 強大的空間局部性使 Compulsory Miss 下降。
• 但根據公式： $\text{總格數 (Blocks)} = \frac{\text{Cache 總容量}}{\text{Block Size}}$

當總容量固定，Block Size 放大，快取內部的總格數（或總組數）反而會大幅縮水。這會造成嚴重的「沙發效能陷阱」，導致 Conflict Miss 劇烈上升。

• 固定總容量與區塊，提升相聯度 (Associativity $\uparrow$)：
• 擺放極度靈活，使得 Conflict Miss 顯著下降。
• 對 Capacity Miss 完全沒有影響（容量缺失只與 Cache 總容量大小有關）。
• 致命硬體代價：由於多個 Way 需要平行比對，硬體內部需要成倍增加比較器（Comparator），導致晶片面積增大、功耗與成本爆炸。同時，後面串接的大型多路複用器（MUX）會拉長電路延遲，造成 Hit Time（命中時間）變長。

題目一：3C Miss Model 情境微觀辨析（精準歸類）#

假設有一個 32 位元系統，內建一個容量為 $64\text{ KB}$、Block Size 為 $64\text{ Bytes}$ 的 2-way Set-Associative Cache。請判斷下列三種獨立發生的記憶體存取缺失，分別屬於 3C Miss 中的哪一種，並簡述其原因：

• (1) 電腦剛開機，CPU 執行第一行核心指令時發生的 Cache Miss。
• (2) 程式要處理一個大小為 $2\text{ MB}$ 的大型影像矩陣，由於陣列連續存取所需的空間遠大於 $64\text{ KB}$，導致在迴圈後段存取時，先前載入的資料早已被全部剔除而發生的 Miss（假設此時排除排擠問題）。
• (3) 某段迴圈在極短時間內，交替讀取主記憶體實體位址 0x00001000 與 0x00011000。經硬體計算發現，這兩個位址因為 Modulo 公式，剛好都會被映射到 Set 64。因為它們瘋狂交替踢走對方，導致這個迴圈每次存取都發生 Miss，但此時整個 Cache 其實還有超過 90% 的空間是空的。

【Step-by-step 詳細解析】

• (1) 答案：Compulsory Miss

• 解析：電腦剛開機執行第一行指令，該記憶體位址是生涯第一次被讀取，快取內為空（Valid bit = 0），此為典型的冷啟動缺失。

• (2) 答案：Capacity Miss

• 解析：工作集資料體積（$2\text{ MB}$）遠遠碾壓了快取的總容納極限（$64\text{ KB}$），即使快取設計得再完美也放不下，因容量耗盡被輪替踢出，故歸類為容量缺失。

• (3) 答案：Conflict Miss

• 解析：關鍵特徵在於「整個 Cache 還有 90% 的空間是空的」。這代表缺失絕非因為總容量不夠（非 Capacity），而是因為 0x00001000 與 0x00011000 這兩個特定的高頻存取位址，倒楣地映射到了同一個格子（Set 64），在局部發生了嚴重的排擠衝突。

題目二：Write Strategy 硬體運作流程#

現有一台處理器，其 L1 Data Cache 採用 Write-Back（寫回策略） 搭配 Write Allocate（寫分配），且替換演算法採用 LRU。

• (1) 當 CPU 執行一個 sw（寫入資料）指令且 Cache Hit 時，硬體內部會做出什麼動作？此時會立刻去修改 Main Memory 的資料嗎？
• (2) 承上題，如果此時不幸發生了 Read Miss（讀取缺失），且經 LRU 算過後，被選中要被踢出（Evict）的那一列 Cache Line 的 **Dirty bit 為 1**。請詳細寫出硬體此時必須依序執行的底層運存步驟。
• (3) 為什麼在業界設計中，Write-Through 通常固定搭配 No-Write Allocate，而 Write-Back 則固定搭配 Write Allocate？請從效能工程的角度解釋原因。

【Step-by-step 詳細解析】

• (1) 答案：

• 硬體動作：硬體會直接將新資料寫入到 L1 Data Cache 對應的欄位中，並**將該快取列的 Dirty bit 標記為 1**。

• 是否修改 Main Memory：絕對不會。這正是 Write-Back 的精髓，將慢速的記憶體寫入動作延遲到區塊被淘汰之時，以此節省寶貴的 CPU 時間。

• (2) 答案（標準硬體狀態鏈流動順序）：

1. 寫回髒污區塊 (Write Back)：快取控制器偵測到被 LRU 挑出的 Victim（犧牲者）區塊之 Dirty bit 為 1，代表其內容已被修改、與記憶體不一致。硬體會率先將此整條 Cache Block 寫回主記憶體（DRAM）對應的實體位址。
2. 載入全新區塊 (Fetch)：當髒污區塊清空後，快取控制器向主記憶體發出讀取請求，將 CPU 當前真正需要讀取的全新實體區塊完整搬運（Fetch）上來，填入該清空的位置。
3. 重設狀態標籤：將這一格的 **Dirty bit 清除為 0**（因為剛從記憶體搬上來，兩邊資料完全一致），並將 **Valid bit 設為 1**。
4. 交付資料：最後把目標資料透過內部匯流排完美交付給 CPU，完成本次讀取任務。

• (3) 答案：
• Write-Through + No-Write Allocate：因為 Write-Through 無論如何都必須同步將資料寫進主記憶體。既然在快取沒命中，最省時的做法就是直接寫去主記憶體（DRAM）即可，不需要大費周章再把整條區塊搬上快取，這能有效保護快取空間不被污染，並節省匯流排頻寬。
• Write-Back + Write Allocate：Write-Back 的核心目的是讓未來的讀寫都在超高速的快取中爆發命中。雖然這次 Miss 必須多花時間從主記憶體分配並載入區塊，但只要成功搬上來，接下來對這個區塊的連續無數次寫入就通通只要 1 cycle 就能在快取搞定。高回報率完全值得初次的搬運代價。

(1) 多階快取的階層式權衡 (Architect’s Goals)#

為了解決「處理器-記憶體效能鴻溝（Processor-Memory Performance Gap）」，現代架構設計了多層防線：

• L1 Cache（第一線戰場）：

• 核心目標：極致的快（Minimize Hit Time）。

• 設計特徵：緊貼 CPU 核心，容量極小（$16\text{ KB} \sim 64\text{ KB}$），相聯度極低（通常 2-way 或 Direct-Mapped），確保在 1 個 cycle 內做出回應。

• L2/L3 Cache（第二/三道防線）：

• 核心目標：極低的缺失率（Minimize Miss Rate），死命攔截住任何企圖外流到主記憶體的存取。

• 設計特徵：容量巨大（$256\text{ KB} \sim 8\text{ MB}+$），相聯度極高（8-way $\sim$ 32-way），雖然 Hit Time 稍慢（10~30 cycles），但比起去 Main Memory 等幾百個 cycles，依然是天壤之別。

(2) 雙層快取 AMAT 終極結算公式#

當引入 L2 快取後，平均記憶體存取時間（AMAT）展開為三層聯動公式：

$\text{AMAT} = \text{Hit Time}_{L1} + \text{Miss Rate}_{L1} \times \text{Miss Penalty}_{L1}$

而 L1 的 Miss Penalty，實質上就是去 L2 尋找資料的平均時間：

$\text{Miss Penalty}_{L1} = \text{Hit Time}_{L2} + \text{Local Miss Rate}_{L2} \times \text{Miss Penalty}_{L2}$

• 【🚨 缺失率名詞大陷阱】：

1. Local Miss Rate（局部缺失率）： $\text{Local Miss Rate}_{L2} = \frac{\text{L2 Miss 總數}}{\text{進入 L2 的存取總數 (即 L1 Miss 數)}}$

一般計組題目若無特別說明，「L2 快取缺失率」預設皆為此項。 2. Global Miss Rate（全域缺失率）： $\text{Global Miss Rate}_{L2} = \frac{\text{L2 Miss 總數}}{\text{CPU 發出的總存取數}} = \text{Miss Rate}_{L1} \times \text{Local Miss Rate}_{L2}$

(3) 主記憶體（DRAM）頻寬優化策略#

當快取全數失守、必須去 DRAM 搬運一整條 Block（假設大小為 $N$ 個 Words）時，有三種硬體組織架構：

• 單字寬度組織 (One-word-wide)：記憶體與匯流排寬度皆為 $1\text{ Word}$。每次搬運都必須獨立重複執行「送位址 + DRAM啟動 + 傳輸 1 Word」的完整流程，速度最慢。

• 加寬組織 (Wide Memory)：直接加寬記憶體與匯流排。路多寬，資料就能併排跑多大。可以一次送出位址、一次讀取並同時打包傳輸一整條 Block。

• $\text{Total Miss Penalty} = \text{傳送位址時間} + \text{DRAM 存取時間} + \text{1 次打包傳輸時間}$

• 交錯式儲存組織 (Interleaved Memory)：【期末考最愛考！】 內部拆成多個獨立的 Memory Banks。可以平行（同時）啟動多個 Bank 讀取，等一次 DRAM 時間，所有資料就在門口準備好了。但為了省錢，與主機連接的資料匯流排寬度維持窄小的 $1\text{ Word}$，因此傳輸時必須排成一縱隊依序過馬路。

• $\text{Total Miss Penalty} = \text{傳送位址時間} + \text{DRAM 存取時間} + (N \times \text{單字傳輸時間})$

題目一：雙層快取（L1/L2）AMAT 與 CPI 聯動地獄計算題#

現有一台高時脈處理器，運作時脈為 $2.5\text{ GHz}$（意即 $1\text{ cycle} = 0.4\text{ ns}$），在理想快取狀態下的 $\text{Base CPI} = 2.0$。所有指令中，有 $40\%$ 的指令是資料存取指令（Load 或 Store）。系統配備了兩級快取，參數如下：

• L1 I-Cache：$\text{Miss Rate} = 2\%$，$\text{Hit Time} = 1\text{ cycle}$。
• L1 D-Cache：$\text{Miss Rate} = 5\%$，$\text{Hit Time} = 1\text{ cycle}$。
• L2 Unified Cache：$\text{Local Miss Rate} = 20\%$，$\text{Hit Time} = 8\text{ cycles}$。
• 主記憶體（Main Memory）：存取一次需要固定的時間 $60\text{ ns}$。

請詳細解答下列問題：

• (1) 請問主記憶體存取一次，對這台 CPU 而言是多少個 Penalty Cycles？
• (2) 請問 L2 D-Cache 的 Global Miss Rate（全域缺失率）是多少？
• (3) 當 L1 Data Cache 發生 Miss 時，平均需要花多少個 Cycles（L1 Miss Penalty）才能從下層系統（L2 + Memory）取回資料？
• (4) 這台處理器在執行該程式時，最終實際的總 CPI 是多少？

【Step-by-step 詳細解析】

• (1) 解答：150 cycles

• 計算： $\text{Memory Penalty Cycles} = \frac{\text{記憶體固定延遲}}{\text{CPU 週期時間}} = \frac{60\text{ ns}}{0.4\text{ ns}} = 150\text{ cycles}$

• (2) 解答：1% (或 0.01)

• 計算： $\text{Global Miss Rate}_{L2} = \text{L1 D-Cache Miss Rate} \times \text{L2 Local Miss Rate} = 5\% \times 20\% = 0.01 = 1\%$

• (3) 解答：38 cycles

• 計算：帶入雙層 Penalty 公式。當 L1 缺失時，一定要先花 $8\text{ cycles}$ 檢查 L2。如果 L2 沒中（機率 $20\%$），才需要外流去 Main Memory 等 $150\text{ cycles}$：

$\text{L1 Data Miss Penalty} = \text{Hit Time}_{L2} + \text{Local Miss Rate}_{L2} \times \text{Mem Penalty} = 8 + 0.20 \times 150 = 8 + 30 = 38\text{ cycles}$

• (4) 解答：3.52
• 計算：由於 L2 是統一快取（Unified），不論是指令（I）還是資料（D）只要漏出 L1，去 L2 + Memory 撈資料的懲罰都是相同的 $38\text{ cycles}$。
• 計算 Instruction Stall： $\text{I-Stall} = 1 \times 2\% \text{ (I-Cache Miss Rate)} \times 38 = 0.76\text{ cycles}$

（每條指令都有 1 次抓取指令的動作）

• 計算 Data Stall： $\text{D-Stall} = 40\% \text{ (Data 指令佔比)} \times 5\% \text{ (D-Cache Miss Rate)} \times 38 = 0.76\text{ cycles}$

• 結算實際總 CPI： $\text{Total CPI} = \text{Base CPI} + \text{I-Stall} + \text{D-Stall} = 2.0 + 0.76 + 0.76 = 3.52$

題目二：主記憶體組織（Memory Organizations）與週期計算大題#

假設目前系統要從 DRAM 搬回一個大小為 4 個 Words 的 Cache Block。已知主記憶體與匯流排的硬體延遲參數如下：

• 傳送位址時間：固定花費 $1\text{ cycle}$。
• DRAM 存取時間（Latency）：每啟動一次讀取，DRAM 內部晶片需要花費 $30\text{ cycles}$ 才能把資料準備好。
• 資料傳輸時間：匯流排每傳送 $1\text{ Word}$ 的資料，需要花費 $2\text{ cycles}$。

請分別計算在以下三種不同的主記憶體組織架構下，CPU 發生一次 Miss 所需付出的總缺失懲罰（Total Miss Penalty，單位為 cycles）：

• 架構 (A)：單字寬度儲存組織（One-word-wide Memory Organization）
• 架構 (B)：加寬儲存組織（Wide Memory Organization，寬度加寬為 4 Words）
• 架構 (C)：四路交錯式儲存組織（4-bank Interleaved Memory Organization，匯流排維持 1 Word 寬）

【Step-by-step 詳細解析】

• 架構 (A) 解答：132 cycles

• 解析：因為每次只能定址傳輸 1 個 Word，整套動作必須重複 4 次。

• $\text{單次循環} = 1\text{ (傳位址)} + 30\text{ (DRAM存取)} + 2\text{ (傳輸)} = 33\text{ cycles}$

• $\text{總時間} = 33 \times 4\text{ (個Words)} = 132\text{ cycles}$

• 架構 (B) 解答：33 cycles

• 解析：路加寬了 4 倍，記憶體一次吐出 4 個 Words，超寬的匯流排還能把這 4 個 Words 綁成一大捆，在「1 次傳輸時間內（即 2 cycles）」一口氣通通運回 CPU。

• $\text{總時間} = 1\text{ (傳位址)} + 30\text{ (DRAM存取)} + 2\text{ (超寬頻一次傳完)} = 33\text{ cycles}$

• 架構 (C) 解答：39 cycles

• 解析：記憶體內部拆成 4 個 Banks，所以可以同時平行啟動 DRAM 存取，我們只需要等 1 次 $30\text{ cycles}$，4 個 Words 就都在各自的 Bank 門口準備好了。但由於匯流排寬度維持窄小的 1 Word，這 4 個 Words 沒辦法並排跑，必須排成一縱隊，一個接一個傳過馬路（傳輸時間需累加）。

• $\text{總時間} = 1\text{ (傳位址)} + 30\text{ (4個Bank平行存取)} + [4\text{ (個Words)} \times 2\text{ (傳輸)}] = 1 + 30 + 8 = 39\text{ cycles}$

(1) 虛擬記憶體的終極定位 (The Illusion)#

虛擬記憶體是硬體與作業系統（OS）聯手打造的宏大魔術。它為每個獨立的進程（Process）提供了一個「私有、連續、從零開始」的虛擬位址空間（Virtual Address Space）。此時，主記憶體（DRAM）本質上變成了次級儲存裝置（硬碟/SSD）的「快取（Cache）」。

(2) 快取 vs 虛擬記憶體之名詞對照表#

為了讓觀念無縫平移，架構師將名詞做了一對一的對照：

(3) 由「恐怖懲罰」逼出的四項架構設計抉擇#

一旦發生 Page Fault，CPU 必須去慢速的硬碟（Disk/SSD）搬資料，這會付出高達數百萬個時脈週期的極致懲罰。為了死命降低 Page Fault 的機率，虛擬記憶體做出了與 Cache 截然不同的設計：

1. 分頁體積做得很巨（Page Size 大）：通常是 4KB 甚至更大。透過極強的空間局部性，攤提每次啟動硬碟讀取的高昂時間。
2. 採用全關聯式擺放 (Fully Associative)：任何虛擬分頁都可以自由存放到實體記憶體的任何角落，這樣能使用最靈活的演算法（如 LRU）把 Page Fault 的機率壓到最低。
3. 遺失由軟體（OS Handler）全權處理：既然 Page Fault 要等數百萬 cycles，硬體花十幾個 cycle 呼叫 OS 軟體根本無傷大雅。OS 會在此時進行進程上下文切換（Context Switch），把 CPU 讓給別的程式使用，免得處理器原地白白發呆。
4. 強制使用寫回策略 (Write-Back)：每次寫入都要同步改硬碟（Write-Through）會直接卡死系統。硬體只有當分頁要被踢出實體記憶體時，才檢查 Dirty bit 寫回硬碟。

(4) 位址翻譯與分頁表 (Address Translation)#

為了解決 Fully Associative 找不到資料的定位問題，OS 在 DRAM 中建立了一個索引地圖，稱為分頁表（Page Table）。 CPU 發出的虛擬位址（Virtual Address, VA）會被拆成兩部分：

• Virtual Page Number (VPN，虛擬分頁編號)：作為 Page Table 的陣列索引（Index）。
• Page Offset (分頁偏移量)：代表資料在該分頁內的確切位置（不參與翻譯，直接照抄）。

透過 VPN 索引查表後，若該條目（Page Table Entry, PTE）的 Valid bit 為 1，代表分頁待在實體記憶體中，此時會吐出 Physical Page Number (PPN，實體分頁編號)，並與 Page Offset 拼接成實體位址（Physical Address, PA）；若 Valid bit 為 0，則代表觸發 Page Fault。

(5) 分頁表拆分核心公式#

$\text{Page Offset 位元數} = \log_2(\text{Page Size 單位為 Bytes})$

$\text{VPN 位元數} = \text{虛擬位址總位元數 (VA)} - \text{Page Offset 位元數}$

$\text{分頁表總條目數 (PTEs)} = 2^{\text{VPN 位元數}}$

題目一：虛擬記憶體軟硬體處理機制辨析#

為什麼處理 Cache Miss 需要「純硬體線路（Hardware）」控制，而處理 Page Fault 卻可以容忍跳躍到作業系統的「軟體（Software OS Handler）」來處理？

【Step-by-step 詳細解析】

• Cache Miss 的情境：快取缺失的懲罰非常低（通常僅有幾十個 cycles），如果此時跳入作業系統執行軟體中斷處理，光是保護暫存器現場（Context Overhead）就要花費數百個 cycles，完全是因小失大。因此，Cache Miss 必須用純硬體線路以極速完成。
• Page Fault 的情境：分頁錯誤去磁碟讀取資料的懲罰高達數百萬個 cycles。與這段漫長的等待時間相比，OS 軟體中斷處理所帶來的幾百個 cycle 開銷根本微不足道。容忍跳入軟體，能讓 OS 有機會執行 Context Switch 切換到其他進程工作，大幅拉高 CPU 的整體整體吞吐量（Throughput）。

題目二：分頁位址拆分與大小結算#

假設某電腦系統採用虛擬記憶體架構，虛擬位址（VA）為 32 位元，實體位址（PA）為 30 位元，每個 Page 的大小為 8KB。請精準計算出：

• (a) Page Offset 需要多少位元（bits）？
• (b) Virtual Page Number (VPN) 有多少位元？
• (c) Page Table 中總共包含多少個 Page Table Entries (PTEs)？

【Step-by-step 詳細解析】

• (a) 解答：13 bits
• 計算：先將 Page Size 換算為 2 的次方： $8\text{ KB} = 8 \times 1024\text{ Bytes} = 8192\text{ Bytes} = 2^{13}\text{ Bytes}$

因此，需要 $13\text{ bits}$ 的 Page Offset 來對分頁內的每個 Byte 進行定址。

• (b) 解答：19 bits
• 計算：虛擬位址由 VPN 與 Page Offset 組成：

$\text{VPN Bits} = \text{VA Bits} - \text{Page Offset Bits} = 32 - 13 = 19\text{ bits}$

• (c) 解答：$2^{19}$ 個 (或 524,288 個)
• 計算：分頁表必須涵蓋所有的虛擬分頁編號可能性：

$\text{PTE 總數} = 2^{\text{VPN Bits}} = 2^{19}\text{ 個條目}$

(1) 救速神器：TLB (Translation Lookaside Buffer)#

由於 Page Table 存放在慢速的 DRAM 中，導致 CPU 每次想拿一個資料，都必須先去 DRAM 讀一次 Page Table 翻譯，再讀一次實體位址，存取時間直接變為兩倍。 為了消除這個致命缺點，架構師在 CPU 內部的 MMU（記憶體管理單元）中建立了一個專門用來快取「分頁表條目（PTE）」的超高速小快取，稱為 TLB。CPU 翻譯位址時會先問 TLB，若 TLB Hit，只需 0.5 $\sim$ 1 cycle 就能瞬間拿到實體位址（PA）。

(2) 四合一系統聯動狀態之「可能與不可能」矩陣#

當 TLB、Page Table、Cache、DRAM 全數交織在一起時，期末考最常考的便是判斷某種硬體組合是否存在矛盾：

題目一：終極四合一聯動追蹤大題#

假設某系統同時配備了 TLB、Page Table 與 Cache。現在 CPU 發出了一個記憶體讀取請求，但很不幸地，這個請求在硬體中依序發生了：TLB Miss $\rightarrow$ Page Table Hit $\rightarrow$ Cache Miss。請詳細寫出底層硬體與系統接下來必須依序執行的「4 個核心步驟」。

【Step-by-step 詳細解析（標準晶片規範書規範寫法）】

• Step 1：去 DRAM 走訪分頁表（修補地圖）

• 由於 TLB Miss，MMU 無法在第一時間完成翻譯。硬體被迫手持虛擬分頁編號（VPN）為索引，走訪位於 DRAM 中的 Page Table。因為 Page Table Hit（Valid bit = 1），硬體順利讀出對應的實體分頁編號（PPN）。

• Step 2：組裝並更新地圖（更新 TLB）

• MMU 將讀出的 PPN 與原本的 Page Offset 完美拼接，產生最終的實體位址（PA）。同時，為了確保下一次存取不用再跑去遙遠的 DRAM 查表，硬體會將這筆新翻譯好的對應關係立刻寫入（更新）TLB。

• Step 3：持實體位址查 Cache（搬移 Block）

• 硬體拿著剛出爐的實體位址（PA）去查 Cache。然而不幸發生 Cache Miss。此時快取控制器被迫再次啟動主記憶體（DRAM），將包含該目標資料的一整個實體區塊（Cache Block）從 DRAM 搬運（Fetch）上來，載入並更新到 Cache 中。

• Step 4：快取命中，交付 CPU（完美收工）

• 當資料成功入駐 Cache 後，CPU 再次存取該位址時便會觸發 Cache Hit，快取立刻將 CPU 真正想要的那個 Word 資料透過內部匯流排交付給暫存器，順利恢復指令的執行！