109 年 國立成功大學資訊工程系碩士班《計算機組織與系統》

核心觀念

本題考查處理器架構如何配合工作負載，以及管線如何把指令執行拆成多個階段，提升整體吞吐量。題目未指定處理器世代，以下以典型五級 RISC CPU 與 SIMT GPU 架構說明；實際階段會依處理器設計而異。

CPU 著重低延遲與控制能力，通常配置少量功能較完整的核心，並使用快取、分支預測、亂序執行等機制。GPU 著重高吞吐量與大量平行運算，以多個運算單元同時執行大量資料相似的工作，並透過切換執行中的執行緒群組來隱藏記憶體延遲。

解題方法

依序比較兩者的架構、典型管線，以及管線設計所對應的目標。CPU 可用指令執行的階段說明；GPU 則須區分運算工作與圖形繪製工作，因為 GPU 的「管線」可能指其中任一種。

CPU 架構與管線

典型 CPU 架構可概括如下：

主記憶體 ↔ 快取 ↔ 暫存器
                    ↕
控制單元 → 指令解碼 → 算術邏輯單元

CPU 核心包含控制單元、暫存器、算術邏輯單元（ALU）與快取等。控制單元負責取指與解碼，ALU 執行整數或邏輯運算；暫存器提供快速的運算元存取。現代 CPU 也常利用分支預測和亂序執行，減少等待資料或分支結果造成的停頓。

典型五級管線如下：

IF → ID → EX → MEM → WB

• IF（取指）：依程式計數器從指令快取或記憶體取得指令。
• ID（解碼）：解析指令，讀取來源暫存器，產生控制訊號。
• EX（執行）：進行算術、邏輯、位址計算或分支判斷。
• MEM（記憶體存取）：讀取或寫入資料記憶體；不需要存取記憶體的指令通常略過實際存取。
• WB（回寫）：將運算結果寫回目的暫存器。

管線讓多條指令同時處於不同階段。理想情況下，管線填滿後可達到每個週期完成一條指令；資料相依、資源競爭或分支判斷則可能造成停頓。常見處理方式包括資料轉送、插入停頓週期，以及分支預測。

GPU 架構與管線

GPU 通常由多個串流多處理器（SM）組成；每個 SM 含多個運算單元、暫存器與共享記憶體。GPU 將執行緒分組成一個個 warp，由排程器派送。

核心觀念

本題考查兩種平行運算方式：異質運算著重於處理器種類的組合；資料平行運算著重於如何把工作分配到大量資料上。

• 異質運算（heterogeneous computing）：在同一個系統中使用兩種或以上不同類型的處理器或運算單元，讓各單元執行適合自己的工作。常見組合是 CPU 搭配 GPU：CPU 負責控制流程與通用運算，GPU 負責大量、規則且可平行化的運算。
• 資料平行運算（data parallel computing）：把一批資料分給多個運算單元，讓它們同時對不同資料元素執行相同或相似的運算。例如兩個向量相加時，各運算單元分別計算不同位置的元素。

解題方法

分別抓住兩個名詞的判斷重點：

核心觀念

本題考查矩陣乘法的索引關係，以及如何將可平行化的計算工作分配給 GPU。

令 $A$ 為 $M\times N$ 矩陣、$B$ 為 $N\times P$ 矩陣，結果 $C$ 為 $M\times P$ 矩陣。每個輸出元素是 $A$ 的一列與 $B$ 的一行做內積：

每個 $C_{ij}$ 的計算彼此獨立，因此可將不同的輸出元素分派給 GPU 上不同的執行緒。以下採用 CUDA C，並假設矩陣以 row-major（列優先） 方式儲存。

解題方法

將 GPU 執行緒配置成二維網格：每個執行緒負責計算一個 $C_{ij}$。執行緒的座標決定輸出元素的列與行：

• row 對應 $i$，範圍為 $0$ 到 $M-1$。
• col 對應 $j$，範圍為 $0$ 到 $P-1$。
• CUDA 執行緒區塊可能超出矩陣邊界，因此核心函式先檢查索引範圍。

row-major 下，矩陣元素的線性索引為：

以下程式包含主機端配置與資料傳輸，以及 GPU 上的矩陣乘法核心函式。輸入矩陣以遞增數值初始化，便於確認程式流程。

核心觀念

讀者－寫者問題要求共享資料遵守兩項互斥規則：

• 多個讀者可以同時讀取。
• 寫者寫入時，不能有其他讀者或寫者存取共享資料。

這段程式使用 wmut 保護共享資料，使用 rmut 保護讀者計數 rcount。第一位進入的讀者會取得 wmut，最後一位離開的讀者才釋放它；因此，讀者群組讀取期間會阻擋寫者。

解題方法

判斷是否為「最佳解法」，要先確認評估標準。若只看互斥與讀者並行，這段程式能達成基本要求：多位讀者可同時讀取，寫者則獨占共享資料。

但它採用讀者優先策略。只要仍有讀者，寫者就不能取得 wmut；而新讀者也能在讀者計數更新後加入。因此，若讀者持續進入，rcount 就可能一直不歸零，寫者便會一直等待，形成寫者飢餓。

正確性與限制

核心觀念

這段程式使用讀者優先的讀寫鎖：多位讀者可以同時讀取；只有第一位讀者取得 $wmut$，最後一位讀者才會釋放 $wmut$。因此，寫者一旦被讀者擋住，後續讀者仍可能加入正在進行的讀取。

解題方法

