109 台大資工所硬體考點分析
計結 50 分整段是一題——用 CNN 卷積層從寫 C、轉組語、分析危障一路問到 roofline。OS 段則是十個是非加三題申論。
題型與配分
科目：計算機結構與作業系統（B），題號 406、節次 2，全卷 100 分、4 頁、5 大題。試題隨卷繳回。
| 區段 | 題號 | 配分 | 形式 |
|---|---|---|---|
| Part I：Computer Architecture | 1 | 50% | 整段只有一大題，分 (a)–(j) 十個小問，每問 5 分 |
| Part II：Operating System | 2–5 | 50% | 是非說明 10 小題（20 分）＋申論 3 題（30 分） |
手寫申論卷、不倒扣。 Part II 卷首同樣印著「題目會刻意給多餘或缺漏的條件，必要時請自行補上假設」——連續第四年出現。
這是台大硬體十年裡結構最集中的一份：計結 50 分全部綁在同一個 CNN 卷積層情境上，從寫程式、轉組語、分析管線危障、加分支預測、迴圈展開、算快取失誤率、blocking、多執行緒、多處理器，一路做到 roofline model。前面小問答錯會連累後面。
Part I：計算機結構（第 1 題，50 分）
情境：一維卷積 (f*g)[n] = Σ f[n−m]·g[m]，輸入序列 f 有 N 個 32-bit 浮點數，卷積核 g 大小為 2M+1。
- (a) 5%｜寫出 C 程式實作這個卷積，題目要求「comprehensive with sufficient comments」——註解也算分。邊界（n−m 超出範圍）怎麼處理要自己定並寫出來
- (b) 5%｜把 C 轉成組合語言，不需最佳化，任何 ISA 都可以，一樣要有完整註解
- (c) 5%｜分析組語中的危障：五級管線、循序發射循序執行、理想 CPI = 1、分支在 EX 級解析、能偵測危障但不支援 forwarding。「無 forwarding」與「分支在 EX 解析」這兩個條件決定了資料危障與控制危障各停幾拍，要分開數
- (d) 5%｜加入分支預測如何做、對效能的影響。要針對這支程式的分支特性（迴圈分支）來討論，不要只寫泛論
- (e) 5%｜用迴圈展開減少資料危障，要說明展開後能怎麼重排指令
- (f) 5%｜估算 M=1、4、8 時的資料快取失誤率：直接對映、16 個區塊、每區塊 16 bytes。要自己推出快取能裝多少個 float、g 在三種 M 下各有多大，再判斷 f 與 g 會不會互相衝突。三個 M 值是刻意挑的，分別落在不同的情況
- (g) 5%｜能不能用 blocking（分塊）降低失誤，要重寫程式並估算效益
- (h) 5%｜同一個核心套用到多個獨立輸入序列，能不能用多執行緒加速。考工作之間有沒有相依
- (i) 5%｜不同核心套用到同一個輸入序列，能不能用多處理器加速。與 (h) 對照，這次共享的是輸入資料，要討論共享對快取的影響
- (j) 5%｜roofline model：算出卷積核的算術強度（FLOPS/Byte）並估計可達效能，分別討論無快取、加資料快取、再加 4 倍效能的向量單元三種情況。三種改動影響的是 roofline 圖上不同的東西——有的移動的是 kernel 的點、有的移動的是屋頂，要分清楚
Part II：作業系統（2–5，50 分）
- 第 2 題（20%，十個是非各 2 分）｜對就答 Yes，錯就簡述為什麼錯。十個敘述涵蓋的考點：
- (a) 執行緒數量與效能的關係
- (b) 頁框數與頁錯誤率的關係（考 Belady's anomaly 的適用範圍）
- (c) 時間量子大小對平均周轉時間的影響
- (d) 多處理器系統與吞吐量
- (e) 韌體放在 RAM 執行（shadowing）
- (f) 程序合作（cooperating processes）的理由
- (g) safe state 與 deadlock state 的關係
- (h) UNIX 語意（與 session 語意對照）
- (i) 即時排程器的目標是什麼
- (j) 兩階段鎖定協定（2PL）保證了什麼、沒保證什麼
- 這十個敘述裡有好幾句是「前半對、後半多加了一個條件」，要讀到句尾才能判斷。錯的要寫理由，只寫 No 不給分
- 第 3 題（5%）｜sector sparing 與 sector slipping 的差異、對磁碟排程的影響。兩者處理壞扇區的方式不同，對「邏輯上相鄰的扇區在實體上是否仍相鄰」的影響也不同
- 第 4 題（10%）｜工作集模型除了防輾轉之外還能用在哪、怎麼用。開放題，要先抽象出工作集模型的核心概念，再套到其他領域
- 第 5 題（15%）｜寫虛擬碼實作網路封包收集器：從多個節點隨時收到帶發送時間戳的封包（抵達順序不等於發送順序），要求每 10 秒印出「已收到的封包中發送時間最早的那一個」，而且越早印出時間戳越早的封包得分越高。題目提示「網路延遲有上界嗎？可能同時需要同步與非同步 I/O」——考資料結構的選擇與「等待」和「即時」之間的取捨，提示本身就是評分重點
這份考卷的難點
- Part I 的十個小問環環相扣。 (a) 的 C 程式寫錯，(b) 的組語、(c) 的危障分析、(f) 的快取失誤率就全部跟著錯。這是台大硬體十年裡「一錯連錯」風險最高的設計。
- (f) 小問要自己推出快取容量與資料重用的關係。 題目只給區塊數與區塊大小，三個 M 值分別對應什麼情況要自己推，推錯一步三個失誤率全錯。
- (j) 小問要同時討論三種改動，而且三者在 roofline 圖上的效果不一樣。只答「效能變 4 倍」一定失分。
- 第 2 題有兩個敘述最容易被直覺帶偏：頁框數與頁錯誤率、2PL 的保證範圍。把「可序列化」與「無死結」混為一談是常見的錯。
準備建議
- 台大硬體 109 的形式最極端：50 分一題到底。 準備時要練「從一段程式一路推到 roofline」的完整鏈路，而不是零散背概念
- roofline model 是台大硬體的招牌，106 第 3 題、109 第 1(j) 題都考，而且 109 這題要討論「加快取」與「加向量單元」對 roofline 的不同影響。要能在圖上畫出每一種改動移動的是哪個東西
- 手寫 C 與組語（(a)(b) 小問）要練到能在考場上寫出有註解的完整程式。台大會直接給「註解要充分」的要求
- 無 forwarding 的管線停頓數要能算：載入後立刻使用、分支在 EX 解析各要停幾拍。110、113 年也考
- 第 2 題的十個是非是送分題（20 分），全部出自 Silberschatz 正文。陷阱都在句尾多加的那個條件
- 全卷不倒扣、全手寫，每一小問都要寫。即使 (a) 的程式寫不完整，(c) 之後仍可以用自己寫的版本繼續分析，不要空著