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

題型與配分

全卷 7 頁、20 題、100 分，禁用計算器，作答於答案卡。

卷面沒有寫「扣到該大題 0 分為止」。單選第 15–18 題的答案是 K 或 Round(K) 再 mod 5。

計算機組織考點

• 第 1 題（5%）｜Boolean algebra：X+YZ = (X+Y)(Y+Z)、(X+Y)(X+Z)、(W+Z+XY)(Z+W'+XY)、(X+Y)(Y+Z)(X+Z)、XY'Z+YZ 五個恆等式，哪些成立
• 第 2 題（5%）｜single-cycle 對 multi-cycle：single-cycle 是否為現代主流處理器採用、single-cycle 的 clock 由最長路徑決定、功能單元能否在一道指令內重複使用、multicycle 是否較有效率
• 第 3 題（5%）｜pipeline data dependence：SUB R2,R1,R3、AND R4,R2,R5、OR R7,R6,R2、ADD R8,R2,R2、SW R9,100(R2) 五道指令，問各 dependence 能否用哪條比較式偵測（如 EX/MEM.RegisterRd = ID/EX.RegisterRs）、SUB 與 ADD 的兩個 dependence 是否為 hazard、ADD 與 SW 之間是否有 data hazard
• 第 4 題（5%）｜branch prediction：1-bit predictor 的 buffer、branch prediction buffer 以位址的高位元還是低位元索引、2-bit predictor 要連錯幾次才改變、dynamic prediction 的假設、delay branch slot 能否避免 branch hazard
• 第 5 題（5%）｜instruction set 設計：Reg-Reg 架構的 CPI 變異、MIPS 的記憶體對齊要求、register indirect addressing（Add R4,(R1)）、編譯器技術與 register 數量、PC-relative 定址
• 第 14 題（5%）｜pipeline speedup：ALU 40%（4 cycles）、Branch 30%（4 cycles）、Memory 30%（5 cycles），未 pipelining clock 1 ns、pipelining clock 1.2 ns、理想 CPI = 1，問 speedup
• 第 15 題（5%）｜已知 F1(A,B,C,D) = AB'+CD 的 minterm 為 M3、M7、M8、M9、M10、M11、M15。F2 = A'B'D+CD'+A'BC'+ABD，若 F2 含 minterm M_i 則 X_i = i，否則 X_i = 0，K 為十六個 X_i 之和，求 K mod 5
• 第 16 題（5%）｜F3(A,B,C,D) = ABC'+A'CD+ABD+BCD+AC'D+ABD'+B'CD 的 essential prime implicant 個數 K，求 K mod 5
• 第 17 題（5%）｜兩台機器：A 機 2 GHz，指令數（百萬）與 CPI 為算術邏輯 8／1、載入儲存 4／3、分支 2／4、其他 4／3；B 機 2.2 GHz，算術邏輯 10／1、載入儲存 8／2、分支 2／4、其他 4／3。較慢那一台的 MIPS 為 K，求 Round(K) mod 5
• 第 18 題（5%）｜2 GHz 處理器，所有記憶體存取都 hit 時 base CPI = 4，main memory 存取時間 100 ns，一階 cache miss rate 8%；加入存取時間 20 ns 的二階 cache 後，到 main memory 的 miss rate 降為 2%。新的 CPI 為 K，求 Round(K × 8) mod 5

作業系統考點

• 第 6 題（5%）｜手持裝置的 OS 需要支援哪些：批次程式設計、virtual memory、time-sharing、interrupt-driven I/O、RAID
• 第 7 題（5%）｜硬體沒有 privileged mode 時，如何做出安全的 OS：軟體詮釋所有使用者程式、協同處理器、網路伺服器、全部以高階語言撰寫並由編譯器檢查、叢集運算
• 第 8 題（5%）｜multithreading process 中哪些程式狀態由 thread 共享：register 值、heap、全域變數、stack、區域變數
• 第 9 題（5%）｜哪些 scheduling 演算法會造成 starvation：FCFS、SJF、Round robin、Priority
• 第 10 題（5%）｜兩個雙核心處理器共四個處理器，CPU 密集應用程式只在啟動時開一個檔案輸入、結束前寫一個檔案輸出，其間完全 CPU-bound，使用 one-to-one thread 模型。(a) 輸入與輸出各開幾條 thread (b) CPU 密集部分開幾條 thread
• 第 11 題（5%）｜使用者 process 能否修改自己的 page table entries、thread 能否在處理器間遷移、dirty bit 是否用來降低頁面傳輸的開銷、test-and-set 是否為 privileged instruction
• 第 12 題（5%）｜哪些是 policy 而不是 mechanism：用 heap 存可執行 process 的 list、root 的 process priority 較高、用計時器從使用者 process 收回 core、密碼每 90 天要換
• 第 13 題（5%）｜deadlock：Banker's algorithm 是否用於 deadlock recovery、每個 process 是否必須宣告各資源的最大需求、取得所有資源的 process 是否必須在有限時間內歸還、unsafe 狀態是否沒有任何配置順序能讓 process 完成
• 第 19 題（5%）｜for (int i=0; i<3; i++) { pid_t pid = fork(); } 會產生幾個新 process
• 第 20 題（5%）｜網路 172.16.41.0/27 上有多少個 IP 位址可供主機使用

作答時要注意的地方

1. 多選第 1–13 題每選項單獨計分，答錯倒扣 1 分；單選第 14–20 題答錯倒扣 2 分。
2. 第 15–18 題的答案取 mod 5，禁用計算器。
3. 第 19 題問的是新產生的 process 數。
4. 第 15 題把 X_i 定義為 i（F2 含 minterm M_i）或 0。

準備方向

• 無 privileged mode 如何做出安全的 OS（106 第 7 題），107 第 10 題、108 第 12 題、112 第 20 題、113 第 11 題也有。
• 哪些 scheduling 演算法會造成 starvation（106 第 9 題），109 第 4 題、112 第 17 題也有。
• policy 與 mechanism（106 第 12 題），107 第 9 題、113 第 15 題、114 第 17 題也有。
• deadlock 與 Banker's algorithm（106 第 13 題），109、110、113、114 也有。
• multithreading 共享什麼（106 第 8 題），108 第 17 題也有。
• fork 產生的 process 數（106 第 19 題），111 第 4 題也有。
• single-cycle 與 multicycle（106 第 2 題），108、109、110、111、112、115 也有。
• pipeline speedup（106 第 14 題），109 第 1 題、111 第 3 題也有。
• branch prediction（106 第 4 題），107、108、110、115 也有。
• 二階 cache 與 CPI（106 第 18 題）、MIPS（106 第 17 題）。
• Boolean algebra 與 Karnaugh map（106 第 1、15、16 題），107 第 11 題也有。