115 交大資工所硬體考點分析

題型與配分

科目：計算機系統（含作業系統及計算機組織）（8103），系所班別「資訊聯招」，考試日期 115 年 2 月 4 日第 3 節，全卷 100 分、12 頁、35 題。不可使用計算機、請用答案卡作答。

計分規則改回 106–109 的版本：答錯一個選項倒扣 2 分，但下限回到「該題 0 分」。110–114 是「答錯 −1、扣至整科 0 分」。

實質影響：單一選項的懲罰變重（要 2/3 以上把握才值得勾），但一題最多只扣到 0，不會侵蝕其他題。

OS 與計組的比重：OS 50%（第 1–10 題與題組 A、B）、計組 50%（第 11–20 題與題組 C、D）。

這一年的計組段大幅轉向 AI 加速器：第 11 題（tokens/sec、NVLink、Infinity Fabric）、第 20 題（roofline 比較兩台機器）、題組 C 整組四小題全部是 GPU/TPU 的系統層設計。

複選題（1–20，80 分）

作業系統（1–10）

• 第 1 題（4%）｜動態載入——四個選項涵蓋 常式在被呼叫前放在哪裡、以什麼格式、它相對靜態載入在記憶體利用率上的優勢從何而來、實作它需不需要核心支援、兩者在大型應用的啟動速度比較。「需不需要核心支援」是全題的判斷點
• 第 2 題（4%）｜軟體陷阱與硬體中斷的差異——四個選項涵蓋 兩者各在什麼時機被處理（指令邊界還是指令執行中）、能不能用中斷旗標遮蔽、同步與非同步的歸屬、系統呼叫是用什麼機制實作的。後兩項都用了「只」「絕不」這類絕對字眼，要優先檢查
• 第 3 題（4%）｜多層頁表——四個選項涵蓋 單層頁表要求的記憶體是連續還是不連續、多層是不是「不論稀疏或密集」都比較省、它省記憶體的機制、它在 TLB 失誤時的效能代價。第二項要想清楚多層頁表的優勢在什麼條件下成立
• 第 4 題（4%）｜多執行緒程序中的 fork() 與 exec()——四個選項涵蓋 fork() 會複製父程序的「所有」執行緒還是只複製呼叫者那一條、fork 當下別的執行緒持有鎖會造成什麼後果、fork 與 exec 之間為何不能亂呼叫函式（async-signal-safe）、exec() 對記憶體空間與執行緒脈絡的處理。第一項與第四項是全題的兩個判斷點
• 第 5 題（4%）｜輾轉、工作集、置換與 COW——四個選項涵蓋 輾轉的症狀為何會誤導排程器使情況惡化、Belady's anomaly 在 FIFO 與 LRU 上的可能性、COW 下共享頁初始被標記成可讀寫還是唯讀、工作集總和超過可用頁框時 OS 會怎麼做。COW 那一項要想清楚寫入要怎麼被「偵測」到
• 第 6 題（4%）｜CPU 排程——四個選項涵蓋 非搶占 SJF 的周轉時間會不會隨到達率變化、同時到達時 SJF 與 FIFO 的比較、RR 與可搶占 SJF 在「平均回應時間」上的比較、MLFQ 的飢餓問題怎麼緩解。要分清每種演算法各自最佳化的是哪一個指標
• 第 7 題（4%）｜原子性違反（atomicity violation）的程式碼模式：給四段程式，要挑出哪些真的有原子性違反。判準是「多個操作本應不可分割，卻可能被其他執行緒插入」。要特別留意用了什麼鎖保護什麼變數，以及檢查與更新之間有沒有空隙
• 第 8 題（4%）｜自旋鎖的實作：要判斷四段程式碼是否正確，分別是 TestAndSet、CompareAndSwap、用 LoadLinked／StoreConditional 寫的 lock()、以及 FetchAndAdd。檢查重點只有兩個：每個原語「該回傳舊值還是新值」、以及迴圈的「繼續等」與「return」有沒有寫反。四個原語的標準實作要能默寫，才有辦法逐段比對
• 第 9 題（4%）｜用 strace 判讀 cat 的系統呼叫——四個選項分別問 第一個 open 的回傳值（要記得哪幾個 fd 已被預先佔走）、第一個 read 讀到幾個位元組（別漏掉換行符）、write 的第一個參數是什麼、值是多少、第二個 read 的回傳值。只要對 fd 與位元組數有概念就答得出來，是全卷最好拿的 4 分
• 第 10 題（4%）｜磁碟效能——四個選項涵蓋 由 RPM 換算每轉幾毫秒、由傳輸率換算傳一定量資料要多久、SCAN 排程器發明的目的、SCAN 能不能解決 SSTF 的飢餓問題。前兩項是純單位換算，一定要動筆算過再判斷（RPM 是「每分鐘」、KB 與 MB 差三個數量級）

