108 年 國立清華大學資訊工程學系碩士班《計算機系統》

核心觀念

1. 系統呼叫（System Call）機制：使用者程序（User Program）透過系統呼叫向作業系統核心（OS Kernel）請求硬體或特權服務（如檔案 I/O、處理器進程管理、記憶體配置等）。
2. CPU 執行模式（Execution Modes）：CPU 硬體提供至少兩種存取等級：
   • 使用者模式（User Mode）：權限受限，無法執行特權指令（Privileged Instructions）或直接存取核心記憶體區段。
   • 核心模式（Kernel Mode / Supervisor Mode）：擁有最高權限，可執行所有指令並存取所有記憶體與硬體資源。
3. 陷阱指令（TRAP Instruction / Software Interrupt）：一種軟體引發的中斷，用於實現由 User Mode 安全切換至 Kernel Mode（Mode Switch），並跳轉至預設核心處理常式的硬體機制。

---

解題方法
本題考查作業系統對 System Call 的底層支援機制，包含 TRAP 指令的執行流程、系統呼叫號碼（System Call Number）的傳遞方式，以及一般函式呼叫（Subroutine CALL/RETURN）與系統呼叫在硬體權限切換與安全性上的本質差異。解題切入點如下：

1. (a) 步驟剖析：分開說明 User Space 準備、Hardware 模式與暫存器切換、Kernel Space 執行，以及 Return 返回 User Space 的四大階段。
2. (b) 識別機制：說明約定好的暫存器（Designated Register）與核心內的系統呼叫對照表（System Call Table / Dispatch Table）之運作。
3. (c) 限制對比：從「權限與 Mode Bit 切換」、「受控入口與安全性（Controlled Entry Point）」以及「獨立堆疊（Kernel Stack Isolation）」三個維度比較 CALL/RETURN 與 TRAP/IRET 的差異。

---

子題與內容解析

(a) 透過 TRAP 指令發起系統呼叫的完整步驟

當使用者應用程式發起系統呼叫時，系統執行的完整步驟如下：

1. 準備參數與系統呼叫號碼（User Space）：
   使用者程式（或 C 標準函式庫的 Wrapper 函式）將系統呼叫所需的參數以及唯一的「系統呼叫號碼（System Call ID）」放入約定的 CPU 暫存器中（例如 x86-64 架構下的 %rax 暫存器放號碼，%rdi、%rsi 等放參數）。
2. 執行 TRAP 指令（User Space $\rightarrow$ Hardware）：
   使用者程式執行 TRAP 特殊指令（在不同架構中稱為 int 0x80、syscall 或 sysenter），發起軟體中斷。
3. 硬體層級處理與模式切換（Hardware Level）：
   • CPU 捕獲 TRAP 訊號，自動將控制暫存器中的 Mode Bit 從使用者模式（User Mode）切換為核心模式（Kernel Mode）。
   • 硬體自動將當前使用者程式的執行上下文（Context，包含 Program Counter $PC$、Stack Pointer $SP$ 與狀態暫存器 Status Register / Flags）保存至核心堆疊（Kernel Stack）或專用硬體暫存器。
   • 硬體根據 TRAP 的向量號碼，查詢中斷向量表（Interrupt Vector Table, IVT / IDT），取得系統呼叫處理程式（System Call Handler）的進入點位址，並將 $PC$ 設定為該位址。
4. 核心層級處理與服務執行（Kernel Space）：
   • 作業系統的核心處理程式（System Call Handler）將其餘通用暫存器狀態保存至核心堆疊。
   • 處理程式讀取先前存入暫存器的系統呼叫號碼，以此號碼作為索引查詢「系統呼叫表（System Call Table）」，找到對應的核心服務常式（Kernel Service Routine，例如 sys_read()）並執行。
   • 服務執行完成後，將執行結果（回傳值）寫入指定的暫存器（如 %rax）。
5. 返回使用者模式（Kernel Space $\rightarrow$ User Space）：
   • 核心恢復先前保存的使用者暫存器狀態。

