107 專利師高等考試 專利師(選試專業日文及計算機結構) 計算機結構 考古題詳解

核心觀念

本題評量計算機架構中兩大經典設計哲學——複雜指令集計算機（CISC）​與精簡指令集計算機（RISC）​的核心架構特徵及其權衡（Trade-off）。

理解兩者架構差異的理論基礎為處理器效能基本方程式（Iron Law of Processor Performance）： $\text{CPU Execution Time} = \text{Instruction Count (IC)} \times \text{CPI} \times \text{Clock Cycle Time}$

1. CISC 的設計哲學：源於 1970 年代記憶體昂貴且容量小、編譯技術尚不成熟的背景。其核心策略是降低指令數（Instruction Count, IC）​與縮小高階語言與機器語言之間的語意差距（Semantic Gap），提供功能強大、可直接操作記憶體運算元的複合指令。
2. RISC 的設計哲學：源於 1980 年代編譯技術躍進與微處理器技術成熟。其核心策略是降低每指令週期數（Cycles Per Instruction, CPI）​與縮短時脈週期（Clock Cycle Time），藉由精簡指令集、固定格式與載入／儲存（Load/Store）架構，使硬體高度簡化以利於深度管線化（Pipelining）運行。

解題方法

本題為國家考試標準的 4 小題申論題（每小題各 5 分，共 20 分）。 解題切入點採用「架構特徵 $\rightarrow$ 對硬體設計者／軟體使用者之影響」的因果對應法：

1. 第 (一)、(二) 小題（CISC）：挑選最能彰顯 CISC 本質的「高程式碼密度（高指令功能豐富度）」與「微程式化語意支持／向下相容性」，並分別從硬體匯流排頻寬、儲存成本、編譯器負擔等維度條列益處。
2. 第 (三)、(四) 小題（RISC）：挑選 RISC 最關鍵的「固定長度與簡化指令格式」與「載入／儲存架構（Load/Store Architecture）」，並分別從解碼電路成本、管線化效率、時脈頻率提升及編譯器暫存器配置最佳化等維度條列益處。

選項分析

本題為申論問答題，非選擇題，故無個別選項分析。

解題技巧與常見陷阱

1. 對稱性條列：題目要求列出「二項優良特性」，且每項特性需列出「至少二項益處」。答題時務必標註層級，嚴格以「特性一 $\rightarrow$ 益處 1、益處 2」、「特性二 $\rightarrow$ 益處 1、益處 2」架構書寫，使閱卷委員一目了然。
2. 避免空洞陳述：切忌使用「速度較快」、「執行較好」等含糊字眼。必須指明技術機制，例如「減少指令擷取對記憶體頻寬的耗費」、「簡化硬體解碼電路並縮短關鍵路徑（Critical Path）」。
3. 區分目標對象：題目要求回答對「設計者」或「使用者」的益處；「設計者」涵蓋硬體邏輯設計師、系統架構師與編譯器工程師，「使用者」涵蓋軟體開發人員、終端系統維護者與使用者。作答時清楚標示受惠主體，可顯著提升答案的專業度。

【答案】

(一) 複雜指令集計算機（CISC）的主要優良特性（任舉二項）

1. 高程式碼密度（High Code Density）與單一指令功能強大： CISC 提供多樣化且長度可變的複雜指令，支援豐富的定址模式（Addressing Modes），單一指令即可完成「自記憶體載入資料、執行算術邏輯運算、並寫回記憶體」的複合操作。
2. 較小的語意差距（Narrow Semantic Gap）與強大的向後相容性（Backward Compatibility）：

核心觀念

本題評量處理器架構中管道化（Pipelining）​與未管道化（Non-pipelined）​系統的效能評估及加速比（Speedup）計算，核心觀念包含：

1. 管道時脈週期（Clock Cycle Time, $\tau$）： 在理想均勻切分的 $k$ 階管道中，若單一指令通過所有階段的總延遲為 $T_{\text{latency}}$，則各階時脈週期為： $\tau = \frac{T_{\text{latency}}}{k}$
2. 有限指令數之執行時間與加速比： 執行 $n$ 道指令時：

