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

題型與配分

科目：計算機結構與作業系統（B），題號 346、節次 2，全卷 100 分、12 頁——台大硬體十年來頁數最多的一份。用 2B 鉛筆作答於答案卡。試題隨卷繳回。

計分規則與 111 年有一個關鍵差異：111 年只說「錯誤選項為零分、不倒扣」，112 年多了一句「整題空白，則該題零分」——白紙黑字告訴你每一題都必須至少勾一個選項。加上不倒扣，全部作答是唯一合理的策略。

配分極度不平均：第 1–5 題各只有 2 分（合計 10 分），但第 14、15、16、17 題各 10 分（合計 40 分）。前五題花太多時間是這份卷子最大的陷阱。

單選題（1–8，26 分）

第 1–5 題共用同一段程式：compute_distance() 用雙層迴圈計算 N×N 組二維點的距離，內層每次載入 4 個浮點數、存回 1 個，N = 1024、單精度、32-byte 區塊、write-back/write-allocate。

• 第 1 題（2%）｜平均快取失誤率：快取放不下所有資料。要逐一分析內層迴圈裡每一個存取的模式：哪些是循序走訪（一條 line 能放幾個 float）、哪些在內層固定不變、輸出怎麼寫。再把五次存取平均
• 第 2 題（2%）｜算術強度：浮點運算數 ÷ 處理器與記憶體之間傳輸的位元組數。要數清楚內層每次做了幾個浮點運算，傳輸量則只算實際碰到記憶體的部分
• 第 3 題（2%）｜若所有點都已在快取中的算術強度。想想此時還剩哪些記憶體流量
• 第 4 題（2%）｜用 roofline 估執行時間：Intel Core i7 960、4 核、單精度尖峰 102.4 GF/s、L1 每核 32 KB。用第 2 題的算術強度在 roofline 上找出可達效能，再用總浮點運算數除以它
• 第 5 題（2%）｜最有效的改善方法。要先由前幾小題判斷出這個工作負載卡在哪一種瓶頸（計算受限還是頻寬受限），再挑對症的手段
• 第 6 題（6%）｜記憶體一致性模型與 store buffer：兩個硬體執行緒各有 store buffer、支援亂序執行，三個案例（Case 0 是經典的 Dekker 模式）。要判斷在 TSO（Total Store Order） 下哪些結果可能出現。關鍵是 TSO 允許哪一種記憶體操作的重排，以及 store buffer 在其中扮演的角色
• 第 7 題（5%）｜無危障偵測也無 forwarding 時要插幾個 NOP：or x10,x3,x4 → ld x5,8(x10) → ld x4,0(x2) → add x5,x10,x5 → sd x5,4(x10)。要逐一找出所有 RAW 相依與它們的距離，再依「暫存器檔能不能同週期先寫後讀」的假設補 NOP。插入 NOP 之後後面的距離會改變，要一路重新檢查
• 第 8 題（5%）｜哪個敘述為真——五個選項都用了「for all programs」這類絕對語氣。判準：這個效果是「硬體特性」還是「取決於程式行為」——只有前者才能對所有程式成立。另外要能分清區塊大小影響的是哪幾種失誤

複選題（9–17，74 分）