計算機結構（11–20）

• 第 11 題（4%）｜AI 加速器的效能指標與互連——四個選項涵蓋 ops/sec 適不適合當 AI 加速器的絕對指標（LLM 推論該用什麼）、MIPS 為何不公平、NVLink／Infinity Fabric 這類互連存在的理由、資料中心的實際運算資源使用率。最後一項與產業實況有關，憑直覺會判斷錯
• 第 12 題（4%）｜設計原則、基本區塊與延遲連結——四個選項涵蓋 一道 MIPS 指令體現了哪幾條設計原則、基本區塊的定義與用途、多週期指令能不能在不延長時脈週期的前提下加入指令集、延遲連結（lazy linking）那張間接表的內容如何隨時間改變
• 第 13 題（4%）｜32-bit ALU 的控制訊號（控制群組為 AInvert、BInvert、Operation[1:0]）——四個選項分別要 由一組控制訊號反推它執行哪一種運算（兩個輸入都反相時要用 De Morgan 律換算）、檢查一段偵測無號加法溢位的程式碼是否正確（注意分支條件的方向）、Set 訊號的用途與它接到哪一位元、另一組控制訊號對應的運算
• 第 14 題（4%）｜乘除法硬體的逐步追蹤：給 5-bit 的乘除法共用硬體，要追蹤 乘法做三次迭代後的暫存器值、復原法除法做四次迭代後的值、非復原除法需要幾次迭代、Booth 演算法各需幾次加法與減法。關鍵前提：這個版本的移位放在每次迭代的「最後」而不是開頭——迭代次數會因此與課本標準版不同。四小題都要實際跑一遍，是全卷計算量最大的一題
• 第 15 題（4%）｜自訂的 16-bit 浮點格式（1 符號、4-bit 指數、11-bit 尾數）——要算 最大正數、最小正非正規化數，並判斷 這個指數寬度對應的 bias 應該是多少（要用 bias 的一般公式代入指數位元數）、浮點加法該移動哪一個運算元
• 第 16 題（4%）｜三組管線設計差異會不會產生不同的「架構層結果」：互鎖 vs 完整旁路、停頓 vs 預測不跳並 flush、單一記憶體埠 vs 無結構危障。判準只有一條：這個差異是「微架構層」的還是「架構層」的
• 第 17 題（4%）｜改變單一快取參數的影響——四個選項各固定兩個參數、變動第三個，問對 每次存取要比較的 tag 數、tag 條目總數、衝突失誤、強制失誤、失誤罰則 的影響。全題的關鍵是把「每次比較的 tag 數」與「tag 條目總數」這兩個量分清楚——前兩個選項就是拿這兩者混淆
• 第 18 題（4%）｜VIPT 的免轉換條件：36-bit 虛擬、30-bit 實體、區塊 64 bytes。四個選項分別給頁面大小與關聯度求最大快取容量、一個關於「區塊偏移落在頁內偏移範圍內」的敘述、給頁面大小與快取容量反解最小關聯度、給直接對映的快取容量反解最小頁面大小。要知道 VIPT 不需要轉換的條件是什麼，第二項要檢查敘述的條件完不完整
• 第 19 題（4%）｜分支預測與條件執行——四個選項涵蓋 BTB 在哪一級被存取（以及為什麼必須是那一級）、間接分支與條件分支誰比較難預測、2-bit 預測器用的是局部歷史還是全域歷史、ARMv8 的 CSEL 如何用條件資料選擇取代控制流。第三項要分清 2-bit 預測器與相關性預測器
• 第 20 題（4%）｜用 roofline 比較兩台機器：機器 A 每週期 3 個乘法、頻寬 0.1 字/週期；機器 B 每週期 1 個乘法、頻寬 0.5 字/週期。四個選項分別問 矩陣—向量與矩陣—矩陣乘法的運算強度各隨 N 怎麼成長、N 夠大時矩陣—向量在兩台機器上各落在 roofline 的哪一段、哪一台勝出、N 夠大時矩陣—矩陣會不會變成計算受限、roofline 模型夠不夠用來比較這兩台機器。第一項要自己數清楚兩種運算的運算量與資料量

