106 台大資工所硬體考點分析

題型與配分

科目：計算機結構與作業系統（B），題號 412、節次 2，全卷 100 分、5 頁、14 題。試題隨卷繳回。

這是一份全手寫的申論卷，沒有答案卡、沒有倒扣。 第 6(a) 題明訂「You must show your calculation, without showing the calculation, your answer can only receive partial credits」——只寫答案會被扣分。

Part II 卷首印著一句很特別的警告：「NOTE that in the question, it is intended to provide redundant or miss certain assumption to disguise you. Please make your own assumption if necessary」——題目會刻意給多餘或缺漏的條件，要自己補假設並寫出來。這句話在 108 年又出現一次。

Part I：計算機結構（1–8，50 分）

• 第 1 題（5%）｜快取設計決策的取捨計算：五級 MIPS，各級延遲 IF 150／ID 100／EXE 50／MEM 200／WB 100 ps，完美快取 CPI = 1，miss penalty 200 cycles，I-cache miss 5%、D-cache miss 10%、load/store 佔 35%。問把 D-cache 從 32 KB 加到 512 KB（miss 降到 5%，但 MEM 級延遲升到 250 ps）划不划算。這是「時脈變慢但 CPI 變好」的典型 trade-off 題，陷阱是只比 CPI 或只比時脈——兩邊都要算完、比的是每指令平均時間
• 第 2 題（5%）｜stride prefetch 對哪種程式有效：Code A 是陣列循序存取、Code B 是鏈結串列走訪。考點是 stride 預取器靠什麼特性運作，以及指標追逐（pointer chasing）的位址規律性
• 第 3 題（5%，多選無部分分數）｜roofline model：尖峰頻寬 16 GB/s、尖峰浮點 16 GFLOPs/s。問軟體預取、迴圈展開、SIMD、改寫程式提升區域性哪些有效。關鍵是先判斷應用落在 roofline 的哪一段，四個選項各自對應的是哪一條天花板要分清楚
• 第 4 題（5%，多選無部分分數）｜高資料層平行的架構特徵：SIMD、SIMT、VLIW、SMT、向量指令延伸五選。考的是資料層／指令層／執行緒層三種平行的分類，VLIW 與 SMT 最容易被歸錯類
• 第 5 題（5%）｜暫存器數量對指令編碼的影響：MIPS 32-bit 指令、32 個暫存器，若增加到 128 個暫存器，R-type 需要幾個位元？別忘了 R-type 有三個暫存器欄位。第二問「更多暫存器能不能縮小組合語言程式」要從 spill／reload 與指令格式兩個角度論述
• 第 6 題（8%）｜SPECint2006 的兩機比較：給 12 個 benchmark 在 Intel 與 AMD 機器上的執行秒數與 SPEC ratio。(a) 哪台快、快多少（用哪一種平均是考點，而且必須寫出計算過程）；(b) 挑出值得最佳化的 benchmark 並提出架構或編譯器的最佳化建議
• 第 7 題（9%）｜把雲端儲存當手機記憶體的延伸（CME cache）設計題，六個小問：(a) CME cache 與晶片內快取有何不同、(b) 區塊大小該多大、(c) 預取政策、(d) 該用全關聯／組相聯／直接對映、(e) 若用組相聯，提出比 LRU 更好的置換演算法並說明理由、(f) tag 該用什麼。這題是把「快取原理」搬到完全不同的尺度上重新推導，是全卷最能鑑別理解深度的一題——每一小問都要回到「命中代價與失誤代價的比例變了」這件事來論證
• 第 8 題（8%）｜分支的四種分類：條件／無條件 × 直接／間接。(a) 為每一類舉一個會讓編譯器產生該分支的 C 語法結構、(b) 哪一類最好預測、哪一類最難、(c) 預測間接分支用什麼硬體結構。「條件間接」這一格最難舉例

Part II：作業系統（9–14，50 分）

情境：為台北市 2,500 個路口設計 IoT 交通號誌系統（TaipeiBox），要在最低預算下最小化車輛與行人的等待時間。

