114 一般警察特考二等 刑事警察人員類別數位鑑識組 計算機系統(包括計算機結構、作業系統) 考古題詳解

核心觀念

本題考的是「移位加法乘法器（Shift-and-Add Multiplier）」的硬體控制。

將乘積暫存器 $P$ 分成高、低兩部分：

• $P_H$：高 4 位元，存放部分積。
• $P_L$：低 4 位元，存放乘數及其右移結果。
• 被乘數暫存於 $M$。
• 每次測試 $P$ 最右邊的最低有效位元 $P_0$：
• 若 $P_0=1$，則 $P_H \leftarrow P_H+M$。
• 若 $P_0=0$，不進行加法。
• 完成判斷後，將整個 8 位元乘積暫存器右移一位。
• 4 位元乘法需重複執行 4 次。

公式為：

（一）Control Test 演算法

暫存器設定

令：

• $M$：4 位元被乘數暫存器。
• $P$：8 位元乘積暫存器。
• $P_H$：$P$ 的高 4 位元。
• $P_L$：$P$ 的低 4 位元。
• $C$：迴圈計數器，初始值為 4。

初始化：

控制流程

1. 測試 $P_L$ 的最低位元 $P_0$。
2. 若 $P_0=1$，執行：

$P_H \leftarrow P_H+M$

3. 將 8 位元乘積暫存器右移一位：

$P \leftarrow P \gg 1$

4. 計數器減 1：

$C \leftarrow C-1$

5. 若 $C\neq 0$，回到步驟 1。
6. 若 $C=0$，$P$ 即為 8 位元乘積。

虛擬流程表示

（二）$5\times 12$ 的執行過程

初始值

被乘數：

乘數：

因此：

每次先測試最低位元，再決定是否加法，最後右移。

執行表

核心觀念

本題考查 32 位元二補數（two’s complement）有號數的加減法與滿溢判斷。32 位元二補數可表示的範圍為

最高位元 $x_{31}$ 是符號位元：$0$ 表示非負數，$1$ 表示負數。滿溢是指數學上的正確結果超出上述範圍；硬體仍會保留 32 位元結果，因此截去進位後，位元結果可能代表另一個數值。

（一）加法與減法的滿溢情形

加法 $A+B$

只有兩個加數同號時，才可能發生滿溢：

• 正數加正數，結果卻成為負數：正向滿溢。
• 負數加負數，結果卻成為非負數：負向滿溢。
• 兩個加數異號：不會發生有號滿溢。

以 32 位元表示，令 $A_{31}$、$B_{31}$ 為加數符號位元，$S_{31}$ 為結果符號位元，則加法滿溢條件為

例如，最大正數加 $1$：

數學結果是 $2^{31}$，超出最大可表示值，位元結果的符號卻變成負數，因此發生滿溢。

減法 $A-B$

減法可視為 $A+(-B)$。只有被減數與減數異號時，才可能滿溢：

• 正數減負數，結果卻成為負數：正向滿溢。
• 負數減正數，結果卻成為非負數：負向滿溢。
• 被減數與減數同號：不會發生有號滿溢。

其條件為

例如，最大正數減 $-1$ 等同最大正數加 $1$，數學結果超出可表示範圍，結果符號卻為負，故發生滿溢。

（二）滿溢檢查電路或演算法

令 $S$ 為 32 位元運算結果，$A_{31}$、$B_{31}$、$S_{31}$ 分別為兩個運算元與結果的符號位元。

核心觀念

本題考查 CPU 執行時間與平均 CPI 的計算，以及平行化後的加速比。總時脈週期數為各類指令數乘上其 CPI 後加總；平均 CPI 則為總時脈週期數除以總指令數。

平行化的提升幅度以加速比計算：

解題方法

先依各類指令的數量與 CPI 計算總時脈週期數，再除以 2 GHz 求執行時間。平行化部分依題目指定的指令數變化，分別計算 4 核心與 8 核心的總週期數；每個核心的分支指令數維持不變，因此分支類總週期數不變。

（一）單處理器執行時間與平均 CPI

各類指令所需週期數如下：

• 算術類：$2.5\times10^9\times1=2.5\times10^9$ 個週期
• Load/store 類：$1.2\times10^9\times10=12.0\times10^9$ 個週期
• 分支類：$2.0\times10^8\times5=1.0\times10^9$ 個週期

因此總時脈週期數為：

時脈頻率為 $2\text{ GHz}=2\times10^9$ 次／秒，故執行時間為：

總指令數為：

平均 CPI 為：

（二）平行化後的提升幅度

題目將每個核心的分支指令數維持為 $2.0\times10^8$ 道；算術類與 load/store 類指令數則依指定除數調整。各核心時脈頻率相同，因此以各平行版本的總週期數除以 $2\times10^9$ 求時間，再與單處理器的 7.75 秒相比。

4 個核心

核心觀念

本題考查記憶體階層中「命中」與「錯失」的意義，以及虛擬位址經過 TLB、頁表、主記憶體與快取時，三種錯失如何互相制約。

• 命中（hit）：在目前查詢的階層中找到所需資訊。例如 TLB 命中，表示在 TLB 找到虛擬頁號對應的實體頁框號；快取命中，表示所需資料已在快取中。
• 錯失（miss）：目前階層找不到所需資訊，必須到下一層查找。例如 TLB 錯失要查頁表；快取錯失要向下一層記憶體取得資料。
• 頁錯失（page fault）：頁表指出該虛擬頁目前不在主記憶體，作業系統須將頁面載入主記憶體，並更新頁表等映射資訊。

命中通常可由較快的階層直接完成存取；錯失則須多花時間查找較低層，甚至由作業系統處理，因此會增加平均存取時間。命中率愈高，整體效能通常愈好；錯失率愈高，效能通常愈差。快取的平均記憶體存取時間可概念化為：

解題方法

以一次記憶體存取的順序判斷三種錯失：

1. 先查 TLB：命中時取得實體位址；錯失時查頁表。
2. 再確認頁面是否在主記憶體：若不在，發生頁錯失；若在，取得實體位址。
3. 最後查快取：只有資料已在主記憶體、且映射後的實體位址已確定，才進行快取查詢。快取命中即取出資料；快取錯失則向主記憶體讀取資料。

因此，TLB 錯失與頁錯失可以同時發生；但依題目所述「資料須先存在主記憶體，才能存在快取」，頁錯失與快取錯失不能同時發生。頁面載入主記憶體後，才會繼續快取查詢。

七種組合分析