依題目給定的開始順序，逐一追蹤 $rcount$、$wmut$ 的狀態，以及各執行緒何時進入臨界區：

1. $R1$ 開始執行：取得 $rmut$，將 $rcount$ 從 $0$ 加為 $1$。因為它是第一位讀者，取得 $wmut$ 後進入讀取臨界區。
2. $W1$ 開始執行：嘗試取得 $wmut$，但 $wmut$ 已由讀者群持有，因此被阻擋，尚未進入寫入臨界區。
3. $R2$ 開始執行（三個執行緒幾乎同時到達，$R2$ 到達時 $R1$ 仍在讀取）：取得 $rmut$，將 $rcount$ 從 $1$ 加為 $2$。因為它不是第一位讀者，不必取得 $wmut$，便能進入讀取臨界區。

核心觀念

信號量的 wait 與 signal 操作必須具備原子性：檢查並修改信號量的值時，不能被其他執行緒插入操作。否則，多個執行緒可能同時判斷資源可用，造成互斥失效。

題目中的讀者與寫者程式以信號量保護共享資料；要讓這些操作安全執行，底層必須有硬體支援的原子指令。

解題方法

判斷此題的切入點是：信號量的核心需求為「不可分割地讀取並更新共享狀態」。常見的硬體原子指令包括：

• Test-and-Set（測試並設定）：原子地讀取記憶體位置的舊值，並將其設為新值。
• Swap／Exchange（交換）：原子地交換暫存器與記憶體位置的內容。

核心觀念

題目考的是：沒有硬體原子指令時，如何用軟體互斥演算法保護鎖的內部狀態，讓多執行緒不會同時修改 semaphore 的計數值或排隊狀態。

這類演算法以共享變數和協定建立臨界區。兩個執行緒可使用 Peterson 演算法；多個執行緒可使用 Lamport 麵包店演算法。它們不依賴硬體的測試並設定等原子指令，但假設對共享變數的基本讀寫本身不可被撕裂，且執行時遵守程式指定的記憶體順序。

解題方法

以兩個執行緒為例，Peterson 演算法使用 want[2] 記錄各執行緒是否想進入臨界區，並用 turn 指定優先讓哪一方進入：

want[i] = true;
turn = j;
while (want[j] && turn == j) {
    // 等待對方離開
}

// 臨界區：更新 semaphore 的內部狀態

want[i] = false;

核心觀念

這題考檔案資料讀取時，處理器快取以外的資料快取，以及作業系統何時會略過這些軟體快取。

從磁碟讀取檔案到使用者程式時，可能經過下列快取：

• 使用者空間快取：例如 C 標準函式庫的 stdio 緩衝區。程式透過 fread() 等函式讀取時，資料可先留在程式的緩衝區，供後續讀取重用。
• 作業系統頁面快取（page cache）：核心將檔案內容保留在主記憶體中。讀取時若資料已在快取內，就能直接由記憶體提供，不必再次存取磁碟。
• 區塊或緩衝快取（buffer cache）：以磁碟區塊為單位快取資料。在部分系統中，它與頁面快取分開；現代作業系統常將兩者整合或共用快取資料。
• 儲存裝置控制器快取：控制器也可能暫存讀寫資料。它位於硬體層，與作業系統的軟體快取不同。

檔案系統也會快取目錄項目、inode 等中繼資料，但這些快取的是檔案系統資訊，不是題目所問的檔案內容。

解題方法

依資料由磁碟傳到應用程式的路徑，逐層辨認可能存放檔案內容的位置：使用者空間緩衝區、核心記憶體中的頁面或區塊快取，以及儲存裝置端的控制器快取。題目特別問「軟體快取」，作答重點應放在使用者空間與作業系統中的快取；裝置控制器快取屬硬體層，須與軟體快取區分。

核心觀念

這題考的是統一緩衝區快取（Unified Buffer Cache，亦稱統一頁面快取）的設計。系統把檔案內容與行程的虛擬記憶體頁面放在同一套虛擬記憶體管理與快取機制中管理。

解題方法

追蹤資料從檔案進入行程記憶體的路徑：

1. 行程讀取檔案時，檔案內容會先進入核心的檔案快取，也就是頁面快取。
2. 若行程再把讀到的資料存進 heap，read() 會將資料從核心空間複製到行程的使用者空間。
3. 因此，同一份檔案資料會同時占用頁面快取與行程 heap 的記憶體。

核心觀念

「雙重快取」（double caching）是指同一份檔案資料同時保存在兩個不同的快取中，因而占用兩份記憶體空間。典型情況是資料一份存於檔案系統的緩衝快取（buffer cache），另一份存於虛擬記憶體的頁面快取（page cache）。

解題方法

核心觀念

這題考的是如何避免同一份檔案資料同時存在於「檔案系統快取」與「虛擬記憶體頁面快取」，造成重複快取、浪費記憶體，或兩份資料內容不一致。

解法是使用統一緩衝快取（Unified Buffer Cache）：檔案讀寫與記憶體映射檔案共用同一份快取頁面，讓同一個檔案區塊只保留一份快取副本。

解題方法

辨認題目中的「避免檔案資料被快取兩次」，關鍵在於讓不同檔案存取路徑共用同一個快取：

• read()、write() 等檔案 I/O 操作，透過統一緩衝快取存取資料。
• mmap() 將檔案映射到程序的虛擬位址空間；頁面載入或修改時，也使用同一份統一緩衝快取。

因此，兩種存取方式不會各自建立一份內容相同的快取。

I/O 方塊圖