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

題型與配分

全卷 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%）｜cache 設計的取捨計算：五級 MIPS，各級延遲 IF 150／ID 100／EXE 50／MEM 200／WB 100 ps，完美 cache 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）划不划算
• 第 2 題（5%）｜stride prefetch 對哪種程式有效：Code A 是 array 循序存取、Code B 是 linked list traversal
• 第 3 題（5%，多選無部分分數）｜roofline model：尖峰 bandwidth 16 GB/s、尖峰 floating point 16 GFLOPs/s。問軟體 prefetch、loop unrolling、SIMD、改寫程式提升 locality 哪些有效
• 第 4 題（5%，多選無部分分數）｜高資料層平行的架構特徵：SIMD、SIMT、VLIW、SMT、向量指令延伸五選
• 第 5 題（5%）｜register 數量對指令編碼的影響：MIPS 32-bit 指令、32 個 register，若增加到 128 個 register，R-type 需要幾個位元。第二問是更多 register 能不能縮小 assembly 程式
• 第 6 題（8%）｜SPECint2006 的兩機比較：給 12 個 benchmark 在 Intel 與 AMD 機器上的執行秒數與 SPEC ratio。(a) 哪台快、快多少，必須寫出計算過程　(b) 挑出值得最佳化的 benchmark 並提出架構或編譯器的最佳化建議
• 第 7 題（9%）｜把雲端儲存當手機記憶體的延伸（CME cache）設計題，六個小問：(a) CME cache 與晶片內 cache 有何不同　(b) block size 該多大　(c) prefetch 政策　(d) 該用 fully associative、set associative 還是 direct-mapped　(e) 若用 set associative，提出比 LRU 更好的 replacement algorithm 並說明理由　(f) tag 該用什麼
• 第 8 題（8%）｜分支的四種分類：條件與無條件、直接與間接。(a) 為每一類舉一個會讓編譯器產生該分支的 C 語法結構　(b) 哪一類最好預測、哪一類最難　(c) 預測間接分支用什麼硬體結構

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

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

• 第 9(a) 題（5%）｜Intel Edison 上跑 Linux，雙核 Atom、1 GB 記憶體，每個 process 至少要 100 MB。已有 10 個 process 卻還能再開新 process 而不 OOM，為什麼？要說出機制名稱並說明位址如何被轉換
• 第 9(b) 題（5%）｜C 編譯器產生的 process 記憶體空間分成哪些區段，各存什麼
• 第 9(c) 題（5%）｜Arduino MEGA2560 只有 256 KB Flash 與 8 KB SRAM，每個函式要 50 KB 的程式碼與變數。能不能部署 10 個函式
• 第 10 題（5%）｜看程式碼回答 signal handling：程式在第 18 行執行 a = *(int *)0;。(a) 第 18 行之後接下來三個 program counter 是哪幾行　(b) system call 被 signal interrupt 後會不會恢復，以及 OS 如何處理
• 第 11 題（5%）｜多 process 與 multithreading 下的資料傳遞：第一段測量的車流資料要送到第二段
• 第 12 題（8%）｜低階鎖的實作取捨：硬體解法（test-and-set、compare-and-swap、關 interrupt）對軟體解法（Peterson、Dekker），以及單處理器與多處理器環境下各自的優缺點
• 第 13 題（9%）｜Linux 描述裝置的三種方式：/dev 的 devfs、/sys 的 sysfs、Device Tree 的差異與使用時機
• 第 14 題（8%）｜開放式系統設計題：集中式伺服器、去中心化分散式、混合式三種架構，在最低預算、最高安全、最短 waiting time 三個目標下要怎麼設計。題目給的提示是 scheduling、reaching consensus、memory、security、storage、communication

作答時要注意的地方

1. 第 6(a) 題明訂不寫計算過程只能拿部分分數。
2. 第 9 題三個小問的平台不同，(c) 的平台是 8-bit 微控制器。
3. 第 14 題是 8 分的開放設計題，題目列出的六個面向是提示。
4. 第 3、4 題是多選，無部分分數。

準備方向

• 106–109 全部是手寫申論，要練寫出推導過程與自己補假設。106 與 108 的卷首都明說題目會給多餘或缺漏的條件。
• Part I 的計算題有三塊：cache 設計的取捨計算（第 1 題）、效能比較與平均（第 6 題）、指令編碼位元數（第 5 題）。這三塊在 107–111 反覆出現。
• roofline model 與 SIMD／SIMT／VLIW／SMT 的分類（第 3、4 題）。roofline 在 109、112、113 還會再考，110 第 8 題問到 SMT 與向量指令。
• 分支的四種分類要各舉一個 C 語法例子。
• OS 段用單一情境串起六題，106–109 都這樣出。
• signal handling 的執行流（第 10 題）。
• 不倒扣，每題都要寫。