113 中山資工所考古題詳解｜硬體考點分析

題型與配分

全卷 3 頁、7 題、100 分，考試時間 100 分鐘，不可使用計算機，全部是問答申論題。卷首註明：題目不清楚或定義不完整時，可以自行假設並在答案卷上清楚寫明。

第 1 題：Amdahl's Law 與通訊開銷（8%）

平行化應用程式時，理想 speedup 等於處理器數，但會被可平行化的比例與通訊成本限制。假設應用程式有 80% 可以平行化。

• 1.1（4%）｜忽略通訊成本，8 個處理器的 speedup
• 1.2（4%）｜處理器數每加倍一次，通訊開銷就增加原始執行時間的 0.5%，8 個處理器的 speedup

第 2 題：GPU 的吞吐量（8%）

一顆假想的 GPU：clock 2.0 GHz，有 16 個 SIMD 處理器，每個含 16 個 single precision floating point 單元，晶片外記憶體 bandwidth 600 GB/sec。

• 2.1（4%）｜不考慮記憶體 bandwidth，假設所有記憶體延遲都能被掩蓋，這顆 GPU 的尖峰 single precision floating point throughput（GFLOPS/sec）
• 2.2（4%）｜考慮記憶體 bandwidth 的限制，這個 throughput 能不能持續，清楚說明理由

第 3 題：pipeline 各級延遲（18%）

datapath 各級的延遲與處理器執行的指令比例：

• 3.1（4%）｜非 pipelining 與 pipelining 處理器的 clock cycle
• 3.2（4%）｜lw 與 beq 兩道指令在非 pipelining 與 pipelining 處理器中各自的總延遲
• 3.3（6%）｜假設沒有 stall 或 hazard，lw、sw、add、beq 四道指令在非 pipelining 與 pipelining 處理器中的總執行時間
• 3.4（4%）｜假設沒有 stall 或 hazard，資料記憶體與 Register 單元寫入埠的使用率

第 4 題：branch predictor（15%）

動態指令的類別比例：R-Type 40%、BEQ 20%、JMP 5%、LW 25%、SW 10%。branch predictor 的準確率：Always-Taken 40%、Always-Not-Taken 60%、2-Bit 80%。

• 4.1（5%）｜branch prediction 正確時不需要 stall，誤判的 stall 週期會增加 CPI，用 always-taken predictor 時，誤判造成的額外 CPI，假設分支結果在基本五級 pipeline 的 EX 級決定、沒有 data hazard、沒有使用 delay slot
• 4.2（5%）｜重做 4.1，改用 2-bit predictor
• 4.3（5%）｜用 always-taken predictor 時，如果能把一半的分支指令換成 ALU 指令，可以得到多少 speedup，假設預測正確與預測錯誤的指令被替換的機會相同

第 5 題：快取（15%）

32 位元記憶體位址的參考序列，以字位址表示：3、180、43、2、191、88、190、14、181、44、186、253。

• 5.1（9%）｜direct-mapped cache、block 兩個 word、共 8 個 block，對每個參考寫出二進位位址、tag、index，並列出是 hit 或 miss，假設 cache 一開始是空的。卷面給了一張表格，第一列範例是字位址 3、二進位 0000 0011、tag 0、index 3、Miss
• 5.2（6%）｜direct-mapped、32 KiB 資料、8-word block、32 位元位址的 cache，總共需要多少位元

第 6 題：兩種快取組態（16%）

完美 cache 的 CPI 為 2.0，clock cycle 1.0 ns，每個指令有 1.5 次記憶體參考，兩個 cache 都是 64 KB、block 64 bytes，一個是 direct-mapped、一個是 two-way set associative。CPU 速度直接取決於 cache hit 的速度，假設為了容納 set-associative cache 的選擇 multiplexer，CPU clock cycle 要拉長 1.3 倍。兩種組態的 cache miss penalty 近似為 80 ns，hit time 為 1 個 clock cycle，64 KB direct-mapped cache 的 miss rate 1.5%，同樣大小的 two-way set-associative cache miss rate 1.1%。

• 6.1（8%）｜兩種 cache 組織的平均記憶體存取時間
• 6.2（8%）｜以 CPU time 表示兩種組織的 CPU 效能

第 7 題：虛擬記憶體（20%）

• 7.1（8%）｜virtual address 42 位元、安裝的實體 DRAM 為 16 GiB、頁大小 4 KiB、PTE 大小 4 bytes，單層 page table 需要多少個 PTE，儲存 page table 需要多少 physical memory
• 7.2（12%）｜系統看到的 virtual address 串流如下，頁大小 4 KiB，TLB 為 4 個 entry 的 fully associative、true LRU replacement，若頁必須從磁碟載入，就把下一個最大的頁號遞增。位址串流為 4669、13916、…，起始 TLB 有 4 個 entry（valid、tag、physical page number 為 (1, 11, 12)、(1, 7, 4)、(1, 3, 6)、(0, 4, 9)），page table 有 12 個 entry（valid 與 physical page 號或在磁碟）。要顯示系統最後的狀態，並對每個參考列出是 TLB hit、page table hit 還是 page fault，卷面給了要填的表格

作答時要注意的地方

1. 第 3 題 18 分、第 7 題 20 分，是配分最高的兩題。
2. 卷首註明題目不清楚或定義不完整時，可以自行假設並寫明，第 2.2 題沒有給每次運算需要搬多少資料。
3. 第 5.1 題與 7.2 題在卷面都附有要填的表格。
4. 第 6 題 set-associative cache 的 clock cycle 拉長 1.3 倍。
5. 第 7.2 題規定從磁碟載入頁時，把下一個最大的頁號遞增。

準備方向

• Amdahl's Law 與通訊開銷（113 第 1 題），107 第 7 題、108 第 2 題、109 第 3 題、110 第 2.2 題、111 第 4.2 題、115 第 2.2 題也有。
• GPU throughput（113 第 2 題），108 第 5.1 題、110 第 3 題也有 GPU 或 SIMD。
• pipeline 各級延遲（113 第 3 題），108 第 3 題也有。
• branch prediction 與誤判代價（113 第 4 題），106 第 7 題考 1-bit 與 2-bit predictor，109 第 5 題、112 第 1.3 題、114 第 3 題、115 年也有。
• CPI 與指令組合（113 第 4 題），109 第 2 題、115 第 1.2、2.1 題也有。
• cache 位元數與位址追蹤（113 第 5 題），108 第 4.1 到 4.3 題、110 第 4.2 題、111 第 3 題也有。
• AMAT 與 associativity 取捨（113 第 6 題），112 第 1.2 題、115 第 6.2 題也有。
• virtual memory 與 TLB 狀態追蹤（113 第 7 題），109 第 4 題、111 第 2 題、114 第 2 題也有。