核心觀念

1. 行程排程演算法（Process Scheduling Algorithms）：

   • FCFS（First-Come, First-Serve）：先到先服務演算法。依行程進入 Ready 佇列（Ready Queue）的先後順序進行 CPU 資源分配（採 FIFO 佇列機制）。
   • SJF（Shortest-Job First）：最短工作優先演算法。挑選下一次 CPU Burst 時間最短的行程優先執行。
   • RR（Round-Robin）：循環分時演算法。專為分時系統設計，每個行程輪流獲得一段固定長度的時間單元（Time Quantum, $q$）執行 CPU 權限。

2. 可搶占與不可搶占（Preemptive vs. Nonpreemptive）：

   • Preemptive（可搶占）：當有更高優先權或新條件滿足的行程進入 Ready 佇列時，作業系統可強行中斷目前正在執行的行程並切換 CPU 資源。
   • Nonpreemptive（不可搶占）：行程一旦取得 CPU，便會持續執行直到該工作完成，或自願放棄 CPU（例如發出 I/O 請求或等待子行程）。

3. 餓死（Starvation / Indefinite Blocking）：

   • 指某個處於 Ready 狀態的行程，因排程演算法的偏頗性，導致長時間（甚至無限期）無法獲得 CPU 資源進行執行的現象。

---

解題方法

(a) 會導致 Starvation 的演算法與情境說明

在題目列出之排程演算法中，會產生 Starvation 的演算法為 Preemptive SJF 與 Nonpreemptive SJF。

• 演算法篩選分析：

  • FCFS（Preemptive / Nonpreemptive）：採 FIFO 佇列機制。由於佇列中先到的行程終將執行完畢，佇列後方的行程必然可在有限時間內獲得 CPU，故不會 Starvation。
  • RR（Round-Robin）：具備循環分時機制，任何 Ready 佇列中的行程皆能在每個週期固定分配到 $q$ 長度的 CPU 時間，故不會 Starvation。
  • SJF（Preemptive / Nonpreemptive）：優先權取決於 CPU Burst 長度。若系統持續注入短 CPU Burst 行程，長 CPU Burst 行程會被不斷延後排程，故會產生 Starvation。

• 具體情境描述（Scenario）：

  1. Preemptive SJF（又稱 Shortest Remaining Time First, SRTF）：
     • 情境：假設有一個需要長 CPU Burst 的行程 $P_{\text{long}}$（如 $100\text{ ms}$）於 $t = 0$ 時抵達系統並開始執行。隨後，在 $t = 1\text{ ms}, 2\text{ ms}, 3\text{ ms}, \dots$ 等時間點，系統源源不絕地進入 CPU Burst 極短的新行程 $P_1, P_2, P_3, \dots$（如每個僅需 $2\text{ ms}$）。
     • 結果：由於新抵達行程的剩餘 CPU Burst 時間始終小於 $P_{\text{long}}$ 當前的剩餘時間，排程器會不斷觸發搶占（Preemption），使得 $P_{\text{long}}$ 一再被迫交出 CPU 控制權，造成 $P_{\text{long}}$ 無限期無法完成（餓死）。
  2. Nonpreemptive SJF：
     • 情境：假設行程 $P_{\text{long}}$ 已經在 Ready 佇列中等待。當當前執行的行程結束、CPU 釋放出來時，若 Ready 佇列中持續有新進的短 CPU Burst 行程，排程器在每次決策時都會優先選擇這些短行程。
     • 結果：即使排程器不會中斷執行中的行程，但在每一次選取下一個行程時，$P_{\text{long}}$ 的排序永遠落後於新抵達的短行程，導致 $P_{\text{long}}$ 永遠無法獲選進入 CPU 執行（餓死）。

(b) 本質相同的兩個演算法與原因分析

在題目給定的六種演算法中，Preemptive FCFS 與 Nonpreemptive FCFS 本質上完全相同。

核心觀念

