114 成大資工所硬體考點分析

題型與配分

考試科目：計算機組織與系統，系所「電機資訊學院－資訊聯招」，日期 0210、節次 1，全卷 100 分、3 頁、5 大題。不可使用計算機、於本試題紙上作答者不予計分。

114 年首度在卷首明確寫出「本卷包含作業系統（Part I）與計算機組織（Part II）兩部分」，並要求「請明確地提供並摘要你的答案」——Part I 的答案要填進卷上示範的表格（o 代表 true、× 代表 false）。

這一年的題型很特殊：Part I 的三大題全部是「判斷 true/false」，但判斷的對象是「設計方案是否合理」而不是課本敘述——要真的推理才能作答。

Part I：作業系統（50%）

第 1 題：兩層記憶體子系統的成本效益設計（15%）

情境：兩層記憶體 A 與 B，平均存取延遲為 L_A、L_B，容量為 S_A、S_B，每位元成本為 C_A、C_B，且 C_A > C_B。處理器先讀 A，A 沒有才讀 B 並把缺的資料補進 A。目標是在成本效益的前提下最小化平均存取延遲。

• (a) 5%｜判斷 L_A > L_B 是否成立
• (b) 5%｜判斷 S_A · C_A > S_B · C_B 是否成立
• (c) 5%｜判斷「以上皆非」這一項成不成立

這題其實是在問「記憶體階層的基本前提」：從「處理器先讀 A」與「單位成本 C_A > C_B」出發，推出 A 與 B 在速度、容量、總成本上應該是什麼關係，階層設計才有意義。(b) 比較的是總成本而不是單位成本，這是最容易看錯的地方。(c) 要先對前兩小題都有把握才敢動它。

第 2 題：指數分布下的排程（15%）

情境：程序執行時間服從指數分布 f(x) = λe^−λx。程序 A 與 B 的參數題目寫成 λ_A = 100 < λ_B = 200（依上下文為平均執行時間 100 與 200），兩者都在時間 0 啟動，單處理器。

• (a) 5%｜判斷 Pr(X_A ≥ 101 | X_A ≥ 100) = Pr(X_A ≥ 111 | X_A ≥ 110) 是否成立。考指數分布最重要的機率性質
• (b) 5%｜判斷用最短工作優先排程時，A 應該排在 B 前面是否成立
• (c) 5%｜判斷任何排程策略下，完成兩個工作的總期望時間都是 300 是否成立。要想清楚「完成兩個工作的時間」指的是哪一個量，它跟平均周轉時間不同

這是成大硬體十年裡最數學的一題，也是唯一一次考機率。題目的 λ 寫法與一般定義不同，作答時可以註明你的解讀。

第 3 題：鍵值檔案的設計與同步（20%）

情境：磁碟檔案 F 存放鍵值對，提供 READ(x) 與 WRITE(x,y) 兩個 API，兩者是獨立的程序／執行緒。S 是 F 中所有鍵值對的集合。要判斷四個設計方案是否合理。

• (a) 5%｜把 S 切成互斥的區塊 {s}，每個區塊當成記憶體與磁碟間的擷取單位；把含 (x,y) 的區塊 s 複製到記憶體區塊 m，再從 m 取出結果；為了效率，m 中的鍵應組織成平衡搜尋樹。考的是緩衝池與記憶體內索引的設計
• (b) 5%｜WRITE() 時在 m 中更新 (x,y)，m 被替換時寫回 F 並可能覆寫原本的 s。考寫回策略
• (c) 5%｜額外建立本地檔案索引 J 來定位 (x,y) 在哪個 s 中，J 在記憶體中有副本 J\，WRITE() 時只更新 J\，判斷「J\* 與 J 可能不一致」是否成立。考記憶體副本與磁碟原本的一致性
• (d) 5%｜多個 WRITE() 可能並行寫同一個鍵；實作方式是**每個 WRITE() 必須同時取得 m 與 J\* 兩個鎖才能進行，提交後一起釋放。題目問「這樣實作「不可能」造成死結」是否成立。要檢查題目有沒有交代取鎖的順序**，回想死結的四個必要條件

Part II：計算機組織（50%）

