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

題型與配分

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

沒有單選題，也沒有 mod 5 的題目。

計算機組織考點（1–10，逐選項倒扣）

• 第 1 題（5%）｜32 位元、64 個 block、每 block 16 bytes、4-way set associative 的 cache：位元組位址 1200 對映到第 11 組、index 欄位 4 位元、offset 欄位 12 位元、tag 欄位 16 位元
• 第 2 題（5%）｜memory hierarchy：spatial locality 的定義、加大 block 對 miss penalty 的影響、提高 associativity 對 cache 利用率的影響、valid bit 的作用、block 是否為 cache 儲存的基本單位
• 第 3 題（5%）｜五級 MIPS pipeline 的 hazard：forwarding 傳遞資料的方向、structural hazard 的觸發條件、重排指令能否解決部分 data hazard、把 register 比較器與目標位址計算器放在 ID 級時 branch hazard 要幾個 stall、比較用 register 是緊接在前的 load 的目的 register 時要幾個 stall
• 第 4 題（5%）｜五級延遲 IF 200、ID 100、EXE 200、MEM 200、WB 100 ps：single-cycle CPU 的理想 cycle time、sw 在 single-cycle 下的執行時間、multicycle CPU 的理想 cycle time、lw 在 multicycle 下的執行時間
• 第 5 題（5%）｜16 位元電腦的 I-type 指令格式（op 5 bits、rs 3 bits、rt 3 bits、immediate 5 bits）：最多支援幾種運算、有幾個 register、immediate 欄位的 two's complement 範圍、每個 register 的長度
• 第 6 題（5%）｜動態 branch prediction：BHT 以 PC 低位元索引、prediction buffer 是否需要 tag 與位址檢查、2-bit predictor 要連錯幾次才改變、索引到錯的分支歷史造成的誤判、correlating predictor 的假設
• 第 7 題（5%）｜RISC：與 CISC 相比核心邏輯用掉的電晶體數、是否允許加大 register 組、統一指令格式與解碼複雜度、是否不適合 pipeline、addressing mode 的多寡
• 第 8 題（5%）｜Amdahl's Law：FP 運算佔 25%、平均 CPI 為 4，其他指令平均 CPI 為 1.5，改良後 FP 的 CPI 降為 2。選項涉及 FP 部分的 speedup、以 Amdahl 式子算出的總 speedup、改良前後的 CPI
• 第 9 題（5%）｜instruction-level parallelism：loop unrolling 的前提、true dependence 能否用 register renaming 解決、antidependence 的定義、loop unrolling 能否減少控制 stall、每週期發射多道指令能否降低理想 CPI
• 第 10 題（5%）｜memory hierarchy：virtual memory 採用 write-through 還是其他寫入策略、提高 associativity 能否減少 conflict miss、virtual memory 的 placement policy、頁面變大時 page table 大小的變化、write-back 時讀取 miss 是否可能產生寫入

作業系統與網路考點（11–20，全對才給分）

• 第 11 題（5%）｜決定頁面大小要考慮什麼：page table 大小、fragmentation、I/O 開銷、page fault 次數
• 第 12 題（5%）｜thread：kernel-level 與 user-level thread 的建立成本、同 process 的 user-level thread 能否有不同 scheduling priority、一條 kernel-level thread block 時是否 block 整個 process、many-to-one 模型下一條 thread blocking 時的行為
• 第 13 題（5%）｜deadlock：resource allocation graph 有 cycle 是否表示 deadlock、unsafe 狀態是否沒有任何配置順序能讓 process 完成、假裝 deadlock 不會發生是否算一種處理方式、Banker's algorithm 是否為 deadlock prevention 演算法
• 第 14 題（5%）｜container 與 virtual machine：container 是否含完整的 guest OS、同一台機器上的 container 是否共用 kernel、VM 是否以使用者空間的隔離 process 執行、container 是否比 VM 輕量
• 第 15 題（5%）｜網路：路由器能否分割 IPv6 封包、DHCP 讓主機動態取得 IP、NAT 轉換什麼位址、DNS 是否用來查本地裝置的硬體位址
• 第 16 題（5%）｜socket 通訊中，客戶端由主機指派埠號，哪些是合法的埠號指派：21、23、80、1625
• 第 17 題（5%）｜哪些不是處理 critical section 的技術：nonpreemptive kernel、preemptive kernel、spinlock、Peterson's solution、Dekker's algorithm
• 第 18 題（5%）｜TLB hit rate 90%、TLB 存取 15 ns、main memory 存取 85 ns，問 effective memory access time，選項有 108.5、100、22、176.5、32
• 第 19 題（5%）｜參考串 1 2 3 4 2 3 4 1 2 1 1 3 1 4、三個 frame，LRU 之後三個 frame 的最終內容，題目註明 FIFO queue 是 left out right in
• 第 20 題（5%）｜blocking system call：呼叫發出後應用程式是否繼續執行、是否立刻返回、執行是否被暫停、程式碼是否比 non-blocking 難懂

作答時要注意的地方

1. 前 10 題逐選項倒扣，扣到多選題 0 分為止；後 10 題全對才給分，答錯不倒扣。
2. 第 17 題問的是「不是」處理 critical section 的技術，且全對才給分。
3. 第 8 題給的 25% 是 FP 運算的指令比例。
4. 第 19 題註明 FIFO queue 是 left out right in。

準備方向

• cache 位址拆解（110 第 1 題），107 第 16 題、109 第 2 題、111 第 2 題也有。
• temporal locality 與 spatial locality（110 第 2 題），109 第 19 題、115 第 9 題也有。
• single-cycle 與 multicycle 的 cycle time（110 第 4 題），106、108、109、111、112、115 也有 single-cycle 與 multicycle。
• 動態 branch prediction（110 第 6 題），106、107、108、115 也有。
• RISC 與 CISC（110 第 7 題），109 第 15 題、111 第 13 題、112 第 5 題、115 第 1 題也有。
• Amdahl's Law（110 第 8 題），111 第 1 題、112 第 10 題也有。
• register renaming（110 第 9 題），109 第 14、20 題、111 第 14 題也有。
• 頁面大小（110 第 10、11 題），108、109、113、114 也有頁面大小與 page table 大小。
• deadlock 與 Banker's algorithm（110 第 13 題），106、108、109、113、114 也有。
• container 與 virtual machine（110 第 14 題），111 第 7 題、113 第 14 題、114 第 16 題也有。
• IPv6 封包分割（110 第 15 題），109 第 12 題也有。
• blocking system call（110 第 20 題），115 第 15 題也有 blocking I/O。
• page replacement（110 第 19 題），108、109、111、113 也有。