本題考查 semaphore 的兩種典型用途：

1. 以二元 semaphore 實作互斥鎖（mutex）。
2. 以 semaphore 建立兩個程序間的執行先後關係。

Semaphore $S$ 維持一個整數值，且 wait(S) 與 signal(S) 必須具備不可分割性：

• wait(S)：若 $S>0$，使 $S$ 減 $1$；若 $S=0$，呼叫者阻塞。
• signal(S)：使 $S$ 加 $1$，並喚醒因該 semaphore 阻塞的程序。

---

解題方法

（a）以 semaphore 實作 mutex lock

互斥鎖只允許一個程序或執行緒同時進入 critical section，因此可使用初始值為 $1$ 的 semaphore：

semaphore L(1)

設計如下：

acquire(L):
    wait(L)

release(L):
    signal(L)

運作說明

初始時 $L=1$：

1. 第一個執行緒呼叫 acquire(L)，執行 wait(L)，使 $L$ 由 $1$ 變成 $0$，成功取得鎖。
2. 其他執行緒再呼叫 acquire(L) 時，由於 $L=0$，會被阻塞，無法進入 critical section。
3. 持鎖者完成工作後呼叫 release(L)，執行 signal(L)，使 $L$ 恢復為 $1$，並喚醒一個等待中的執行緒。
4. 被喚醒的執行緒取得鎖後進入 critical section。

因此，$L$ 的值可視為「鎖是否可用」：

• $L=1$：鎖可取得。
• $L=0$：鎖已被占用。

---

（b）以 semaphore 確保執行先後順序

要求 statement $S1$ of process $P1$ 必須先於 statement $S2$ of process $P2$ 執行，因此建立一個初始值為 $0$ 的 semaphore：

semaphore x(0)

安排如下：

Process P1:
    S1
    signal(x)

Process P2:
    wait(x)
    S2

運作說明

核心觀念

本題考查虛擬記憶體的兩種配置方式：

• Paging（分頁）：將虛擬記憶體切成固定大小的 page，實體記憶體切成相同大小的 frame。
• Segmentation（分段）：依照程式的邏輯單位切割，例如 code、data、stack，每個 segment 大小可不同。

碎片分為：

• Internal fragmentation（內部碎片）：已配置給某單位的空間內，尚未被有效使用的部分。
• External fragmentation（外部碎片）：可用空間分散在不同位置，總量足夠但缺乏連續的大區塊。

---

解題方法

判斷碎片類型時，觀察記憶體配置單位是否固定大小：

1. 配置單位固定大小時，最後一個配置單位通常無法完全使用，容易產生內部碎片。
2. 若配置單位可變大小，配置時需要尋找連續空間，釋放後容易留下分散的小空洞，形成外部碎片。

因此：

• Paging 的配置單位是固定大小的 page。
• Segmentation 的配置單位是大小可變的 segment。

---

(a) Paging 是否具有內部碎片與外部碎片？

Internal fragmentation：有

Paging 使用固定大小的 page。若程式大小不是 page size 的整數倍，最後一個 page 通常無法完全填滿。

設：

• 程式大小為 $S$
• page size 為 $P$

所需 page 數為：

$$\left\lceil \frac{S}{P} \right\rceil$$

配置的總空間為：

$$\left\lceil \frac{S}{P} \right\rceil P$$

因此內部碎片大小為：

$$\left\lceil \frac{S}{P} \right\rceil P - S$$

此碎片最多小於一個 page，即：

$$0 \leq \text{Internal Fragmentation} < P$$

所以，paging 具有內部碎片，主要出現在程式最後一個 page 未被完全使用的部分。

External fragmentation：沒有

Paging 將實體記憶體切成固定大小的 frame，任何可用 frame 都能配置給任意虛擬 page。由於 page 不要求在實體記憶體中連續配置，即使可用 frame 分散在各處，也能完成配置。

因此，不會因為缺少連續的大型空間而無法配置，故：

Paging 沒有外部碎片。

(a) 結論

