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

題型與配分

全卷 100 分、5 頁、14 題。全部作答於試卷內的「非選擇題作答區」，標明題號依序作答。試題隨卷繳回。

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

Part I 內部：申論 25 分（第 1、2 題），選擇與是非 25 分（第 3–9 題）。

2018 年 1 月爆發的 Meltdown 漏洞是全卷主軸：第 1 題（13 分）印出論文摘要要求逐段解釋，第 3 題問哪顆處理器不受影響，第 10 題（25 分）從 OS 角度再問一次，相關題合計 43 分。

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

• 第 1(a) 題（2%）｜程式並行執行但不能讀別的程式的記憶體，需要什麼架構支援
• 第 1(b) 題（2%）｜為什麼 out-of-order execution 是現代處理器不可或缺的效能特徵
• 第 1(c) 題（3%）｜speculative execution 的好處與壞處
• 第 1(d) 題（3%）｜什麼會造成 exception、out-of-order execution 下現代處理器如何正確處理 exception
• 第 1(e) 題（3%）｜cache 為何重要、被 cache 的資料為何會造成可觀測的差異
• 第 2 題（12%）｜1 PB 巨量資料的叢集效能估算，四個小問，各 3%：(1) 每個運算存取 1 KB、儲存 block 1 KB、每台電腦 D 顆磁碟、每顆 250 MB/s、平均搜尋時間 5 ms，估算讀完 1 PB 的最短與最長時間　(2) 每台 8 張 GPU 透過 PCIe（16 GB/s）連接，計算時間小於傳輸時間且可重疊，求這一段的時間　(3) 跨電腦傳結果要 100 µs，求 reduction 的時間　(4) 估總時間、指出瓶頸在哪、提出硬體改善
• 第 3 題（5%，單選）｜哪顆處理器不受 Meltdown 影響
• 第 4 題（5%，單選）｜看圖判斷哪個對 NVidia GPU 業績貢獻最少，圖是 NVidia 股價對 BTC hash 率
• 第 5 題（4%，單選）｜關於 Google TPU（2016）哪個敘述是錯的
• 第 6 題（4%，單選）｜哪個效能改善技術沒有利用平行
• 第 7 題（2%，是非）｜pipeline 越長，branch prediction 是否越重要
• 第 8 題（2%，是非）｜有 data dependence 的兩道指令未必造成 data hazard。108 年第 1(b) 題考同一個觀念，寫法是「會造成 pipeline 停頓」
• 第 9 題（3%，是非）｜VIPT 的別名問題：Intel i7-6700（Skylake）L1 為 32 KB、64 B/line、8-way、4 KB 頁，問「同一筆 RAM 資料可能同時出現在不同快取槽」

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

• 第 10(a) 題（5%）｜TLB 如何把 virtual address 轉成 physical address（題目把 Meltdown 歸因於使用者與 kernel 共用 TLB 以降低模式切換延遲）
• 第 10(b) 題（6%）｜看 page table 做 address translation：16-bit virtual 與 physical address、4096 位元組頁，把 0xA12C、0x3A9D、0xB2D0 轉成 physical address
• 第 10(c) 題（4%）｜64-bit 位址、4 KB 頁時單層 page table 太大，OS 如何避免，題目要求至少兩種
• 第 10(d) 題（5%）｜在不關閉 TLB 的前提下如何防堵這個安全漏洞
• 第 10(e) 題（5%）｜user mode 與 kernel mode 的切換程序，以及 getpid() 需不需要模式切換
• 第 11 題（5%）｜Linux scheduler 用 red-black tree 改善了什麼效能、怎麼改善的
• 第 12 題（5%）｜按下滑鼠按鍵到跳出選單，相關軟體元件如何協作
• 第 13 題（5%）｜disk scheduling：FCFS 何時優於 SSTF、何時更差
• 第 14 題（10%）｜用 binary semaphore（mutex）實作 counting semaphore，題目要求寫得越完整越好。這是全卷唯一要寫程式碼的題目

作答時要注意的地方

1. 第 3、4、5 題連續三題是時事題，合計 14 分。
2. 第 9 題要用題目給的 cache 參數與頁大小作判斷。
3. 第 2 題問的是最短與最長時間兩個數字。
4. 第 14 題要手寫 counting semaphore。

準備方向

• 台大硬體常把當年的熱門技術整卷化：107 年是 Meltdown 與 Spectre，109 年是 CNN convolution 層，113 年是 LLM 與 MLPerf，115 年是 AI 與安全關鍵系統。
• Meltdown 與 Spectre 可以從兩個角度準備：架構角度（out-of-order execution、speculative execution、precise exception、cache side channel），OS 角度（TLB、page table 隔離的修補方式）。
• VIPT 的別名條件，107 第 9 題考，111 第 14 題、114 第 14–15 題再考。
• 效能估算題（第 2 題）：磁碟 bandwidth 與 seek、PCIe bandwidth、網路延遲各階段的時間。106 第 1、6 題與 110 年是同一類。
• 107 第 8 題寫「未必造成 data hazard」，108 第 1(b) 題寫「會造成 pipeline 停頓」，同一個觀念說法相反，是非題每個字都要看。
• 手寫 synchronization primitive（第 14 題），mutex、counting semaphore、condition variable 互相實作。
• 全手寫、不倒扣，每題都要寫。