第 4 題：六個是非說明題（30%）

每題 5 分，而且明訂「請提供解釋來佐證你的答案」。只判斷不解釋拿不到分。

• (a)｜「微處理器設計中，ISA 完全隱藏了所有實體實作細節」。「完全」與「所有」要特別檢查，可以想想微架構特性有沒有辦法被軟體觀察到
• (b)｜「多核處理器在不增加問題規模的情況下達成加速就是 strong scaling」。要能把 strong scaling 與 weak scaling 各寫一句
• (c)｜「多層快取設計中，第一層著重降低失誤率，所以要用較大的區塊；第二層著重改善失誤罰則」。考 L1 與 L2 各自的設計目標。與 108 年第 3(4) 題是同一個考點
• (d)｜「管線處理器設計中，讓 ALU 指令用更少的週期是提升吞吐量的常見做法」。要想清楚管線的時脈與吞吐量由什麼決定
• (e)｜「加法速度高度依賴位元數，位元越多需要越多 1-bit 加法器，因而延遲越長」。要考慮不同的加法器設計，不只有一種
• (f)｜「RISC-V 的 SB-format 分支有 12-bit 位址立即數、UJ-format 跳躍有 20-bit，所以程式可以在 ±2¹⁰ 字內分支、±2¹⁸ 字內跳躍」。要自己驗算，關鍵是 RISC-V 的立即數以什麼為單位，以及「字」與「半字」的差別

第 5 題：矩陣乘法的記憶體區域性（20%）

程式為 for(x=0;x<8;x++) for(y=0;y<8000;y++) N[x][y] = M[x][0] + N[x][y];，元素是 32-bit 浮點數、同一列的元素連續儲存。

• (a) 5%｜哪些變數展現時間區域性
• (b) 5%｜哪些變數展現空間區域性
• (c) 5%｜若快取容量無限，需要多少個 4-word 的快取區塊才能存下所有被參考的元素
• N 與 M 的存取模式完全不同，要分開算：一個沿著連續位址走、一個每次跳到不同的列
• 對 M 直接用「元素數 ÷ 每區塊元素數」是最常見的錯法
• (d) 5%｜資料像影片串流一樣以可預測的模式流入時，用什麼技術把相鄰的快取區塊預先帶進核心內的緩衝區，並詳述其運作方式。題目要求「詳述」，只寫名詞拿不到滿分

這份考卷的難點

1. 第 2 題要用機率性質回答排程問題。 這是成大硬體十年唯一一次考機率，而且這個性質對「用已執行時間預測剩餘時間」有很直接的意涵。
2. 第 1 題要反推「記憶體階層的成本效益前提」。 三個小題是 True／False 的組合判斷，而且有「以上皆非」這一項——要同時對前兩句都有把握才敢動它。
3. 第 5(c) 題的 M 不能直接除。 M[x][0] 對不同的 x 落在不同的列，要想清楚它們會不會落在同一個區塊。
4. 第 4 題的六個小題都要寫解釋。 只判斷 Correct／Incorrect 而不說明理由，依題目要求是拿不到分數的。

準備建議

• 114 年起成大硬體明確切成 Part I（OS）與 Part II（計組）各 50 分，這個結構很可能延續。分科複習時可以直接對應
• 第 4 題的六個敘述涵蓋了計組最核心的六個觀念：ISA 的抽象邊界、strong／weak scaling、L1 與 L2 的設計目標（成大在 108、114 兩年都考）、管線吞吐量、加法器設計、RISC-V 的分支與跳躍範圍
• 時間區域性與空間區域性的辨識（第 5(a)(b) 題）要能從程式碼直接看出來
• 快取區塊數的計算要注意「元素是否連續」（第 5(c) 題）
• 預取與串流緩衝區（第 5(d) 題）是成大偏好的題材（110 年第 1 題也考過類似的記憶體最佳化），要能講出運作流程
• 指數分布的性質（第 2 題）雖然只考過一次，但它跟 SJF 在實務上的困難有關，這個連結值得記住
• 成大近年都要求「寫出解釋」（114 年第 4 題、113 年第 5 題、106 年第 3 題都明訂）。只填 T／F 拿不到分數