• 內部碎片：有
• 外部碎片：沒有

核心觀念

協程（Coroutine）是一種允許暫停與恢復執行的協同式多工機制。在 C 語言中，可利用 <setjmp.h> 的 setjmp 與 longjmp 儲存與恢復 CPU 執行環境（包含暫存器、堆疊指標 SP 與程式計數器 PC）：

1. setjmp(jmp_buf env)：保存當前呼叫環境至 env 中。直接呼叫時回傳 $0$。
2. longjmp(jmp_buf env, int val)：恢復 env 保存的環境，使執行流程跳轉回對應的 setjmp 呼叫點，並使該 setjmp 回傳 val（非 $0$ 值）。

當協程需要讓出 CPU 控制權（Yield）時，呼叫 setjmp 保存自身狀態，並隨即呼叫 longjmp 切換至目標協程的 jmp_buf，即可實現協同式上下文切換（Cooperative Context Switch）。

---

協程切換設計與關鍵程式碼

以下實作兩個協程（coroutine_a 與 coroutine_b）之間的交替執行與控制權轉移：

核心觀念

本題考驗作業系統（Computer Systems / Operating Systems）中「多執行緒與並行程式設計（Concurrency and Multithreading）」的排程機制與抽象化設計。

關鍵觀念與定義包括：

1. Grand Central Dispatch (GCD)：Apple 為 macOS 與 iOS 開發的多核心並行處理架構（系統級 API 與 Runtime 技術），將傳統以執行緒為中心（Thread-based）的並行模型，提升為以任務為中心（Task-based）的模型。
2. Blocks（程式區塊 / 閉包）：C、C++ 與 Objective-C 的語法擴充，用以將程式碼塊及其作用域內的上下文變數封裝為匿名函式物件（Anonymous Functions / Closures），作為提交給 GCD 的基本「任務（Task）」單位。
3. Dispatch Queues（調度佇列）：GCD 用於管理與排程 Blocks 的 FIFO 佇列。包含：
   • Serial Dispatch Queue（串列佇列）：一次僅執行一個任務，嚴格按 FIFO 順序執行。
   • Concurrent Dispatch Queue（並行佇列）：按 FIFO 順序取出任務，但可調用多個執行緒同時並行執行。
4. Thread Pool Management（執行緒池管理）：由 OS 底層與 GCD Runtime（libdispatch）自動維持執行緒池，根據系統即時負載與 CPU 核心數動態分配執行緒，取代開發者手動建立與管理執行緒。

---

解題方法

回答本題需切入兩個核心訴求：「運作機制（How it works）」與「優點效益（Benefits）」，建議從程式語言語法層、佇列與任務調度層、以及作業系統核心排程層三個面向完整說明。

一、 GCD 的運作機制（How the GCD Scheme Works）

1. 任務封裝（Task Packaging with Blocks）：
   開發者利用 C/C++ 擴充語法 Blocks（例如 ^{ /* Task Code */ }），將欲並行執行的工作項目封裝成單一 Task。
2. 提交至調度佇列（Submitting to Dispatch Queues）：
   將 Blocks 提交至特定的 Dispatch Queue 中，提交方式分為：
   • 非同步提交（dispatch_async）：調用端不等待任務完成即繼續執行後續程式碼。
   • 同步提交（dispatch_sync）：調用端會阻塞（Block），直到該任務執行完成。
3. 佇列類型與任務排程（Queue Processing）：
   • Serial Queue：系統確保佇列中前一個 Block 執行完畢後，才開始執行下一個 Block，常用於實現資源存取的互斥性（Mutual Exclusion）。
   • Concurrent Queue：系統會依序自佇列取出 Block，並將其派發至執行緒池中的不同執行緒同時執行。
4. 核心層級執行緒池與動態排程（Thread Pool & Kernel Integration）：
   GCD 整合作業系統核心（Mach/POSIX 執行緒與排程器），依據當前硬體 CPU 核心數量、系統整體 Load、以及任務的優先等級（Quality of Service, QoS），自動分配最合適的執行緒數量執行 Blocks。