題組（21–35，20 分）

• 題組 A（21–25，5%）｜分段式分頁的完整位址轉換：13-bit 邏輯位址、實體記憶體 4 KiB、頁面 64 bytes。邏輯位址 0x16A4，卷上給段表（段基底位址）與頁表（頁框號）。
• 第 21 題｜段索引
• 第 22 題｜從段表取得的段基底位址
• 第 23 題｜線性位址
• 第 24 題｜用來查頁表的虛擬頁號
• 第 25 題｜最終實體位址
• 五個小題是一條完整的轉換鏈，前一步錯後面全錯。先確定 13-bit 位址怎麼切出段號與段內偏移
• 題組 B（26–28，5%）｜TFS 檔案系統的 inode 配置：32 個 4 KB 區塊，最後 24 塊是資料區、5 塊是 inode 表、superblock 與兩個 bitmap 各 1 塊。每個 inode 256 bytes。
• 第 26 題｜最多能管理幾個檔案
• 第 27 題｜索引 16 的 inode 在哪個 i-block
• 第 28 題｜要讀磁碟的哪個磁區——要先確定 inode 表從第幾塊開始，再算出絕對位址，最後換算成磁區號
• 題組 C（29–32，5%）｜GPU/TPU 加速器的系統層設計（全組四小題都是單選觀念題）：
• 第 29 題｜多加速器系統做頻繁的 all-reduce 時，哪個互連特性最關鍵——要想 all-reduce 的流量模式是什麼樣子
• 第 30 題｜相同總運算資源下，chiplet 設計必然引入什麼取捨——把單一大晶片拆成多顆小晶片，換來什麼、代價出在哪裡
• 第 31 題｜給尖峰算力、記憶體頻寬與 kernel 的運算強度，判斷它卡在哪一邊——roofline 模型的直接應用
• 第 32 題｜固定功耗與面積預算下，為大模型推論設計時哪項投資最直接提升端到端吞吐量——要先確認大模型推論的瓶頸落在算力還是頻寬
• 題組 D（33–35，5%）｜費氏數列遞迴的 MIPS 組語填空與機器碼：給 fib 的 C 程式、MIPS 暫存器編號表與 opcode 對照表，組語中有若干行被挖空（第 13–18 行）。要填出缺少的指令並算出機器碼。與 110 年第 12 題是同一個 fib 程式

這份考卷的難點

1. 第 20 題的運算強度成長率非常容易答錯。 要真的數出兩種運算各做多少次乘加、讀多少資料，憑印象很容易差一級。
2. 第 17 題把「tag 條目總數」與「每次比較的 tag 數」混在一起。 兩個量各由什麼決定要分清楚。
3. 第 8 題要逐段檢查同步原語的實作是否正確。 有錯的地方都只錯一行，要真的看懂語意。
4. 題組 A 是五個小題的連鎖轉換。 任何一步算錯，後面四個答案全錯，5 分歸零。

準備建議

• 115 年計分改回「答錯 −2、扣至該題 0 分」。把握低於 2/3 不要勾，但每題至少勾一個（整題未作答不給分）
• 115 年的計組段大幅轉向 AI 加速器（第 11、20 題與題組 C 合計 13 分）。116 年很可能延續，建議補齊：
• roofline 與運算強度：各種矩陣運算的運算強度如何隨 N 變化
• 加速器互連：NVLink、Infinity Fabric、bisection bandwidth、all-reduce
• chiplet 的取捨
• LLM 推論的效能指標
• VIPT 的免轉換條件（第 18 題）：台大也連考三次，是跨校共同高頻考點
• 分段式分頁的完整轉換鏈（題組 A）要練到反射
• inode 表的容量與磁區換算（題組 B）
• 同步原語的正確實作（第 8 題）：TestAndSet、CompareAndSwap、LL/SC、FetchAndAdd 四個都要能默寫
• 微架構與架構層的區別（第 16 題）是很基本但常被忽略的原則