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

題型與配分

全卷 5 頁、20 題、100 分，禁用計算器。

單選第 2、3、4、5 題的答案是 K 或 Round 後的數值再 mod 5，第 1 題直接給 CPU 使用率的數值選項。

單選題（1–5）

• 第 1 題（5%）｜degree of multiprogramming 為 6，也就是記憶體中同時有 6 個程式，每個 process 有 40% 的時間在等 I/O，問 CPU 使用率
• 第 2 題（5%）｜指令 miss rate 2%、資料 miss rate 4%、20% 的指令會存取資料、miss penalty 50 clock cycles、hit 無罰則（CPI = 1），執行 1111 道指令所需的 clock cycles 為 H，求 Round(H) mod 5
• 第 3 題（5%）｜四個 IEEE 754 single precision floating point 值：A 為最大 denormalized number、B 為最小 normalized 正數、C = −2.25、D 為正無窮大。E = A XOR B XOR C XOR D，E 中 1 的個數為 K，求 K mod 5
• 第 4 題（5%）｜16 個 word 的 2-way set associative cache，block 為 2 個 word，依序存取字位址 12, 17, 18, 16, 5, 29, 19, 12, 4, 22, 23, 24, 17, 25, 26, 27，採 LRU，hit 次數為 K，求 K mod 5
• 第 5 題（5%）｜pipeline 實作：1/4 的 load 後面緊接使用結果的指令、一半的 branch 預測錯誤並延遲 1 個週期、jump 一律延遲 1 個週期。指令組合為 load 24%、store 20%、ALU 30%、branch 20%、jump 6%，平均 CPI 為 K，求 Round(K × 234) mod 5

計算機組織考點（6–11）

• 第 6 題（5%）｜superscalar 靠硬體還是編譯器達成 instruction-level parallelism、page table 是否為 cache、TLB 是否為 cache、microprogrammed control 的主要優點是否為速度、TLB hit 但 cache miss 是否可能
• 第 7 題（5%）｜single-cycle 與 multicycle：multicycle 的 clock rate 是否較大、single-cycle 的 CPI 是否為 1、single-cycle 的 throughput 是否較大、multicycle 的 cycle time 是否由最慢的指令決定、以上全部
• 第 8 題（5%）｜add $s0,$t0,$t1 接 sub $t2,$s0,$t3：是否有 RAW hazard、是否有 WAW hazard、能否用 forwarding 解決 RAW、能否插入 bubble 解決 WAW
• 第 9 題（5%）｜分支指令與預測：MIPS 的 jump 是否為條件分支、branch target buffer 是否由編譯器用來預測、pipeline 愈長 branch prediction 是否愈重要、預測失敗時要清除指令並修正 PC
• 第 10 題（5%）｜五級 pipeline（IF、ID、EXE、MEM、WB）：理想 speedup 的上限、把分支執行從 MEM 提前到 IF 是否能解決 control hazard、各級工作量是否該不平衡、branch hazard 是否源自 data cache miss
• 第 11 題（5%）｜MIPS 指令組合 add 30%、addi 20%、beq 25%、lw 15%、sw 10%：指令記憶體的使用週期比例、資料記憶體的使用週期比例、sign-extend 電路輸入的使用週期比例、MemtoReg 訊號開啟的週期比例

作業系統考點（12–20）

• 第 12 題（5%）｜硬體沒有 privileged mode 時，如何保持 OS 隨時掌控：軟體詮釋所有使用者程式、全部以高階語言撰寫並由編譯器產生保護檢查、雲端伺服器執行程式、開放原始碼的使用者程式、ROM-based 的作業系統
• 第 13 題（5%）｜preemptive 的動態 priority scheduling：process 在 ready queue 中等待時 priority 以速率 A 變化，執行時以速率 B 變化，priority 數字愈大愈優先，進入 ready queue 時 priority 都是 0。問 A < B < 0 與 A > B > 0 各對應哪種 scheduling：RR、FCFS、SJF、LIFO、Random
• 第 14 題（5%）｜多處理器系統上用 many-to-many 模型寫的 multithreading 程式，user-level thread 數多於處理器數，kernel thread 數分別少於處理器數、等於處理器數、介於處理器數與 user-level thread 數之間、等於 2、多於 user-level thread 數時，效能有何較低的影響
• 第 15 題（5%）｜Banker's algorithm 下，哪些變更可以安全進行：增加 Available、減少 Available、增加某 process 的 Max、減少某 process 的 Max、減少 process 數
• 第 16 題（5%）｜參考串 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1，demand paging、三個 frame，LRU、FIFO、Optimal 各發生幾次 page fault
• 第 17 題（5%）｜來自不同 process 的兩條 thread 共享什麼：全域變數、heap、file descriptor、program counter
• 第 18 題（5%）｜CPU scheduling 決策發生在 process 的哪些狀態轉換：running 到 waiting、waiting 到 ready、ready 到 running、running 到「decision」狀態
• 第 19 題（5%）｜較小的頁面是否使 page table 較小、是否造成較多 TLB miss、Round robin 是否最佳化 CPU throughput、Round robin 是否可以是 preemptive
• 第 20 題（5%）｜網路：ARP 查 MAC 位址、DNS 把網域名稱轉成 IP 位址、IPSec 用於 VPN、ICMP 訊息用於診斷 IP 運作的錯誤

作答時要注意的地方

1. 多重選擇第 6–20 題答錯不倒扣，單選第 1–5 題答錯倒扣 2 分並扣到該大題 0 分為止。
2. 第 2、5 題的答案先乘上係數或四捨五入再取 mod 5。
3. 第 16 題要跑三種 replacement algorithm。
4. 第 17 題問的是「不同 process」的兩條 thread。

準備方向

• 無 privileged mode 如何做出安全的 OS（108 第 12 題），106 第 7 題、107 第 10 題、112 第 20 題、113 第 11 題也有。
• degree of multiprogramming 與 CPU 使用率（108 第 1 題）。
• cache 的 hit 次數模擬（108 第 4 題），106 第 18 題、107 第 16、18 題、109 第 2 題也有 cache 計算。
• IEEE 754（108 第 3 題），107 第 19 題、111 第 10 題、114 第 9、10 題也有。
• single-cycle 與 multicycle（108 第 7 題），106、109、110、111、112、115 也有。
• single-cycle datapath 各單元的使用比例（108 第 11 題），111 第 9 題也有 datapath 圖。
• many-to-many 模型下 kernel thread 數的效能（108 第 14 題），109 第 6 題、112 第 19 題也有。
• Banker's algorithm（108 第 15 題），106、109、110、113、114 也有。
• LRU、FIFO、Optimal 的 page fault 數（108 第 16 題），109 第 7 題、111 第 6 題、113 第 13 題也有。
• multithreading 共享什麼（108 第 17 題），106 第 8 題也有。
• 頁面大小與 page table 大小（108 第 19 題），109、110、113、114 也有。