二、 GCD 的優點（Benefits of the GCD Scheme）

1. 簡化並行程式設計（Simplification of Concurrent Programming）：
   開發者僅需關注「任務定義（Blocks）」與「佇列選擇」，無需處理複雜的 Thread 生命週期（如 pthread_create、pthread_join）與低階同步邏輯。
2. 避免過度訂閱與頻繁上下文切換（Eliminating Thread Thrashing & Over-subscription）：
   傳統程式若各自建立大量 Thread，會導致 CPU 花費過多時間在執行緒上下文切換（Context Switching Overhead）。GCD 由 OS 全域掌控 Thread Pool，確保活躍執行緒數目與 CPU 核心數精確匹配，大幅降低 Context Switch 成本。
3. 高硬體擴展性與資源利用率（Automated Scalability & Efficiency）：
   程式碼具備自動適應性。

核心觀念

本題考查 OpenMP 的資料競爭與互斥同步。多個執行緒同時讀寫共享變數，且存取順序會影響結果時，就會發生資料競爭。

圖 1 的 result += ... 是「讀取 result、計算新值、寫回 result」的複合操作，不是不可分割的單一操作。多個執行緒可能同時讀到相同的舊值，分別計算後再寫回，造成部分累加結果遺失。

解題方法

a. 圖 1 的競爭條件與圖 2 的修正

圖 1 中，result 是所有執行緒共享的變數。迴圈的不同迭代由多個執行緒執行，每個迭代都要更新 result。若兩個執行緒同時執行累加，可能發生：

1. 兩個執行緒都讀到相同的 result 舊值。
2. 各自計算要加上的數值。
3. 先後將各自結果寫回 result。

後寫入的結果會覆蓋先前的更新，因此最後的 result 可能小於正確總和。

圖 2 將每次更新放在 #pragma omp critical 區段內。同一時間只有一個執行緒能進入該區段，故每次讀取、計算與寫回都會依序完成，避免更新互相覆蓋。

b. 減少 critical 區段

圖 2 每次迴圈迭代都進入一次 critical 區段，共需同步 1000 次。可讓每個執行緒先用區域變數累加自己負責的迭代，迴圈結束後再進入一次 critical 區段，把小計加到共享的 result：

核心觀念

本題考查計算機結構中評估系統效能改善的重要定量法則——阿姆達爾定律（Amdahl's Law）。

在計算機系統設計中，當我們對系統的某個特定模組或功能進行優化時，阿姆達爾定律用於計算該局部優化對系統整體效能所帶來的提升幅度。其核心變數與定義如下：

1. 整體加速比（Overall Speedup, $S_{\text{overall}}$）：
   $\text{Speedup} = \frac{\text{Execution Time}_{\text{old}}}{\text{Execution Time}_{\text{new}}}$
   表示優化前與優化後系統執行時間的比值。

2. 可改良比例（Fraction Enhanced, $f$）：
   在未優化前（原始系統），可被改良部分的執行時間佔總執行時間的比例（$0 \le f \le 1$）。

3. 局部加速比（Speedup Enhanced, $s$）：
   僅針對「可改良部分」進行優化後，該部分效能提升的倍數（$s > 1$）。

---

解題方法

本題為 5 分的申論／問答題。解題脈絡需分為「公式推導與原理說明」以及「指導系統效能改善的設計原則」兩大部分：

一、阿姆達爾定律的定義與數學推導

假設原系統的總執行時間為 $T_{\text{old}}$。

1. 原始執行時間可分為兩部分：
   • 可改良部分耗時：$f \cdot T_{\text{old}}$
   • 不可改良（未受惠）部分耗時：$(1 - f) \cdot T_{\text{old}}$
