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

題型與配分

科目：計算機結構與作業系統（B），題號 417、節次 2，全卷 100 分、5 頁、14 題。全部作答於試卷內的「非選擇題作答區」，請標明題號依序作答。試題隨卷繳回。

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

這一年最大的特色是「時事整卷化」：2018 年 1 月爆發的 Meltdown 漏洞成為全卷主軸，第 1 題（13 分）直接把論文摘要印上去要你逐段解釋、第 3 題問哪顆處理器不受影響、第 10 題（25 分）從 OS 角度再問一次。Meltdown 相關題合計 43 分。

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

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

• 第 1 題（13%）｜讀 Meltdown 論文摘要回答五個小問：
• (a) 2%｜程式並行執行但不能讀別的程式的記憶體，需要什麼架構支援
• (b) 2%｜為什麼亂序執行是現代處理器不可或缺的效能特徵
• (c) 3%｜推測執行的好處與壞處——壞處不只一種，這一小問是在為 Meltdown 的成因鋪路
• (d) 3%｜什麼會造成例外、亂序執行下現代處理器如何正確處理例外（考精確例外的硬體機制）
• (e) 3%｜快取為何重要、被快取的資料為何會造成可觀測的差異（考 cache side channel 的原理）
• 五個小問其實是 Meltdown 攻擊鏈的五個環節，依序答完就是一篇完整的成因說明
• 第 2 題（12%）｜1 PB 巨量資料的叢集效能估算，四個小問：
• 3%｜每個運算存取 1 KB、儲存區塊 1 KB、每台電腦 D 顆磁碟、每顆 250 MB/s、平均搜尋時間 5 ms。估算讀完 1 PB 的最短與最長時間——「最短」與「最長」分別對應哪一種存取型態是這一小問的考點
• 3%｜每台 8 張 GPU 透過 PCIe（16 GB/s）連接，計算時間小於傳輸時間且可重疊，求這一段的時間
• 3%｜跨電腦傳結果要 100 µs，求 reduction 的時間（考歸約的拓撲結構）
• 3%｜估總時間、指出瓶頸在哪、提出硬體改善
• 第 3 題（5%，單選）｜哪顆處理器不受 Meltdown 影響。考點是 Meltdown 依賴哪一種微架構特徵，再回頭看每顆處理器的排程方式
• 第 4 題（5%，單選）｜看圖判斷哪個對 NVidia GPU 業績貢獻最少：圖是 NVidia 股價對 BTC 雜湊率。要知道 2017 年加密貨幣挖礦硬體的演變
• 第 5 題（4%，單選）｜關於 Google TPU（2016）哪個敘述是錯的。考 TPU 第一代的設計取捨，數值精度是最常被問的一點
• 第 6 題（4%，單選）｜哪個效能改善技術「沒有」利用平行。四個選項要逐一歸類到指令層／執行緒層平行，「沒有」兩個字別看漏
• 第 7 題（2%，是非）｜管線越長，分支預測是否越重要。考管線深度與誤判代價的關係
• 第 8 題（2%，是非）｜有資料相依的兩道指令「未必」造成資料危障。考相依（dependence）與危障（hazard）的區別。108 年第 1(b) 題把同一句的關鍵字改掉再考一次，兩題要對照著讀
• 第 9 題（3%，是非）｜VIPT 的別名問題：Intel i7-6700（Skylake）L1 為 32 KB、64 B/line、8-way、4 KB 頁，問「同一筆 RAM 資料可能同時出現在不同快取槽」。要動手算 index 與 offset 落在虛擬位址的哪些位元，再跟頁內偏移比較——只記得「VIPT 有別名問題」這句口訣會判錯

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

• 第 10 題（25%）｜從 OS 角度看 Meltdown，五個小問：
• (a) 5%｜TLB 如何把虛擬位址轉成實體位址（題目把 Meltdown 歸因於使用者／核心共用 TLB 以降低模式切換延遲）
• (b) 6%｜看頁表做位址轉換：16-bit 虛擬與實體位址、4096 位元組頁，把 0xA12C、0x3A9D、0xB2D0 轉成實體位址。先定出頁號與偏移各佔幾位元，再查表
• (c) 4%｜64-bit 位址、4 KB 頁時單層頁表太大，OS 如何避免——題目要求至少兩種
• (d) 5%｜在不關閉 TLB 的前提下如何防堵這個安全漏洞。考 2018 年 Linux 實際採用的修補方式，以及它帶來的效能代價如何降低
• (e) 5%｜使用者模式與核心模式的切換程序，以及 getpid() 需不需要模式切換。後半題有傳統說法與現代 Linux 實作兩個層次，能講到後者是加分點
• 第 11 題（5%）｜Linux 排程器用紅黑樹改善了什麼效能、怎麼改善的。考 CFS 的資料結構與各操作的複雜度，以及它取代了什麼
• 第 12 題（5%）｜按下滑鼠按鍵到跳出選單，相關軟體元件如何協作。要講出一條從硬體中斷到應用程式的完整鏈，漏掉中間任何一層都會被扣分
• 第 13 題（5%）｜磁碟排程：FCFS 何時優於 SSTF、何時更差。兩個方向都要舉出情境，而且要點出 SSTF 本身的公平性問題
• 第 14 題（10%）｜用二元號誌（mutex）實作計數號誌，要求「寫得越完整越好」。這是全卷唯一要寫程式碼的題目。最常見的錯是只用一個 mutex——要想清楚「保護計數器」與「讓等待者阻塞」是不是同一件事

這份考卷的難點

1. 第 9 題的 VIPT 別名判斷需要動手算。 要從 cache 容量、路數、區塊大小推出位元切法，再跟頁大小比較。只記得口訣而不會算的人很容易判錯。
2. 第 2 題的最短／最長時間差距極大。 兩種極端情況的主導因素不一樣，沒意識到題目在考「哪個因素主導」的人會把兩個答案算成差不多。
3. 第 5 題的 TPU 超出一般課本範圍，要靠對 2016–2017 年硬體新聞的認識。第 3、4、5 題連續三題都是時事題，合計 14 分。
4. 第 14 題手寫計數號誌是經典但容易寫錯的題目——寫錯的版本通常會死結或讓計數器競爭，寫完要自己追一次多執行緒交錯的情況。

準備建議

• 台大硬體會把當年度的熱門技術整卷化。 107 年是 Meltdown／Spectre（43 分）、109 年是 CNN 卷積層、115 年是 AI 與安全關鍵系統。考前務必掃過該年度的重大硬體新聞
• Meltdown／Spectre 的原理要能從兩個角度講：架構角度（亂序執行、推測執行、精確例外、快取旁路）、OS 角度（TLB、頁表隔離的修補方式）。這是台大硬體最具代表性的一題
• VIPT 的別名條件要會算，不能只背結論。107 第 9 題考它，115 年第 6、7 題再考一次 VIPT
• 效能估算題（第 2 題）的固定套路：先找出各階段的時間（磁碟頻寬與 seek、PCIe 頻寬、網路延遲），再判斷哪個主導，最後提出改善。106 第 1、6 題與 110 年也是同一類
• 第 8 題與 108 年第 1(b) 題是「同一句話改一個字」。台大很愛用這種改字陷阱，是非題每個字都要看
• 手寫同步原語（第 14 題）建議把 mutex、counting semaphore、condition variable 三者互相實作各寫過一次
• 全卷不倒扣、全手寫，所以每一題都要寫滿。申論題的分數給在論述的完整度，寫得出架構就有分