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

題型與配分

全卷 100 分、12 頁，用 2B 鉛筆作答於答案卡。試題隨卷繳回。

111 年只寫「錯誤選項為零分、不倒扣」，112 年多了一句「整題空白，則該題零分」。

配分不平均：第 1–5 題各 2 分，合計 10 分；第 14、15、16、17 題各 10 分，合計 40 分。

單選題（1–8，26 分）

第 1–5 題共用同一段程式：compute_distance() 用雙層迴圈計算 N×N 組二維點的距離，內層每次載入 4 個 floating point、存回 1 個，N = 1024、single precision、32-byte block、write-back 與 write-allocate。

• 第 1 題（2%）｜平均 cache miss rate，cache 放不下所有資料
• 第 2 題（2%）｜算術強度：floating point 運算數除以處理器與記憶體之間傳輸的位元組數
• 第 3 題（2%）｜若所有點都已在 cache 中的算術強度
• 第 4 題（2%）｜用 roofline 估執行時間：Intel Core i7 960、4 核、single precision 尖峰 102.4 GF/s、L1 每核 32 KB
• 第 5 題（2%）｜最有效的改善方法
• 第 6 題（6%）｜memory consistency model 與 store buffer：兩個硬體 thread 各有 store buffer、支援 out-of-order execution，三個案例（Case 0 是經典的 Dekker 模式）。判斷在 TSO（Total Store Order）下哪些結果可能出現
• 第 7 題（5%）｜無 hazard 偵測也無 forwarding 時要插幾個 NOP：or x10,x3,x4、ld x5,8(x10)、ld x4,0(x2)、add x5,x10,x5、sd x5,4(x10)
• 第 8 題（5%）｜哪個敘述為真，五個選項都用了「for all programs」這類絕對語氣

複選題（9–17，74 分）

• 第 9 題（8%）｜巢狀 page table（二維位址 traversal）要幾次記憶體存取，兩種頁面大小各算一次
• 第 10 題（8%）｜三個處理器並行讀改寫同一位址 A 的所有可能值：A 初值 0，CPU0 做「store 4、load、add 4、store」，CPU1 做「load、add、store」，CPU2 做「store 6、load、add 自己、store」，沒有任何 synchronization
• 第 11 題（8%）｜看 cache 內容表回答四個位址的 hit 與否：13-bit 位址、4-way、4-byte block、8 組，位址為 0x71A、0x16E8、0x178B、0xA73
• 第 12 題（5%）｜次要儲存的配置方式：連續、鏈結、索引三種配置在 external fragmentation、循序存取、隨機存取上的優劣，FAT 屬於哪一種的變形，用 linked list 管理空閒空間的效率
• 第 13 題（5%）｜資訊安全：fork bomb 屬於哪一類攻擊、message authentication code（MAC）能提供哪些保證、buffer overflow 的後果
• 第 14 題（10%）｜兩層 paging 下哪些參數能讓外層 page table 塞進一頁：W-bit logical address、頁面 2^X bytes、外層 entry 2^Y bytes、內層 entry 2^Z bytes，給五組 (W,X,Y,Z)
• 第 15 題（10%）｜機率式的最佳 page replacement：3 頁 2 框、共 4 次參考、第一次是 P1，replacement algorithm 只知道下一次參考的機率分布。轉移機率為 P1 到 P2 0.8、P1 到 P3 0.2、P2 到 P3 0.4、P2 到 P1 0.6、P3 到 P1 0.9、P3 到 P2 0.1，要算最佳策略下第 2、3、4 次參考的期望 page fault 數
• 第 16 題（10%）｜帶「softness」的即時 scheduling：softness Si 表示任意 Si 個連續實例中只要有 1 個滿足期限即可。判斷五個關於 schedulability 的敘述，其中一項問最佳演算法是否必須交錯地滿足與錯過期限
• 第 17 題（10%）｜數出 Banker's algorithm 的 safe sequence 有幾條：7 個 thread、3 種資源，給 Available、Max、Allocation 三張表。答案寫成 1000W+100X+10Y+Z，再驗證四個係數等式

作答時要注意的地方

1. 第 1–5 題各 2 分，共用同一段程式。第 9、14、15、16、17 題各 8 到 10 分。
2. 整題空白該題零分，其餘不倒扣。
3. 第 8 題五個選項都用「for all programs」這類絕對語氣。
4. 第 9 題兩種頁面大小要各算一次。

準備方向

• roofline 全流程在 106 第 3 題、109 第 1(j) 題、112 第 1–5 題都出現。
• memory consistency model（TSO、SC）是 112 年新增的考點。110 年考 snooping coherence，111 年考 race condition 窮舉。
• 巢狀 page table 的存取次數（第 9 題）與兩層 paging 的參數條件（第 14 題），都是先算每層幾 bits 再組合。
• 帶 softness 的即時 scheduling（第 16 題），111 第 10 題考 RMS，114 第 8 題考 DM。