• 未管道化處理器總時間：$T_{\text{unpipe}} = n \times T_{\text{unpipe\_single}}$
• $k$ 階管道處理器總時間（無危障）：$T_{\text{pipe}} = (k + n - 1) \times \tau$
• 加速比公式： $S = \frac{T_{\text{unpipe}}}{T_{\text{pipe}}}$

3. 無限指令數之極限加速比： 當指令數 $n \to \infty$ 時，填滿管道的 $k-1$ 週期開銷可忽略，平均每指令時脈週期數 $\text{CPI} \to 1$： $S_{\text{ideal}} = \lim_{n \to \infty} \frac{T_{\text{unpipe}}}{T_{\text{pipe}}} = \frac{T_{\text{unpipe\_single}}}{\tau}$
4. 管道危障（Pipeline Hazards）對效能之影響： 當發生結構、資料或控制危障導致管線停頓（Stall）時，每指令平均耗費週期數增加，加權平均 $\text{CPI}_{\text{avg}}$ 為各類指令占比與其耗費週期的期望值： $\text{CPI}_{\text{avg}} = \sum (P_i \times \text{CPI}_i)$ 在指令數趨近無限時，平均每道指令執行時間為 $\text{CPI}_{\text{avg}} \times \tau$。

解題方法

基本參數整理

• 未管道化處理器單一指令執行時間：$T_{\text{unpipe\_single}} = 0.8\ \mathrm{ns}$
• 管道階數：$k = 5$ 階
• 指令通過五個管道階所需總時間：$1.0\ \mathrm{ns}$
• 管道化時脈週期： $\tau = \frac{1.0\ \mathrm{ns}}{5} = 0.2\ \mathrm{ns}$

(一) 計算執行 1、5、10、100 道指令時之加速性

執行 $n$ 道指令所需時間：

• 未管道化總時間：$T_{\text{unpipe}}(n) = n \times 0.8\ \mathrm{ns}$
• 5 階管道化總時間：$T_{\text{pipe}}(n) = (5 + n - 1) \times 0.2\ \mathrm{ns} = (n + 4) \times 0.2\ \mathrm{ns}$

加速比公式： $S(n) = \frac{T_{\text{unpipe}}(n)}{T_{\text{pipe}}(n)} = \frac{n \times 0.8}{(n + 4) \times 0.2} = \frac{4n}{n + 4}$

分別代入 $n = 1, 5, 10, 100$：

1. $n = 1$ 道指令： $S(1) = \frac{4 \times 1}{1 + 4} = \frac{4}{5} = 0.8\text{ 倍}$ （此時未管道化耗時 $0.8\ \mathrm{ns}$，管道化耗時 $1.0\ \mathrm{ns}$，加速比為 $0.8$ 倍）

2. $n = 5$ 道指令： $S(5) = \frac{4 \times 5}{5 + 4} = \frac{20}{9} \approx 2.22\text{ 倍}$

3. $n = 10$ 道指令： $S(10) = \frac{4 \times 10}{10 + 4} = \frac{40}{14} = \frac{20}{7} \approx 2.86\text{ 倍}$

4. $n = 100$ 道指令： $S(100) = \frac{4 \times 100}{100 + 4} = \frac{400}{104} = \frac{50}{13} \approx 3.85\text{ 倍}$

(二) 計算理想情況下的加速性

核心觀念

本題評量數位邏輯與計算機結構中算術邏輯單元（ALU）​之基本設計核心，涵蓋三大重點：

1. 全加器（Full Adder, FA）之功能與真值表：全加器為組合邏輯電路的基本單元，能處理本位之被加數、加數以及低位進位，並輸出本位和與向高位的進位。
2. 加減法器之整合設計（2 的補數運算）：利用 2 的補數原理，減法 $A - B$ 可轉換為加法 $A + (-B) = A + \overline{B} + 1$。透過互斥或閘（XOR Gate）的「可控反相」特性搭配最低位進位輸入 $C_0$ 的設定，僅需單一加法器即可同時實現加法與減法功能。
3. 運算狀態旗標（Condition Flags）之邏輯推導：在算術運算中，處理器狀態暫存器常見的四個條件碼旗標為 $N$（負值）、$Z$（零值）、$V$（溢位）、$C$（進位／借位），需掌握各旗標於 2 的補數及無符號數系統下的布林判斷邏輯。

