111 中興資工所考古題詳解｜硬體考點分析

題型與配分

全卷 9 頁，不得使用計算機。硬體在資訊概論的 PART II（計算機組織與作業系統），PART I 是資料結構與演算法。112 年起硬體獨立成「計算機組織與作業系統」。卷面沒有標示倒扣。

題組 4：快取、DMA、中斷與相依（8%）

• 4-I｜關於 cache block size 哪個敘述正確，選項涉及 spatial locality、cache tag 的大小、cache hit time、miss penalty
• 4-II｜哪種 DMA 傳輸模式與 interrupt 處理機制的組合能達到最高的 I/O bandwidth：Transparent DMA、Cycle-stealing、Block transfer，搭配 Polling 或 Vectored interrupts
• 4-III｜哪個關於 interrupt 的敘述為真：CPU 啟用才能處理 interrupt、loop 指令能否被 interrupt、處理器於執行新指令前檢查 interrupt、微處理器是否只有 level triggered interrupt
• 4-IV｜下列程式中 RAW、WAR、WAW dependence 的個數：

ADD R5, R3, R4
ADD R1, R4, R5
SUB R2, R5, R3
ADD R1, R1, R2

題組 5：frame、ROB 與 critical section（6%）

• 5-I｜virtual memory 環境下，執行中的 process 至少要配置幾個 page frame，由什麼決定：page size、ISA、physical memory 大小、記憶體中的 process 數
• 5-II｜關於 re-order buffer（ROB）的四個敘述哪些為真：用於 Tomasulo 演算法的 out-of-order execution、允許指令 out-of-order commit、好處包含 precise exception 與預測錯誤時的回復、通常以 CAM 型的 FIFO 實作
• 5-III｜兩個 process 的 critical section 存取方法，共享的布林變數 S1、S2 初值隨機：

P1: while (S1 == S2);  Critical Section;  S1 = S2;
P2: while (S1 != S2);  Critical Section;  S2 = not(S1);

5-III 問這個方法達成哪些性質：mutual exclusion、progress。

題組 6：page table、RAM 與 SRT 排程（8%）

• 6-I｜32 位元 virtual address、1 KB 頁面，為什麼使用單層 page table 不實際
• 6-II｜為什麼增加 RAM 通常能改善效能
• 6-III｜採 Shortest Remaining Time first（SRT），P1（執行時間 20、到達 0）、P2（25、到達 15）、P3（10、到達 30）、P4（15、到達 45），求 P2 的總 waiting time
• 6-IV｜關於 microprogram 哪個敘述為真

題組 7：執行緒、pipeline 效率與 I/O（8%）

• 7-I｜關於 user-level thread 與 kernel supported thread 的四個敘述哪些為真：context switch 的速度、一次 system call 是否 block 整個 process、能否獨立 schedule、對 kernel 是否透明
• 7-II｜400 MHz 的 pipeline 處理器，speedup 為 6、效率為 70%，pipeline 有幾級
• 7-III｜關於 I/O 方式哪個敘述為真：mapped I/O、isolated I/O、asynchronous serial transfer、synchronous serial transmission
• 7-IV｜關於 synchronous 與 asynchronous I/O 哪個敘述不是真的

題組 8：兩層快取與 pipeline（12%，每小題 4%）

• 8-I｜兩層 cache，L1、L2 與 main memory 的存取時間分別為 1 ns、10 ns、500 ns，L1 與 L2 hit rate 分別為 0.8 與 0.9，忽略 cache 內的搜尋時間，求平均存取時間
• 8-II｜五級 pipeline IF、ID、OF、PO、WO，IF、ID、OF、WO 各 1 個 clock cycle，PO 在 ADD 與 SUB 需要 1 週期、MUL 需要 3 週期、DIV 需要 6 週期，有 operand forwarding，執行 MUL R2, R0, R1、DIV R5, R3, R4、ADD R2, R5, R2、SUB R5, R2, R6 共需幾個 clock cycle
• 8-III｜16 KB、4-way set-associative cache，block 8 words，word 長 32 位元，physical address space 4 GB，求 TAG 欄位的位元數

題組 9：pipeline 與 page table（8%，每小題 4%）

• 9-I｜四級 pipeline S1–S4，給四道指令 I1–I4 在各級所需的週期數，求執行 1000 次迴圈所需的週期數
• 9-II｜處理器使用 36 位元 physical address、32 位元 virtual address，frame 4 KB，每個 page table entry 為 4 bytes，採三層 page table，virtual address 第 30–31 位元索引第一層、第 21–29 位元索引第二層、第 12–20 位元索引第三層、第 0–11 位元為 offset，求第一、二、三層 page table entry 中，用來定址下一層 page table（或 frame）所需的位元數

作答時要注意的地方

1. 卷面沒有標示倒扣。
2. 題組 8、9 的小題每題 4 分，題組 4、5、6、7 的小題每題 2 分。
3. 4-IV 要分別數 RAW、WAR、WAW 三種 dependence 的個數。
4. 5-III 兩段程式中的 S1、S2 初值是隨機指定的。
5. 6-III 問的是 P2 的總 waiting time。
6. 7-II 的 pipeline stage 數要由 speedup 與效率反推。

準備方向

• dependence 的分類：111 第 4-IV 題，110 第 4-A 題也有 RAW 與 WAR。
• DMA、interrupt 與 I/O：111 第 4-II、4-III、7-III、7-IV 題，110 第 5-B、5-D 題、112 第 11、14 題也有。
• interrupt：111 第 4-III 題與 110 第 5-B 題是同一題，選項順序不同。
• ROB 與 reservation station：111 第 5-II 題，108 第 (6) 題、114 第 20 題、115 第 4 題也有。
• critical section：111 第 5-III 題，113 第 8、9 題、114 第 13 題也有 synchronization。
• page table：111 第 6-I、9-II 題，110 第 1-C、3-A 題、112 第 25 題、115 第 15 題也有。
• 增加 RAM 為何改善效能：111 第 6-II 題與 110 第 3-C 題是同一題。
• SRT scheduling：111 第 6-III 題，110 第 1-D 題、114 第 16 題也有 preemptive scheduling。
• user-level 與 kernel thread：111 第 7-I 題，113 第 2 題、114 第 11 題也有。
• pipeline 的週期數與 speedup：111 第 7-II、8-II、9-I 題，110 第 5-A 題、113 第 13 題、115 第 1 題也有。
• 兩層 cache 與 tag：111 第 8-I、8-III 題，108 第 (7) 題、110 第 3-B、4-D 題、114 第 22 題、115 第 5 題也有。