• 第 9 題（15%）｜兩種硬體平台的取捨，三個小問：
• (a) 5%｜Intel Edison 上跑 Linux，雙核 Atom、1 GB 記憶體，每個程序至少要 100 MB。已有 10 個程序卻還能再開新程序而不 OOM，為什麼？要說出機制名稱並說明位址如何被轉換
• (b) 5%｜C 編譯器產生的程序記憶體空間分成哪些區段，各存什麼
• (c) 5%｜Arduino MEGA2560 只有 256 KB Flash 與 8 KB SRAM，每個函式要 50 KB 的程式碼與變數。能不能部署 10 個函式？陷阱在平台差異——要注意這顆微控制器有沒有 (a) 小題所依賴的那套硬體
• 第 10 題（5%）｜看程式碼回答信號處理：程式在第 18 行執行 a = *(int *)0;（解參考空指標）。(a) 第 18 行之後接下來三個 program counter 是哪幾行，要追出會觸發哪個信號、控制流跳到哪裡；(b) 系統呼叫被信號中斷後會不會恢復，要說明恢復程序或 OS 如何處理
• 第 11 題（5%）｜多程序與多執行緒下的資料傳遞：第一段測量的車流資料要送到第二段。考兩種模型的位址空間差異，以及各自要付出的代價（IPC 或同步）
• 第 12 題（8%）｜低階鎖的實作取捨：硬體解法（test-and-set、compare-and-swap、關中斷）對軟體解法（Peterson、Dekker），以及單處理器與多處理器環境下各自的優缺點。「關中斷」在兩種環境下的適用性是這題的核心
• 第 13 題（9%）｜Linux 描述裝置的三種方式：/dev 的 devfs、/sys 的 sysfs、Device Tree 的差異與使用時機。三者分別是「裝置節點」「核心物件視圖」「開機時的硬體描述」這三個不同層次，容易混在一起講
• 第 14 題（8%）｜開放式系統設計題：集中式伺服器、去中心化分散式、混合式三種架構，在「最低預算、最高安全、最短等待時間」三個目標下要怎麼設計。題目直接給提示「scheduling, reaching consensus, memory, security, storage, communication」——這六個面向就是評分面向

這份考卷的難點

1. 第 7 題把快取原理搬到雲端尺度重新推導。 沒有標準答案可背，必須真的理解晶片內快取的每個設計決策是基於什麼樣的延遲比例做出來的——比例一變，每個決策都要重新想。
2. 第 6(a) 題的平均方式。 用錯平均會得到不同的結論，而且題目明訂不寫計算過程只能拿部分分數。
3. 第 9(c) 題會被前兩小問帶著走。 前兩小問都在談 Linux 平台上的記憶體管理，第三小問把場景換到 8-bit 微控制器——沒看出平台差異的人會用同一套說法作答。
4. 第 14 題是 8 分的開放設計題，沒有標準答案，給分看論述的完整度。題目給的六個提示就是評分面向，沒有逐項回應就拿不到高分。

準備建議

• 台大硬體 106–110 全部是手寫申論，準備方式與選擇題完全不同：要練「寫出推導過程」與「自己補假設」。106 與 108 的卷首都明說題目會刻意給多餘或缺漏的條件
• Part I 的計算題有固定三塊：快取設計的取捨計算（第 1 題）、效能比較與平均（第 6 題）、指令編碼位元數（第 5 題）。這三塊在 107–110 反覆出現
• roofline model、SIMD/SIMT/VLIW/SMT 的分類（第 3、4 題）是台大硬體的招牌，110、112、113 都再考過
• 分支的四象限分類（第 8 題）要能各舉一個 C 語法例子，這是台大特有的問法
• OS 段用單一情境串起六題是台大 106–109 的固定寫法。讀題時先花兩分鐘看懂情境，後面六題會省很多時間
• 信號處理的執行流（第 10 題）建議實際寫一個 SIGSEGV handler 跑跑看，比背書有效
• 不倒扣、全手寫，所以每一題都要寫——即使只寫得出架構，部分分數也拿得到