解題方法

(一) 全加器的定義與真值表

1. 全加器定義： 全加器（Full Adder）是一種用來執行二進位加法的組合邏輯電路。它具備 3 個 1 位元的二進位輸入：被加數位元 $A_i$、加數位元 $B_i$ 以及來自相鄰低位的進位輸入 $C_i$；產生 2 個 1 位元的二進位輸出：本位和（Sum）$S_i$ 與向相鄰高位的進位輸出（Carry-out）$C_{i+1}$。 其邏輯運算式為： $S_i = A_i \oplus B_i \oplus C_i$ $C_{i+1} = A_i B_i + C_i(A_i \oplus B_i) = A_i B_i + A_i C_i + B_i C_i$

2. 真值表（Truth Table）：

(二) 修改加法器為加減法器

1. 設計原理：

• 2 的補數算術中，減法可化為加法：$A - B = A + (-B) = A + (\overline{B} + 1)$。
• 利用互斥或閘（XOR）的控制特性：
• 當控制端為 0 時：$B_i \oplus 0 = B_i$（信號不變）。
• 當控制端為 1 時：$B_i \oplus 1 = \overline{B_i}$（信號反相，取 1 的補數）。
• 利用最低位進位輸入 $C_0$ 加 1 完成 2 的補數取負運算。

2. 電路修改步驟：

• 加數輸入端改造：在四個全加器的加數輸入端前各串接一個 2 輸入的 XOR 閘。每個 XOR 閘的一個輸入端接控制訊號 $OP$，另一個輸入端分別接 $B_0, B_1, B_2, B_3$。傳入各全加器 $B$ 端的訊號變為 $B_i' = B_i \oplus OP$。
• 進位輸入端設定：將最低位全加器的進位輸入端 $C_0$ 直接連接至控制訊號 $OP$，即 $C_0 = OP$。
• 工作模式驗證：
• 當 $OP = 0$（加法）：$B_i' = B_i \oplus 0 = B_i$ 且 $C_0 = 0$，電路執行 $A + B + 0 = A + B$。
• 當 $OP = 1$（減法）：$B_i' = B_i \oplus 1 = \overline{B_i}$ 且 $C_0 = 1$，電路執行 $A + \overline{B} + 1 = A - B$。

(三) 四個運算旗標的布林式推導

令修改後的加減法器各級加數輸入為 $B_i' = B_i \oplus OP$，輸出和為 $S_3, S_2, S_1, S_0$，進位鏈為 $C_1, C_2, C_3, C_4$。

1. 負值旗標（Negative Flag, $N$）：

• 在 2 的補數表示法中，最高有效位元（MSB）直接代表數值的正負號（0 為正、1 為負）。
• 本 4 位元運算結果之符號位元為 $S_3$。
• 布林式： $N = S_3$

2. 零旗標（Zero Flag, $Z$）：

• 當且僅當所有運算結果位元 $S_3, S_2, S_1, S_0$ 同時為 0 時，$Z$ 旗標設定為 1。
• 採用 NOR 邏輯閘實現。
• 布林式： $Z = \overline{S_3 + S_2 + S_1 + S_0} = \overline{S_3} \cdot \overline{S_2} \cdot \overline{S_1} \cdot \overline{S_0}$

3. 滿溢旗標（Overflow Flag, $V$）：

• 溢位僅發生於有符號數（Signed）運算，當結果超出 4 位元 2 的補數表示範圍（$-8 \sim +7$）時成立。
• 最直接且標準的硬體偵測方式為比較最高位的進位輸入 $C_3$ 與進位輸出 $C_4$。兩者不相等時即代表溢位： $V = C_4 \oplus C_3$

核心觀念

本題考查計算機結構中精簡指令集計算機（RISC）之核心設計原則如何支援典型五階管線（Classic 5-Stage Pipeline）​的高效運作。

管線化技術的核心目標在於讓多個指令重疊執行，理想狀態下達到每個時脈週期完成一個指令（$\text{CPI} = 1$）。為達成此目標，各管線階（Pipeline Stage）的延遲必須盡可能均勻，且硬體控制邏輯必須極簡化。典型的五個階段依序為：

