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{ 倍}$

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

核心觀念

1. 全加器（Full Adder, FA）之基本結構與運算原理： 全加器為組合邏輯電路的基本運算單元，具有三個 1 位元二進位輸入（被加數位元 $A_i$、加數位元 $B_i$、低位進位輸入 $C_i$）與兩個 1 位元輸出（總和位元 $S_i$、向高位的進位輸出 $C_{i+1}$），其實現之算術關係為： $A_i + B_i + C_i = 2 \times C_{i+1} + S_i$
2. 2 的補數（Two's Complement）加減法電路設計： 二進位減法 $A - B$ 可轉換為 2 的補數加法： $A - B = A + (-B) = A + (\overline{B} + 1)$ 利用互斥或閘（XOR Gate）具有「可控制反相器」的特性（當控制端為 $0$ 時，輸出原值；當控制端為 $1$ 時，輸出反相值），配合將最低位進位端 $C_0$ 設為控制訊號，即可僅用一組加法器同時達成加法與減法運算。
3. 算術邏輯單元（ALU）狀態旗標（Status Flags）之硬體生成機制： 在微處理器結構中，運算結果的狀態透過狀態旗標記錄，主要包含四個：

• 進位／借位旗標（Carry / Borrow Flag）：無號數運算之超出範圍指示。
• 滿溢／溢位旗標（Overflow Flag）：有號數運算時結果超出表示範圍指示。
• 負值旗標（Negative / Sign Flag）：運算結果之正負號指示。
• 零旗標（Zero Flag）：運算結果是否全為 0 之指示。

解題方法

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

1. 定義： 全加器（Full Adder）為能夠處理三個 1 位元二進位數相加的組合邏輯電路。三個輸入分別為被加數位元 $A$、加數位元 $B$，以及來自低位的進位輸入 $C_{in}$；輸出則為該位元的總和 $S$（Sum）以及產生給高位的進位輸出 $C_{out}$（Carry-out）。 其布林代數表示式為： $S = A \oplus B \oplus C_{in}$ $C_{out} = AB + BC_{in} + AC_{in} = AB + (A \oplus B)C_{in}$

2. 真值表（Truth Table）：

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

依據 2 的補數算術：

• 當 $OP = 0$（加法）時，電路執行 $A + B + 0$，加數各輸入端應為 $B_i$，最低位進位輸入 $C_0 = 0$。
• 當 $OP = 1$（減法）時，電路執行 $A + \overline{B} + 1$，加數各輸入端應為 $\overline{B_i}$，最低位進位輸入 $C_0 = 1$。

具體修改方式：

1. 加數端引腳配置 XOR 閘：在加數 $B$ 的每個位元（$B_0, B_1, B_2, B_3$）進入全加器前，分別串接一個 2 輸入的 XOR 閘。 XOR 閘的第一個輸入端接 $B_i$，第二個輸入端接控制訊號 $OP$，其輸出 $B'_i$ 接至原全加器的 $B_i$ 輸入端，即： $B'_i = B_i \oplus OP \quad (i = 0, 1, 2, 3)$

• 當 $OP = 0$ 時：$B'_i = B_i \oplus 0 = B_i$。
• 當 $OP = 1$ 時：$B'_i = B_i \oplus 1 = \overline{B_i}$。

2. 最低位進位端設定：將全加器最低位的進位輸入端 $C_0$ 直接連接控制訊號 $OP$，即： $C_0 = OP$

• 當 $OP = 0$ 時：$C_0 = 0$。
• 當 $OP = 1$ 時：$C_0 = 1$（達成 2 的補數所需之 $+1$）。

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

本電路為 4 位元加減法器，運算結果之和位元為 $S_3, S_2, S_1, S_0$，最高位全加器（處理 $A_3, B'_3$）之進位輸入為 $C_3$，進位輸出為 $C_4$。

1. 進位／借位旗標（Carry / Borrow Flag，記為 $C$）：

• 若單純代表加法器本體的最高位進位輸出，布林式為： $C = C_4$
• 若作為加減法通用之 Carry / Borrow 旗標（依微處理器架構如 x86 慣例，加法時產生進位為 1，減法時產生借位為 1，其中減法 $A - B$ 當 $A < B$ 時借位產生，此時加法器 $C_4 = 0$）： $C = C_4 \oplus OP$ （即 $OP = 0$ 時 $C = C_4$；$OP = 1$ 時 $C = \overline{C_4}$）。

核心觀念

本題考查計算機結構中精簡指令集計算機（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）。