114 成大資工所考古題詳解｜硬體考點分析

題型與配分

全卷 3 頁、5 大題、100 分，不可使用計算機，於本試題紙上作答者不予計分。

卷首寫明本卷包含作業系統（Part I）與計算機組織（Part II）兩部分，並要求明確地提供並摘要答案。Part I 的答案要填進卷上示範的表格（o 代表 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。目標是在成本效益的前提下最小化平均存取延遲。

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

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

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

• 第 2(a) 題（5%）｜判斷 Pr(X_A ≥ 101 | X_A ≥ 100) = Pr(X_A ≥ 111 | X_A ≥ 110) 是否成立
• 第 2(b) 題（5%）｜判斷用 shortest-job-first scheduling 時，A 應該排在 B 前面是否成立
• 第 2(c) 題（5%）｜判斷任何 scheduling 策略下，完成兩個工作的總期望時間都是 300 是否成立

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

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

• 第 3(a) 題（5%）｜把 S 切成 disjoint blocks {s}，每個 block 當成記憶體與磁碟間的擷取單位；把含 (x,y) 的 block s 複製到記憶體 block m，再從 m 取出結果；為了效率，m 中的鍵應組織成平衡搜尋樹
• 第 3(b) 題（5%）｜WRITE() 時在 m 中更新 (x,y)，m 被替換時 write-back F 並可能覆寫原本的 s
• 第 3(c) 題（5%）｜額外建立本地檔案索引 J 來定位 (x,y) 在哪個 s 中，J 在記憶體中有副本 J\，WRITE() 時只更新 J\，判斷「J\* 與 J 可能不一致」是否成立
• 第 3(d) 題（5%）｜多個 WRITE() 可能並行寫同一個鍵，每個 WRITE() 必須同時取得 m 與 J\* 兩個鎖才能進行，提交後一起釋放，判斷這樣實作「不可能」造成 deadlock 是否成立

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

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

每題 5 分，題目明訂請提供解釋來佐證答案。

• 第 4(a) 題｜「微處理器設計中，ISA 完全隱藏了所有實體實作細節」
• 第 4(b) 題｜「多核處理器在不增加問題規模的情況下達成加速就是 strong scaling」
• 第 4(c) 題｜「多層快取設計中，第一層著重降低 miss rate，所以要用較大的區塊；第二層著重改善 miss penalty」，與 108 第 3(4) 題同一考點
• 第 4(d) 題｜「pipeline 處理器設計中，讓 ALU 指令用更少的週期是提升吞吐量的常見做法」
• 第 4(e) 題｜「加法速度高度依賴位元數，位元越多需要越多 1-bit 加法器，因而延遲越長」
• 第 4(f) 題｜「RISC-V 的 SB-format 分支有 12-bit 位址立即數、UJ-format 跳躍有 20-bit，所以程式可以在 ±2¹⁰ 字內分支、±2¹⁸ 字內跳躍」

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

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

• 第 5(a) 題（5%）｜哪些變數展現 temporal locality
• 第 5(b) 題（5%）｜哪些變數展現 spatial locality
• 第 5(c) 題（5%）｜若 cache 容量無限，需要多少個 4-word 的 cache block 才能存下所有被參考的元素
• 第 5(d) 題（5%）｜資料像影片串流一樣以可預測的模式流入時，用什麼技術把相鄰的 cache block 預先帶進 core 內的緩衝區，並詳述其運作方式

作答時要注意的地方

1. 於試題紙上作答不予計分。
2. Part I 的答案填進卷上示範的表格，o 代表 true、× 代表 false。
3. 第 2 題的 λ 寫法與一般定義不同，作答時可以註明自己的解讀。
4. 第 4 題六小題都要寫解釋，只判斷對錯不給分。
5. 第 5(d) 題明訂要詳述運作方式。

準備方向

• memory hierarchy 的成本、延遲與容量關係（114 第 1 題）。
• 指數分布的性質與 SJF（114 第 2 題）。
• 緩衝池、write-back 策略、記憶體內索引與鎖（114 第 3 題）。
• 多層 cache 各層的設計目標：108 第 3(4) 題、114 第 4(c) 題。
• strong scaling 與 weak scaling：106 第 3(1) 題、114 第 4(b) 題。
• RISC-V 的分支與跳躍範圍（114 第 4(f) 題）。
• temporal 與 spatial locality、cache block 數的計算、相鄰 block 先帶進 core 內緩衝區的機制（114 第 5 題）。
• 題目明訂要求解釋的題型：106 第 3 題、113 第 5 題、114 第 4 題。