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

題型與配分

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

第 13、14 題問的是 NOT true 的敘述。

單選題（1–2）

• 第 1 題（5%）｜未 pipelining 機器 clock 9 ns，ALU 4 cycles、branch 5 cycles、memory 5 cycles，比例為 30%、30%、40%。pipelining 使 clock 多 1 ns，理想 CPI = 1，其他影響忽略，問 speedup，選項是 4.5 到 4.9
• 第 2 題（5%）｜4 KB 的 direct-mapped cache，block 4 bytes，位址 32 位元，問 tag 用幾位元

作業系統考點（3–12）

• 第 3 題（5%）｜VM 執行原生指令時，哪些指令屬於 sensitive：設定計時器、讀時鐘、清記憶體、發出 trap、關閉 interrupt
• 第 4 題（5%）｜哪些 scheduling 演算法會造成 starvation：FCFS、SJF、Round robin、Priority、Weighted fair queueing
• 第 5 題（5%）｜counting semaphore：是否本質上是整數變數、是否只透過一個標準操作存取、能否被多個 thread 同時修改、能否用來控制 critical section、是否作為單一不可 interrupt 單位執行
• 第 6 題（5%）｜多處理器上用 many-to-many 模型寫的 multithreading 程式，user-level thread 數多於處理器數，kernel thread 數分別少於處理器數、等於處理器數、介於處理器數與 user-level thread 數之間、等於 2、多於 user-level thread 數時，效能有何較低的影響
• 第 7 題（5%）｜參考串 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 1, 0, 5, 4, 6, 2, 3, 2, 3, 0, 1，demand paging、三個 frame，LRU、FIFO、Optimal 各發生幾次 page fault
• 第 8 題（5%）｜一般使用者通常不會主動察覺什麼：資源配置、互動性、連續性、回應性
• 第 9 題（5%）｜TLB 與 multi-level page table、固定 virtual address 位元數時線性 page table 大小與頁面大小的關係、time slice 愈長 RR 與 FIFO 的結果、SJF 是否可以是 preemptive
• 第 10 題（5%）｜單使用者系統是否需要 multitasking、I/O 完成後 blocked process 移到 RUNNING 狀態、32 位元 physical address 配 4 KB 頁時高 18 位元是否恰為 physical page 號、虛擬頁數是否等於 physical page 數
• 第 11 題（5%）｜二層 page table 無 TLB 時取一道指令是否恰要 3 次記憶體存取、unsafe 狀態下 OS 是否 deadlock、Banker's algorithm 是否為 deadlock avoidance 演算法、wait-for graph 是否用於 deadlock detection
• 第 12 題（5%）｜IPv6：標頭長度是否為 IPv4 的四倍、是否不支援 broadcast、IPsec 是否為規格強制、路由器是否不得分割封包

計算機組織考點（13–20）

• 第 13 題（5%）｜single-cycle 與 multicycle，哪些敘述不成立：single-cycle 是否不被現代主流處理器採用、single-cycle 的 clock 是否由 shortest path 決定、功能單元能否在一道指令內重複使用、multicycle 是否較有效率、multicycle 是否較適合 pipelining
• 第 14 題（5%）｜哪些敘述不成立：write-back cache 的讀取 miss 是否可能引發寫入、write-through 是否不需要 write buffer、WAW 與 RAW hazard 能否用 register renaming 解決、distributed shared memory 是否不會造成非均勻的存取時間
• 第 15 題（5%）｜dynamic scheduling 的動機是否不含防止 out-of-order completion、分離指令與資料 cache 主要減少 data hazard、RISC 是否已過時、記憶體延遲與功耗限制是否促成單晶片多處理器
• 第 16 題（5%）｜virtual memory：address translation 是否把 virtual address 轉成 register 編號、physical address 是否為 register 位址、TLB miss 時是否仍可能在 page table 中找到、virtual page number 位元數是否必須等於 physical page 號位元數、context switch 時 OS 是否保證 P2 不能存取 P1 的 page table
• 第 17 題（5%）｜MIPS CPU 設計：forwarding 是否能部分解決 RAW hazard、branch prediction 是否防止 data hazard、pipeline 是否縮短單一指令的完成時間、beq 的分支目標位址是否在編譯時已知、pipeline 是否增加同時執行的指令數
• 第 18 題（5%）｜MIPS 的 procedure call：stack frame 的定義、frame pointer 是否存放 stack 頂端的位址、stack pointer 超出邊界時是否 stack overflow、process 結束要返回時是否呼叫 jal、beq 的第三個運算元
• 第 19 題（5%）｜記憶體與 cache：spatial locality 的定義、加大 block 是否更善用 spatial locality、write through 是否需要 dirty bit、提高 associativity 是否提高 cache 利用率、direct-mapped 的 miss rate 是否低於 fully associative
• 第 20 題（5%）｜pipeline 與平行化：loop unrolling 的目的是否為縮小程式碼、register renaming 的目的是否為提高可讀性、VLIW 一道寬指令是否發出許多相依的運算、superscalar 處理器能否同時派送多道指令、static multiple issue 是否由編譯器做許多決定

作答時要注意的地方

1. 第 3–20 題每一選項單獨計分，90 分全部在逐選項倒扣下。
2. 第 13、14 題問的是 NOT true。
3. 第 7 題的參考串有 21 個頁號。
4. 第 1 題的五個選項相差 0.1。

準備方向

• 哪些 scheduling 演算法會造成 starvation（109 第 4 題），106 第 9 題、112 第 17 題也有。
• counting semaphore（109 第 5 題），112 第 18 題也有。
• many-to-many 模型（109 第 6 題），108 第 14 題、112 第 19 題也有。
• LRU、FIFO、Optimal 的 page fault 數（109 第 7 題），108 第 16 題、111 第 6 題、113 第 13 題也有。
• 頁面大小與 page table 大小（109 第 9 題），108 第 19 題、110 第 10 題、113 第 18 題、114 第 4 題也有。
• deadlock 與 Banker's algorithm（109 第 11 題），106、108、110、113、114 也有。
• single-cycle 與 multicycle（109 第 13 題），106、108、110、111、112、115 也有。
• register renaming（109 第 14、20 題），110 第 9 題、111 第 14 題也有。
• 分離 I-cache 與 D-cache 減少哪一種 hazard（109 第 15 題），111 第 12、14 題也有。
• RISC 與 CISC（109 第 15 題），110 第 7 題、111 第 13 題、112 第 5 題、115 第 1 題也有。
• pipeline 改善的是 throughput 還是 latency（109 第 17 題），107 第 14 題、112 第 4 題也有。
• temporal locality 與 spatial locality（109 第 19 題），110 第 2 題、115 第 9 題也有。
• cache 位址拆解（109 第 2 題）與 pipeline speedup（109 第 1 題），111 第 2、3 題同型。
• IPv6（109 第 12 題），110 第 15 題也有。