2. 進行局部優化後，可改良部分的執行時間縮減為原來的 $\frac{1}{s}$，而不可改良部分保持不變。因此，優化後的總執行時間 $T_{\text{new}}$ 為：
   $T_{\text{new}} = (1 - f) \cdot T_{\text{old}} + \frac{f}{s} \cdot T_{\text{old}} = T_{\text{old}} \left( (1 - f) + \frac{f}{s} \right)$
3. 根據加速比定義，整體加速比公式推導如下：
   $S_{\text{overall}} = \frac{T_{\text{old}}}{T_{\text{new}}} = \frac{T_{\text{old}}}{T_{\text{old}} \left( (1 - f) + \frac{f}{s} \right)} = \frac{1}{(1 - f) + \frac{f}{s}}$

二、阿姆達爾定律如何指導系統效能改善

阿姆達爾定律為計算機系統設計師提供了三項關鍵的指導方針：

1. 常態優先原則（Make the Common Case Fast）：

   • 系統整體的提升效果主要受限於 $f$（可改良比例）。若某指令或模組在總執行時間中所佔比例極小（$f \approx 0$），即便將其局部加速比提升至無窮大（$s \to \infty$），整體的改善效果仍微乎其微。
   • 因此，設計資源應優先投入於出現頻率最高、耗時最長的部分。

2. 收益遞減法則（Law of Diminishing Returns）：

   • 當對同一個模組持續加大投資以提高局部加速比 $s$ 時，整體加速比 $S_{\text{overall}}$ 的成長曲線會趨於平緩。
   • 盲目追求單一模組的極致加速（高 $s$ 值）成本極高且邊際效益遞減，設計時應評估成本與收益的平衡。

核心觀念

先依題目公式計算 FP 乘法次數，再利用 FP MUL、FP ADD、FP Load/Store 的比例，求出各類操作的數量。總週期數為各類操作數乘上對應的每操作週期數（CPO），最後除以處理器時脈頻率，得到運算時間。

解題方法

卷積層的參數數量為

$$\#\text{parameter} = \text{kernel}_{size}^{2}\times\text{channel}_{in}\times\text{channel}_{out} = 5^{2}\times 3\times 100 = 7{,}500$$

FP 乘法次數為

$$N_{\text{MUL}} = \#\text{parameter}\times x\times y = 7{,}500\times 200\times 200 = 300{,}000{,}000$$

FP MUL 佔全部操作的 $80\%$，所以總操作數為

$$N_{\text{total}} = \frac{N_{\text{MUL}}}{0.80} = 375{,}000{,}000$$

依操作比例求出各類操作數：

$$N_{\text{ADD}}=0.15N_{\text{total}}=56{,}250{,}000$$

核心觀念

本題考的是位元串列循序電路與最短時脈週期。電路每個時脈處理一個位元，D 正反器保存狀態供下一個位元使用；輸入須由最低有效位元開始送入。

最短時脈週期由正反器之間的最長路徑決定：

$$T_{\min}=t_{\text{時脈至 }Q}+t_{\text{組合邏輯}}+t_{\text{建立時間}}$$

本題可忽略建立時間。

解題方法

（a）由輸出與狀態方程判斷功能

令 $X_i$ 為目前輸入的第 $i$ 個位元，$C_i$ 為左側 AND 閘輸出、送往後段邏輯的狀態，$Y_i$ 為輸出位元。

處理最低位元時，令 $\mathrm{Start}=1$，左側 AND 閘將 $C_0$ 強制為 $0$；之後令 $\mathrm{Start}=0$，讓正反器保存的狀態通過。

由圖中的 XOR 閘可得：

$$Y_i=\overline{X_i}\oplus C_i$$

由回授至 D 端的 AND、OR 閘可得下一個狀態：

$$C_{i+1} =X_i\lor\left(\overline{X_i}\land C_i\right) =X_i\lor C_i$$

因此，$C_i$ 表示「先前處理過的低位元中，是否已經出現 $1$」：

