108 中正資工所考古題詳解｜硬體考點分析

題型與配分

全卷 6 頁、9 題、100 分。答案寫在試卷（答案卷）作答區內，限用藍色或黑色筆（含鉛筆），試題須隨試卷繳還。入場後 40 分鐘內不得離場。卷面沒有倒扣規定。

第 1 題：十個單選（20%）

• 第 1(1) 題｜哪個機制可以追蹤磁碟上的空閒空間，同時還兼做其他事（FCB、Partition、FAT、Inode）
• 第 1(2) 題｜哪一種 RAID 組態提供冗餘但額外磁碟成本最高
• 第 1(3) 題｜為什麼發展 multi-level page table
• 第 1(4) 題｜Multilevel Feedback Queue 之下 CPU 時間如何在各 queue 間分配
• 第 1(5) 題｜在 virtual memory 中找空閒 frame 時，花 CPU 週期避免後續磁碟存取，哪一項值得
• 第 1(6) 題｜哪一項不是 deadlock 發生的必要條件
• 第 1(7) 題｜Shortest Run Time First scheduling 的問題
• 第 1(8) 題｜允許 preemption 的 scheduling 要付出什麼代價
• 第 1(9) 題｜Linux 的架構
• 第 1(10) 題｜sandbox 模式（sandbox mode）指的是什麼

第 2 題至第 9 題

• 第 2 題（5%）｜系統有沒有可能處於既非 deadlock、也非安全的狀態，要說明
• 第 3 題（8%）｜卷上印出 SPEC CPU 2006 中 cactusADM、libquantum、Xalan、omnetpp、hmmer、astar 六個 benchmark 的 RD／WD 存取圖，x 軸是取樣時間，y 軸是整個 address space 中的不同頁面。(a) 4%：簡述 astar 中 process 的行為。(b) 4%：簡述 cactusADM 中 process 的行為
• 第 4 題（7%）｜給一段含兩次 fork 的程式（第一次 fork 後設 c = 5，child process c += 5，parent process 再 fork 一次並 c += 10，第二次 fork 的 parent process 再 c += 5），問變數 c 有幾份不同的副本、各自的值
• 第 5 題（10%）｜給 Solaris dispatch table（priority、time quantum、time quantum expired、return from sleep）。(a) 4%：priority 10 與 55 的 time quantum 各是幾毫秒，各 2 分。(b) 3%：priority 35 的 thread 用完整個 time quantum 而沒有 blocking，新的 priority。(c) 3%：priority 35 的 thread 在 time quantum 用完前因 I/O 而 block，新的 priority
• 第 6 題（10%）｜CNN convolution：3×4 的輸入圖、2×2 的 kernel（參數 w、x、y、z），輸出 2×3 的 feature map。兩輸入 adder 延遲 D_ADD = 0.1 × D_MUL，輸入與核參數在計算前已載入，乘法與加法可以平行，求做一次 convolution 的最小延遲（以 D_MUL 表示）
• 第 7 題（10%）｜同第 6 題的 convolution，改由 CPU 計算，硬體限制每個 clock cycle 只能同時執行一次乘法與一次加法，求輸入圖改變後做一次 convolution 最少需要幾個 clock cycle
• 第 8 題（5%）｜依 IEEE 754 double precision（1 位元符號、11 位元指數、52 位元尾數）寫出 −5.0 的表示
• 第 9 題（25%）｜辨識手寫數字的 fully connected neural network：input layer 256 個節點（16×16 灰階影像，每像素 8 位元）、3 個 hidden layer（每層 16 個 neuron，含 bias 與 ReLU）、output layer 10 個節點（不含 ReLU）。(a) 算出一張 16×16 影像所需的權重與 bias 個數，以及兩者都用 IEEE 754 single precision 時所需的儲存大小。(b) 只允許 1 KByte 的 SRAM 存權重，用 direct-mapped cache 管理晶片內外的權重，一個 block 存 32 bytes，問除了 1 KByte SRAM 外還需要多少晶片內儲存（提示：cache tag）。(c) (b) 的權重 cache miss rate 與 miss 的種類（compulsory、conflict 或 capacity）。(d) 在相同成本限制下改善 (b) 的權重記憶體組織的有效方法

作答時要注意的地方

1. 全卷沒有倒扣規定，第 1 題每題 2 分。
2. 第 2 題與第 3(a)(b) 題要用文字說明，沒有數值結果。
3. 第 5 題 (b)、(c) 問的是兩種不同的情況。
4. 第 6 題指定輸入與 kernel 參數已載入，乘法與加法可以平行。

準備方向

• deadlock 的必要條件與 safe、unsafe、deadlock 的關係（108 第 1(6) 題、第 2 題），109 第 1(3) 題、110 第 4 題、112 填空第 3 題也有 Banker's 與 safe state。
• MLFQ 的 CPU 時間分配（108 第 1(4) 題），109 第 1(9) 題、113 第 1(7) 題也有。
• 為什麼發展 multi-level page table、找空閒 frame、SRTF 的問題、Linux 的架構、sandbox 模式（108 第 1(3)(5)(7)(9)(10) 題），113 年的單選題也各有一題同樣的問法；multi-level page table 在 106 第 1(8) 題、SRTF 在 107 第 1(4) 題也有，preemption 的代價（108 第 1(8) 題）在 106 第 1(3) 題也有。
• Solaris dispatch table（108 第 5 題），成大 112 第 2 題也考 Solaris dispatch table。
• CNN convolution（108 第 6、7 題算延遲與週期，109 第 9 題算 IEEE 754 數值），106 第 5、6 題、107 第 5、6 題也算 neural network 的延遲與週期數。
• IEEE 754（108 第 8 題），109 第 9 題、110 第 10 題（FP16）、112 填空第 5 題也有。
• RAID（108 第 1(2) 題），106 第 1(10) 題、112 填空第 4 題、114 填空第 8 題也有。
• fork 之後的 process 與變數副本（108 第 4 題），113 第 2 題也有。
• cache 容量與 tag 位元數（108 第 9(b) 題），114 填空第 2 題也有。