• 第 9 題（8%）｜巢狀頁表（二維位址走訪）要幾次記憶體存取。三個步驟：(1) 由「一個頁表裝得下幾個條目」算出每層索引幾位元、再推出共幾層（兩種頁面大小的層數不同）；(2) 關鍵洞見：每一次「客體頁表的存取」本身也是一個客體實體位址，還要再經過主機的頁表轉換；(3) 把兩個維度組合起來。這是全卷最花時間的一題，而且兩種頁面大小要各算一次
• 第 10 題（8%）｜三個處理器並行讀改寫同一位址 A 的所有可能值：A 初值 0，CPU0 做「store 4 → load → add 4 → store」、CPU1 做「load → add → store」、CPU2 做「store 6 → load → add 自己 → store」。沒有任何同步，要窮舉交錯順序
• 第 11 題（8%）｜看快取內容表回答四個位址的命中與否：13-bit 位址、4-way、4-byte 區塊、8 組。要把 0x71A、0x16E8、0x178B、0xA73 各自拆成 tag／index／offset，到表上找對應組的四路，比對 tag 與 valid 位元，命中則讀出指定位元組。這是全卷最花時間但也最確定的 8 分
• 第 12 題（5%）｜次要儲存的配置方式——涵蓋 連續／鏈結／索引三種配置在外部碎裂、循序存取、隨機存取上的優劣、FAT 屬於哪一種的變形、用鏈結串列管理空閒空間的效率。三種配置方式的優缺點要整理成對照表
• 第 13 題（5%）｜資訊安全——涵蓋 fork bomb 屬於哪一類攻擊、訊息鑑別碼（MAC）能提供哪些保證、緩衝區溢位的後果。MAC 那幾個選項是全題重點：要分清它能保證什麼、不能保證什麼
• 第 14 題（10%）｜兩層分頁下哪些參數能讓外層頁表塞進一頁：W-bit 邏輯位址、頁面 2^X bytes、外層條目 2^Y bytes、內層條目 2^Z bytes。先用 W、X、Y、Z 推出「外層頁表大小 ≤ 一頁」的一般條件，再把五組 (W,X,Y,Z) 代進去驗算
• 第 15 題（10%）｜機率式的最佳頁面置換：3 頁 2 框、共 4 次參考、第一次是 P1，置換演算法只知道下一次參考的機率分布、不知道確切是哪一頁。給定轉移機率（P1→P2 0.8／P3 0.2、P2→P3 0.4／P1 0.6、P3→P1 0.9／P2 0.1），要算出最佳策略下第 2、3、4 次參考的期望頁錯誤數。這是把頁面置換變成馬可夫決策問題，是全卷最新穎的一題。每次置換時都要比較「踢掉哪一頁」對未來期望頁錯誤的影響
• 第 16 題（10%）｜帶「softness」的即時排程：softness Si 表示任意 Si 個連續實例中只要有 1 個滿足期限即可。要判斷五個關於可排程性的敘述。先想 Si = 1 時退化成什麼標準條件，再推廣到 Si > 1 時等效利用率怎麼變。還有一項問「最佳演算法是否必須交錯地滿足與錯過期限」
• 第 17 題（10%）｜數出銀行家演算法的安全序列有幾條：7 個執行緒、3 種資源，給 Available／Max／Allocation 三張表。要數出所有安全序列的數量，答案寫成 1000W+100X+10Y+Z 再驗證四個係數等式。要用有系統的樹狀展開，每一步列出所有可執行的執行緒

這份考卷的難點

1. 第 17 題要在考場上數出安全序列的數量。 7 個執行緒的排列有 5040 種，即使用樹狀展開，也是極大的手工工作量。10 分，但可能是全卷最不划算的一題。
2. 第 15 題把頁面置換變成機率決策問題。 傳統的 OPT 假設「已知未來」，這題改成「只知道下一步的機率分布」，必須逐層算期望值。課本上找不到，只能現場推。
3. 第 6 題的 TSO 記憶體模型要知道 store buffer 會造成哪一種重排，這是 x86 記憶體模型最反直覺的一點。
4. 第 9 題的巢狀頁表要算兩種頁面大小，而且兩個維度的組合方式是最容易算錯的地方——這也正是虛擬化下 TLB 特別重要的原因。

準備建議

• 前五題各只有 2 分卻共用一段程式，而後四題各 10 分。先掃過配分再決定作答順序是這份卷子的關鍵
• roofline 全鏈路（第 1–5 題）是台大硬體最具代表性的題組，106 第 3 題、109 第 1(j) 題、112 第 1–5 題三度出現。要練到能：由存取模式 → 失誤率 → 算術強度 → roofline 上的可達效能 → 判斷該改善頻寬還是運算
• 記憶體一致性模型（TSO／SC）是 112 年新增的考點，與 110 年的窺探式一致性、111 年的競爭條件窮舉是同一條線
• 巢狀頁表的存取次數（第 9 題）與兩層分頁的參數條件（第 14 題）都是「先算每層幾 bits，再組合」的題型。位址位元切分要練到反射
• 「for all programs」這類絕對語氣（第 8 題）是高風險選項
• 整題空白該題零分、其餘不倒扣，所以每一題都要勾。即使第 17 題數不出來，把四個係數等式代幾組合理值試試也比空白好