110 成大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 2 頁、只有兩大題、100 分，不可使用計算機，於本試題紙上作答者不予計分。

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

三個 N×N 矩陣 A、B、C，元素是 double precision floating point（每個 8 bytes）。給一段三層迴圈的矩陣乘法 C 程式，最內層敘述 (a) 是 C[x+y*N] += A[x+z*N] * B[z+y*N];。

• 第 1(1) 題（5%）｜寫出敘述 (a) 的 MIPS assembly，題目已說明三個元素已分別載入 $f4、$f6、$f8 三個 floating point register
• 第 1(2) 題（5%）｜要加速這段運算，該最佳化 CPU 的哪些 datapath
• 第 1(3) 題（5%）｜嵌入式處理器沒有 floating point 硬體時，用整數運算模擬 floating point 的技術叫什麼
• 第 1(4) 題（5%）｜軟體 floating point 函式庫與 (3) 的技術，哪個運算效率較好，為什麼
• 第 1(5) 題（10%）｜單核嵌入式處理器常支援哪一類指令來利用這段程式的資料層平行，請用該類指令改寫程式
• 第 1(6) 題（5%）｜N = 64 時，能同時容納三個矩陣且無 conflict miss 的最小 L1 資料 cache 容量（要取 2 的冪）
• 第 1(7) 題（5%）｜改寫成分塊（blocked）版本時，能讓三個子矩陣塞進 16 KB 資料 cache 的最大子矩陣邊長 M

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

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

題目要求依序討論以下十項技術如何最佳化延遲與 throughput，每項 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

作答時要注意的地方

1. 全卷兩大題各 50 分，沒有選擇題。第 1 題七個小問的配分加總是 40 分，與題首標的 50% 不符，卷面如此。
2. 第 2 題十個面向每項 5 分，題目明訂要依序討論。
3. 第 1(6) 題明訂容量要取 2 的冪。
4. 不可使用計算機，2 的冪次等計算都要手算。

準備方向

• 矩陣乘法的 cache 最佳化：110 第 1 題、109 第 3 題的 GPU 矩陣乘法、113 第 6 題。
• 分塊（tiling）與 SIMD 向量化的改寫（110 第 1(5)(7) 題）。
• 沒有 floating point 硬體時以整數運算模擬 floating point（110 第 1(3)(4) 題）。
• 鍵值儲存系統：110 第 2 題、115 簡答題 2（LSM-tree）。
• paging、cache、批次 I/O、日誌與 compaction 在儲存系統中的角色。