• 尚未遇到 $1$ 時，$C_i=0$，輸出為 $Y_i=\overline{X_i}$。
• 遇到第一個 $1$ 時，該位元仍使用 $C_i=0$，所以輸出 $0$，並使下一個狀態變成 $1$。
• 其後的位元，$C_i=1$，輸出為 $Y_i=\overline{X_i}\oplus1=X_i$。

也就是從最低位元開始，反相直到第一個 $1$，包含該位元；其餘高位元保持原樣。這正是二進位減 $1$ 的規則。例如：

$$00001000_2-1=00000111_2$$

核心觀念

本題旨在考驗 MIPS 組譯碼對應至 C 語言指標（Pointer）運算之對照能力，以及對 MIPS 暫存器慣例（Register Conventions）的認識。

1. MIPS 暫存器慣例 (Register Conventions)：

   • $a0 ~ $a3（Register 4–7）：引數暫存器（Argument Registers），用於傳遞函式的輸入參數。在本題中，$a0 為陣列起始位址（int *），$a1 為陣列元素個數（int）。
   • $t0 ~ $t9（Register 8–15, 24–25）：臨時暫存器（Temporary Registers），用於儲存運算過程中的暫存值。
   • $ra（Register 31）：返回位址暫存器（Return Address Register），用於儲存呼叫結束後返回原程式碼的位址。

2. MIPS 定址與指標運算：

   • sll $t1, $a1, 2：將 $a1 邏輯左移 2 位元（等同乘以 $4$），計算出 $a1$ 個 int 元素所佔用的記憶體位元組偏移量（Byte Offset）。
   • lw $t2, 4($t0)：以 $t0 所存位址加上 $4$ 位元組作為記憶體位址，取出一個 32 位元整數（即下一個陣列元素 *(ptr + 1)）。
   • sw $t2, 0($t0)：將 $t2 的數值寫回 $t0 所指向的記憶體位址（即當前陣列元素 *ptr）。
   • addi $t0, $t0, 4：指標移動 4 個位元組（在 int* 型態下相當於 ptr++）。

---

解題方法與推導步驟

(a) MIPS 組譯碼逐行語意推導

組譯碼逐行翻譯與 C 語言對照如下：

1. find: move $t0, $a0

   • 將陣列起始位址 $a0 複製至臨時暫存器 $t0。
   • 對應 C 語意：int *t0 = a0;（設 t0 為指向陣列開頭的指標）。

2. sll $t1, $a1, 2

   • $t1 = a1 * 4，計算 $a1$ 個整數元素的總位元組數。

3. add $t1, $t1, $a0

   • $t1 = a0 + (a1 * 4)，得到陣列終點（上界）的記憶體位址。
   • 對應 C 語意：int *t1 = a0 + a1;（指標加法自動乘以 sizeof(int)）。

4. loop: beq $t0, $t1, done

   • 當前指標 $t0 若等於終點指標 $t1，則跳轉至 done 結束迴圈。
   • 對應 C 語意：while (t0 != t1)

5. lw $t2, 4($t0)

   • 讀取 $t0 + 4 位址的整數資料至 $t2。
   • 對應 C 語意：t2 = *(t0 + 1);

6. sw $t2, 0($t0)

   • 將 $t2 寫入 $t0 所指向的位址。
   • 對應 C 語意：*t0 = t2;（與上一指令合起來即 *t0 = *(t0 + 1);）。

7. skip: addi $t0, $t0, 4

   • 將指標 $t0 增加 4 個位元組。
   • 對應 C 語意：t0++;

8. b loop

   • 無條件跳回迴圈開頭繼續執行。

9. done: jr $ra

   • 返回呼叫函式。

(b) 臨時暫存器（Temporary Registers）數量統計

核心觀念

直接對映快取的位址分成標籤（Tag）、索引（Index）與區塊位移（Offset）。索引位元數決定快取行數，位移位元數決定每個區塊的大小；資料儲存容量等於快取行數乘上每行資料量。

快取的實際儲存容量還包含標籤與有效位元。以下以每行有 $48$ 位元標籤、$1$ 位元有效位元計算，不計題目未指定的其他狀態位元。

