刑事警察人員 108 年計算機概論考古題

假設處理器執行某個程式，在沒有任何記憶體停頓（stall）時，每個指 令的平均時脈數（CPI）為2。已知資料快取（data cache）的錯失率（miss rate）為3%，指令快取（instruction cache）的錯失率為1%，每一次快 取錯失的懲罰為100 個時脈週期。假設有30%的指令需要存取資料記憶 體的內容，相對之下，完全沒有快取錯失的處理器效能會是有快取錯失 時的多少倍？（20 分）

假設可以平行執行兩個10×20 整數矩陣的相加，接著還要循序執行20 次整數的相加。使用20 個處理器的時候，相對於只使用一個處理器， 可以得到多大的增速（speedup）？（20 分）

針對下列的組合語言程式 sub $3, $4, $5 //暫存器3 = 暫存器4 - 暫存器5 sub $1, $2, $3 說明：有或沒有管線危害（pipelining hazard）的理由。如果有，可能 是那一種危害？（10 分）是否可以利用什麼硬體的方法加速？是否可 能完全避免管線的停頓（stall）？（10 分）

針對Quicksort 演算法：請敘述如何用遞迴的方式來製作（10 分），並 且說明它的優點和缺點。請涵蓋時間複雜度，以及在什麼情況下會有 很差的效能。（10 分）

TN 代表一個程式在輸入資料的個數為N 時的執行時間。已知： T1 = 1 TN = TN-1 + N, N >= 2 請逐步推導出該程式的時間複雜度。（20 分）