110 成大資工所硬體考點分析

題型與配分

科目：計算機組織與系統，系所「電機資訊學院－資訊聯招」，日期 0202、節次 1，全卷 100 分、2 頁、只有兩大題。不可使用計算機、於本試題紙上作答者不予計分。

全卷只有兩大題，各佔 50 分——這是成大硬體十年裡最極端的配分結構。任何一大題答得零散，就直接失去一半分數。

第 2 題是一道 50 分的開放式系統設計題，題目直接列出十個必須依序討論的技術面向，每項 5 分。沒有逐項回應就拿不到分數。

OS 與計組的比重：計組 50%（第 1 題）、OS 50%（第 2 題）。

第 1 題：CNN 矩陣運算的最佳化（50%）

情境：三個 N×N 矩陣 A、B、C，元素是雙精度浮點數（每個 8 bytes）。給一段三層迴圈的矩陣乘法 C 程式，最內層敘述 (a) 是 C[x+y*N] += A[x+z*N] * B[z+y*N];

• (1) 5%｜寫出敘述 (a) 的 MIPS 組語。題目已說明三個元素已分別載入 $f4、$f6、$f8 三個浮點暫存器，所以只需要寫運算的部分。要用雙精度的浮點指令
• (2) 5%｜要加速這段運算，該最佳化 CPU 的哪些資料路徑。運算單元與資料搬移兩方面都要想到
• (3) 5%｜嵌入式處理器沒有浮點硬體時，用整數運算模擬浮點的技術叫什麼
• (4) 5%｜軟體浮點函式庫與上一小題的技術，哪個運算效率較好、為什麼。(3)(4) 要一起想，名詞答對只拿到一半，理由才是重點
• (5) 10%｜單核嵌入式處理器常支援哪一類指令來利用這段程式的資料層平行？請用該類指令改寫程式。改寫時要說清楚迴圈怎麼調整、哪些純量運算被什麼取代
• (6) 5%｜能同時容納三個矩陣且無衝突失誤的最小 L1 資料快取容量（要取 2 的冪）。三個矩陣都要算進去，最後取 2 的冪那一步最容易漏
• (7) 5%｜改寫成分塊（blocked）版本時，能讓三個子矩陣塞進 16 KB 資料快取的最大子矩陣邊長 M。列出不等式再解，注意 M 要是整數

第 2 題：鍵值儲存的作業系統設計（50%）

情境：一個鍵值（KV）儲存系統，提供 PUT(x,v)、v=GET(x)、SCAN(x1,x2) 三個 API。系統有 x 的揮發性記憶體與 y 的持久儲存，且 x ≪ y。工作負載可能是隨機存取或循序存取、三種操作可並行執行、KV 資料總量可能大於 x、系統可能隨時故障但要能復原已提交的 PUT。

題目要求「依序」討論以下十項技術如何最佳化延遲與吞吐量，每項 5 分：

1. In-memory indexing
2. In-disk indexing
3. Caching
4. Paging
5. Batched I/O
6. Multithreading and thread scheduling
7. Shared memory and consistency
8. Encoding/Decoding
9. File system block layout
10. File system compaction

作答要扣住情境裡的每一個條件：

• SCAN 是範圍查詢，這會限制索引結構的選擇
• 資料量大於記憶體，要討論記憶體與磁碟之間怎麼分工
• 三種操作可並行，要討論同步與一致性
• 「系統可能隨時故障但要能復原已提交的 PUT」 是一個必須正面回應的約束，沒談到持久性機制會被扣分
• 隨機與循序兩種存取模式的最佳設計不同

第 10 項的「compaction」是關鍵字，它暗示了一整類適合寫入密集工作負載的儲存結構。

這份考卷的難點

1. 第 2 題是 50 分的開放設計題，而且題目指定了十個面向。 這種題目沒有標準答案，給分完全看論述的完整度與是否真的扣住 KV 儲存的情境。只寫出「用快取可以加速」這種泛泛之論拿不到分數，每一項都要講到「在這個情境下為什麼要這樣設計、代價是什麼」。
2. 第 1(6)(7) 題的計算容易少算一個矩陣。 讀 A、讀 B、寫 C 三個矩陣都要同時塞進快取。而且 (6) 還要求「取 2 的冪」，算完之後別忘了那一步。
3. 第 1(3)(4) 題的「用整數運算模擬浮點」不是每個人都叫得出名字。 而且第 (4) 小問還要接著說明理由——名詞答對只拿到一半。
4. 全卷只有兩大題，沒有任何一題可以放棄。時間分配上，第 1 題的七個小問偏計算（可以確定拿分），第 2 題的十個面向偏論述（要控制篇幅，每項寫三到五句）。

準備建議

• 成大硬體從 110 年起明顯轉向「大題化」：110 年只有兩大題、111 年四大題、113 年起也都是少題大分。準備方式要從「刷選擇題」改成「練完整論述」
• 矩陣乘法的快取最佳化是成大的固定主線（110 年第 1 題、109 年第 3 題的 GPU 矩陣乘法）。要熟悉：分塊（tiling）的容量計算、SIMD 向量化的改寫
• 第 2 題這類「依指定面向逐項論述」的開放題，準備方式是把 Silberschatz 的每一章各整理出三到五個關鍵技術名詞與一句話說明，考場上才能對著題目給的面向逐一套用
• 鍵值儲存系統雖然不是傳統 OS 課本的內容，但它把分頁、快取、批次 I/O、日誌、compaction 全部串在一起，是成大偏好的綜合題材。建議至少讀過 LevelDB／RocksDB 的架構概觀
• 沒有浮點硬體時的替代方案（第 1(3)(4) 題）：嵌入式系統的基本觀念
• 「不可使用計算機」十年不變，2 的冪次計算這類步驟都要手算