1. 指令擷取（Instruction Fetch, IF）
2. 指令解碼／暫存器讀取（Instruction Decode / Register Fetch, ID）
3. 執行／有效位址計算（Execute / Address Calculation, EX）
4. 記憶體存取（Memory Access, MEM）
5. 結果寫回（Write Back, WB）

RISC 針對傳統 CISC（複雜指令集計算機）的缺點進行革新，透過「指令長度固定」、「格式規律」、「暫存器-暫存器運算導向」與「Load/Store 架構」等特性，精準消除各階段的結構危害（Structural Hazard）與控制複雜度。

解題方法

本題評分重點在於能否將 RISC 的具體架構特徵 與 特定管線階段的硬體操作機制 進行因果對應，並說明其帶來的具體效能或電路簡化效益。解題切入點如下：

• IF 階：硬體在不知道指令內容前，最需要知道「下一個指令在哪裡」與「該讀取多少位元組」。
• ID 階：硬體需要同步完成「解碼控制訊號」與「抓取運算元（暫存器）」，欄位規律性是關鍵。
• EX 階：運算單元（ALU）必須在單一時脈週期內完成運算，指令操作必須單純且操作數來源一致。
• MEM 階：記憶體存取延遲長，必須限制能存取記憶體的指令型態與定址模式。
• WB 階：必須以最少的寫入埠（Write Ports）與最單純的資料路徑將結果存回。

各小題詳解與分析

(一) 有利於指令擷取（IF）者

• 最主要特性：固定長度指令（Fixed-Length Instructions）
• 必要說明： RISC 架構中所有指令均為相同的固定長度（例如 32 位元）。此特性為 IF 階帶來兩大關鍵優勢：

1. 下一指令位址預測簡化：程式計數器（Program Counter, PC）不需等待指令解碼，即可在 IF 階直接並行計算下一條依序執行的指令位址（例如以加法器計算 $PC \leftarrow PC + 4$），使管線能夠順暢連續擷取，完全避免因變動長度（Variable-length）導致必須等待前一指令長度解析完畢才能抓取下一指令的停頓（Stall）。
2. 記憶體對齊與單次存取：所有指令在記憶體中均依字組（Word）邊界對齊存放，處理器在單一時脈週期內即可透過指令快取（I-Cache）完整擷取一條指令，絕不會發生跨快取行（Cache Line）或跨頁而需多次擷取的結構瓶頸。

(二) 有利於指令解碼（ID）者

• 最主要特性：規律且固定的指令格式與暫存器欄位（Regular Instruction Formats with Fixed Register Specifiers）
• 必要說明： RISC 的指令格式種類極少，且來源暫存器（Source Registers，如 $rs, rt$）的位元位置在所有指令格式中均保持固定（例如固定出現在指令的特定幾個位元區段）：

1. 並行讀取暫存器檔案：處理器在硬體電路剛接收到指令的同時，無需等待運算碼（Opcode）解碼完成，即可直接以指令固定位元區段作為索引，並行存取暫存器檔案（Register File）讀出運算元，大幅縮短關鍵路徑（Critical Path）延遲。
2. 解碼控制邏輯極簡：由於欄位對稱規律，控制單元僅需簡單的組合邏輯電路即可產生各階控制訊號，免去 CISC 所需的微程式碼（Microcode）唯讀記憶體解碼，可在單一週期內輕鬆完成解碼。

(三) 有利於執行（EX）者

• 最主要特性：僅限暫存器-暫存器運算與簡易的算術邏輯操作（Register-Register ALU Operations）
• 必要說明： RISC 的運算指令其所有輸入運算元皆來自暫存器，且運算操作設計簡單（均為基本算術或邏輯位移）：

核心觀念

本題考查計算機結構中虛擬記憶體（Virtual Memory）​之分頁機制（Paging）與位址轉譯（Address Translation）。核心概念與公式如下：

1. 虛擬位址結構（Virtual Address, VA）：

