109 台大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 100 分、4 頁、5 大題，試題隨卷繳回。

手寫申論卷，不倒扣。Part II 卷首同樣印著「題目會刻意給多餘或缺漏的條件，必要時請自行補上假設」。

計結 50 分全部綁在同一個 CNN convolution 層情境上，從寫程式、轉 assembly、分析 pipeline hazard、加 branch prediction、loop unrolling、算 cache miss rate、blocking、multithreading、多處理器，一路到 roofline model。

Part I：計算機結構（第 1 題，50 分）

情境：一維 convolution (f*g)[n] = Σ f[n−m]·g[m]，輸入序列 f 有 N 個 32-bit floating point，kernel g 大小為 2M+1。

• (a) 5%｜寫出 C 程式實作這個 convolution，題目要求「comprehensive with sufficient comments」，註解也算分
• (b) 5%｜把 C 轉成 assembly，不需最佳化，任何 ISA 都可以，一樣要有完整註解
• (c) 5%｜分析 assembly 中的 hazard：五級 pipeline、in-order issue 循序執行、理想 CPI = 1、分支在 EX 級解析、能偵測 hazard 但不支援 forwarding
• (d) 5%｜加入 branch prediction 如何做、對效能的影響
• (e) 5%｜用 loop unrolling 減少 data hazard，要說明展開後能怎麼重排指令
• (f) 5%｜估算 M=1、4、8 時的資料 cache miss rate：direct-mapped、16 個 block、每 block 16 bytes
• (g) 5%｜能不能用 blocking（分塊）降低 miss，要重寫程式並估算效益
• (h) 5%｜同一個 kernel 套用到多個獨立輸入序列，能不能用 multithreading 加速
• (i) 5%｜不同 kernel 套用到同一個輸入序列，能不能用多處理器加速
• (j) 5%｜roofline model：算出 kernel 的算術強度（FLOPS/Byte）並估計可達效能，分別討論無 cache、加資料 cache、再加 4 倍效能的向量單元三種情況

Part II：作業系統（2–5，50 分）

• 第 2 題（20%，十個是非各 2 分）｜對就答 Yes，錯就簡述為什麼錯。十個敘述的主題如下：
• (a) thread 數量與效能的關係
• (b) frame 數與 page fault rate 的關係
• (c) time quantum 大小對平均 turnaround time 的影響
• (d) 多處理器系統與 throughput
• (e) 韌體放在 RAM 執行（shadowing）
• (f) process 合作（cooperating processes）的理由
• (g) safe state 與 deadlock state 的關係
• (h) UNIX semantics（與 session 語意對照）
• (i) 即時 scheduler 的目標
• (j) two-phase locking 協定（2PL）
• 第 3 題（5%）｜sector sparing 與 sector slipping 的差異、對 disk scheduling 的影響
• 第 4 題（10%）｜working set 模型除了防 thrashing 之外還能用在哪、怎麼用
• 第 5 題（15%）｜寫 pseudo-code 實作網路封包收集器：從多個節點隨時收到帶發送時間戳的封包（抵達順序不等於發送順序），要求每 10 秒印出「已收到的封包中發送時間最早的那一個」，而且越早印出時間戳越早的封包得分越高。題目提示「網路延遲有上界嗎？可能同時需要同步與非同步 I/O」

作答時要注意的地方

1. Part I 的十個小問環環相扣，(a) 的程式會影響 (b)、(c)、(f) 等後面的分析。
2. 第 2 題錯的敘述要寫理由，只寫 No 不給分。
3. (f) 小問的三個 M 值是 1、4、8。
4. (j) 小問要分別討論三種硬體改動。

準備方向

• 這一年計結 50 分一題到底，可以練從一段程式一路推到 roofline 的完整流程。
• roofline model 在 106 第 3 題、109 第 1(j) 題都考。109 這題問加 cache 與加向量單元對 roofline 的影響有什麼不同。
• 手寫 C 與 assembly（(a)(b) 小問），題目要求註解要充分。
• 無 forwarding 的 pipeline stall 數，110、113 年也考。
• 第 2 題的十個是非，113 年第 9 題有八題主題相同，其中四題是反過來寫。
• 全手寫、不倒扣，每一小問都要寫。