解題方法

圖中標籤為位元 $63$–$16$，共 $48$ 位元；索引為位元 $15$–$6$，共 $10$ 位元；位移為位元 $5$–$0$，共 $6$ 位元。由此可得快取有 $2^{10}$ 行，每個區塊含 $2^6$ 個位元組。

(a) 資料儲存容量

每行的資料量為 $2^6$ 位元組，行數為 $2^{10}$，因此：

$$2^{10}\times 2^6 =2^{16}\text{ bytes} =64\text{ KiB}$$

(b) 實際儲存容量與資料儲存容量之比

核心觀念

加速比定義為「單處理器執行時間」除以「多處理器執行時間」：

$$S=\frac{T_1}{T_n}$$

其中，$T_1$ 是單處理器執行整個工作負載的時間，$T_n$ 是 $n$ 個處理器執行時的總時間。平行部分可分配給多個處理器；循序部分不受處理器數量影響。工作負載分配不均時，平行部分的執行時間由負載最重的處理器決定。

解題方法

題目給定平行部分時間為 $6t^2$，循序部分時間為 $3t$。令 $t=10$：

$$T_{\text{平行}}=6(10)^2=600$$ $$T_{\text{循序}}=3(10)=30$$

因此，單處理器執行時間為：

$$T_1=600+30=630$$

（a）15 個處理器理想分配

平行部分平均分配給 15 個處理器，執行時間為 $600/15=40$；循序部分仍需 30：

$$T_{15}=40+30=70$$ $$S=\frac{630}{70}=9$$

核心觀念

Omega 網路是由多階段 $2\times2$ 交換盒組成的多級互連網路。對 $N=2^n$ 個處理器，網路有 $n=\log_2N$ 個階段，每階段有 $N/2$ 個交換盒；相鄰階段之間以 perfect shuffle（完美洗牌）排列線路。

本題有 $8=2^3$ 個處理器，因此需要 3 個階段、每階段 4 個交換盒，共 12 個交換盒。圖中的交換盒有兩個輸入、兩個輸出，可依控制設定選擇直通或交叉連接。

解題方法

原卷附圖中的交換盒是 $2\times2$ 交換盒；題目要求畫出 8 個處理器的 Omega 網路，並比較它與 8×8 crossbar 網路的交換數量及功能。

將處理器編號視為 3 位元二進位數。每兩個相鄰處理器接到第一階段的一個交換盒；相鄰階段間採用位元循環左移的 perfect shuffle：

$$(b_2b_1b_0)_2\longmapsto(b_1b_0b_2)_2$$

依此規則，8 條線路的排列為：

$$0\to0,\quad 1\to2,\quad 2\to4,\quad 3\to6,\quad 4\to1,\quad 5\to3,\quad 6\to5,\quad 7\to7$$

(a) 8 個處理器的 Omega 網路

令 $S_{r,i}$ 表示第 $r$ 階段、第 $i$ 個交換盒，其中 $r=1,2,3$，$i=0,1,2,3$。第一階段的輸入配對如下：

$$(P_0,P_1)\to S_{1,0},\quad (P_2,P_3)\to S_{1,1},\quad (P_4,P_5)\to S_{1,2},\quad (P_6,P_7)\to S_{1,3}$$

第三階段則由 $S_{3,i}$ 的兩個輸出分別接到 $P_{2i}$、$P_{2i+1}$。兩階段之間都按同一組 perfect shuffle 接線。下表列出每個交換盒的兩個輸出端實際連到哪個交換盒及其輸入端；表中連線要套用兩次：一次從第一階段接到第二階段，再一次從第二階段接到第三階段。

目前交換盒	輸出端 0 接至	輸出端 1 接至
$S_{r,0}$	$S_{r+1,0}$ 的輸入端 0	$S_{r+1,1}$ 的輸入端 0
$S_{r,1}$	$S_{r+1,2}$ 的輸入端 0	$S_{r+1,3}$ 的輸入端 0