• 虛擬位址總位元數 $n$ 決定虛擬位址空間大小為 $2^n\ \mathrm{Bytes}$。
• 虛擬位址分割為兩部分：虛擬頁號（Virtual Page Number, VPN） 與 頁內位移（Page Offset）。
• 若頁（Page）大小為 $S = 2^p\ \mathrm{Bytes}$，則位移占 $p$ 個位元，$\mathrm{VPN}$ 占 $n - p$ 個位元。
• 頁表項次數（Number of Page Table Entries, PTEs）等於虛擬頁的總數，即 $2^{n - p}$ 個。

2. 實體位址結構（Physical Address, PA）：

• 主記憶體（實體記憶體）大小為 $M = 2^m\ \mathrm{Bytes}$，位元組定址下實體位址長度為 $m$ 個位元。
• 實體位址分割為：實體頁框號（Physical Frame Number, PFN） 與 頁內位移（Page Offset）。
• 頁框（Frame）大小必等於分頁大小（$2^p\ \mathrm{Bytes}$），位移同樣占 $p$ 個位元。
• 標示頁框位置所需的位元數即為 $\mathrm{PFN}$ 之長度，等於 $m - p$ 個位元；主記憶體所含頁框總數為 $2^{m - p}$ 個。

3. 位址轉譯硬體元件與流程：

• CPU 執行程式時發出虛擬位址，由記憶體管理單元（MMU）​負責轉譯。
• 硬體配置轉譯後備緩衝區（TLB）​以快取最近使用的頁表項，加速位址轉譯。
• 位址合成後，透過實體位址依序搜尋快取記憶體（Cache）​與主記憶體（Main Memory）。

解題方法

(一) 頁表內包含的項次（Entries）數量

• 已知條件：虛擬位址為 $32$ 位元，採位元組定址（Byte-addressable）；頁大小為 $2\ \mathrm{KB}$。
• 計算步驟：

1. 頁大小為 $2\ \mathrm{KB} = 2 \times 2^{10}\ \mathrm{B} = 2^{11}\ \mathrm{B}$，故頁內位移（Offset）需使用： $\log_2(2^{11}) = 11\ \text{位元}$
2. 虛擬頁號（VPN）的位元數為： $32 - 11 = 21\ \text{位元}$
3. 線性頁表（Single-level Page Table）中，每一個虛擬頁均對應一個頁表項（Page Table Entry, PTE），因此頁表內之項次數為： $2^{21} = 2,097,152\ \text{個（或表示為 } 2\ \mathrm{M} \text{ 個）}$

(二) 實體位址（Physical Address）包含的位元數

• 已知條件：實體記憶體大小為 $512\ \mathrm{MB}$，採位元組定址。
• 計算步驟：

1. 實體記憶體容量換算為位元組： $512\ \mathrm{MB} = 512 \times 2^{20}\ \mathrm{B} = 2^9 \times 2^{20}\ \mathrm{B} = 2^{29}\ \mathrm{B}$
2. 每個位元組需要唯一的位址編號，故實體位址所需位元數為： $\log_2(2^{29}) = 29\ \text{位元}$

(三) 標示頁框（Page Frame）位置最少需使用的位元數

• 已知條件：實體記憶體為 $512\ \mathrm{MB}$（$2^{29}\ \mathrm{B}$），頁框大小等於頁大小 $2\ \mathrm{KB}$（$2^{11}\ \mathrm{B}$）。
• 計算步驟：

1. 主記憶體中擁有的頁框總數為： $\frac{\text{實體記憶體大小}}{\text{頁框大小}} = \frac{2^{29}\ \mathrm{B}}{2^{11}\ \mathrm{B}} = 2^{18}\ \text{個}$
2. 要在主記憶體中唯一標示並區隔每一個頁框（即實體頁框號 PFN / PPN），所需的最少位元數為： $\log_2(2^{18}) = 18\ \text{位元}$ (亦可由實體位址總長度減去頁內位移求得：$29 - 11 = 18\ \text{位元}$)

(四) 程式執行時發出的記憶體位址名稱

• 程式在執行時，由中央處理器（CPU）產生的位址稱為虛擬位址（Virtual Address, VA），在作業系統理論中亦常統稱為邏輯位址（Logical Address）。