112 中山資工所硬體考點分析

題型與配分

科目名稱：計算機結構【資工系碩士班甲組、乙組】，題號 434001，考試時間 100 分鐘。不可以使用計算機（問答申論題）。試題請隨卷繳回。

112 年的題目全部是「反推／設計」型，幾乎沒有純套公式的題目。第 6 題要從三組存取序列的命中率逆向工程出快取的完整規格，是中山硬體八年最具代表性的一題。

全卷純計算機結構，不考作業系統。

第 1 題：效能計算（20%）

• 1.1（5%）｜失誤延遲 10 cycles、直接對映的命中延遲 2 cycles、失誤率 15%，求平均記憶體延遲
• 1.2（5%）｜組相聯的命中延遲 3 cycles，失誤率要低於多少才能贏過上面的直接對映。考關聯度的取捨：命中時間變長、失誤率變低，要反求損益兩平點
• 1.3（5%）｜30% 是分支、預測準確率 66.66%、誤判罰則 3 cycles、其他指令 1 cycle，求 CPI
• 1.4（5%）｜在什麼條件下，「管線深度加倍、核心時脈加倍」的設計會勝過淺管線。題目沒給深管線的誤判罰則，要自己設成未知數，比較兩種設計的「CPI × 週期時間」後反求條件

第 2 題：DRAM 更新（15%）

4 個通道、每通道 2 個 rank、每 rank 8 個 bank、每 bank 32K 列、每列 8 KB；保留時間 64 ms，每列每 64 ms 更新一次；每次更新佔用命令匯流排 5 ns、佔用該 bank 40 ns。考慮 1.024 秒。

• 2.1（5%）｜1.024 秒內所有通道總共執行幾次更新
• 2.2（5%）｜DRAM 更新直接造成的命令匯流排使用率（跨所有通道）
• 2.3（5%）｜平均每個 bank 的使用率

陷阱是分母：命令匯流排是每個通道一條，bank 使用率是每個 bank 各自算，兩小題的分攤方式不同。題目明說「可以用 2 的冪與 10 的冪的簡化形式作答」——這是因為不能用計算器，數字設計成 2 的冪好算。

第 3 題：鏈結串列走訪與多執行緒（15%）

給一段走訪鏈結串列的 RISC-V 程式（LW 載入 key、LW 載入 next 指標、SEQ 比較、BNEZ 判斷、ADD 移動、BNEZ 迴圈）。單發射循序處理器、每週期發射一道指令、資料相依時停頓、整數指令 1 週期、完美分支預測。

• 3.1（5%）｜沒有快取、每次記憶體操作要 50 個 CPU 週期、load/store 單元完全管線化且非阻塞時，穩態下跑完一次迴圈要幾個週期。要逐拍排出時序，重點是非阻塞讓兩道 LW 可以重疊，以及哪幾道指令依賴哪一道 LW
• 3.2（5%）｜加入零開銷多執行緒、固定 round-robin（每個執行緒每 N 週期執行一道指令），要完全利用處理器至少需要幾條執行緒
• 3.3（5%）｜改成「只在指令因資料相依無法執行時才切換」後，最少需要幾條執行緒。題目提示「考慮每條執行緒在穩態下能連續執行幾道指令」

3.2 與 3.3 的差別在於「每次輪到時能執行幾道」，同一個題型 114 年第 5 題又考了一次。

第 4 題：矩陣乘法的重用區間（15%）

題目先定義重用區間（Reuse Interval, RI）：同一個元素兩次被參考之間，有多少個不同的元素被參考過。並給範例：Z[m,n] = A[m]*B[n] 的雙層迴圈中，RI(A) = 1、RI(B) = N、RI(Z) = 無限（無重用）。

• 4.1（5%）｜迴圈順序為 for m → for n → for k 時，A、B、Z 各自的 RI
• 4.2（5%）｜迴圈順序改為 for k → for m → for n 時，A、B、Z 各自的 RI
• 4.3（5%）｜M=500、N=1000、K=30，硬體預算是一個 MAC 單元 + 一個能存 32 個元素的 SRAM。要最大化計算密度（每次 DRAM 存取的平均計算次數），該選哪個迴圈順序？SRAM 要怎麼分配？
• 要看 RI 與 SRAM 容量（32）之間的關係，再決定哪個張量值得放進 SRAM。題目給的 K 值不是隨便挑的

4.1、4.2 就是逐一套用定義，範例已經示範了寫法；真正的分數在 4.3 的設計取捨。

第 5 題：循序一致性（15%）

三個處理器各執行「先寫一個變數、再讀另一個變數」：

P1: ST (A),1 ; LD RC,(C)
P2: ST (B),1 ; LD RA,(A)
P3: ST (C),1 ; LD RB,(B)

初值 RA = RB = RC = 0。題目已給兩個範例（{1,1,1} 與 {1,1,0} 各自的執行序列），要對 {0,0,0}、{0,1,0}、{1,0,0}、{0,0,1} 四個狀態分別給出可能的執行序列，若在 SC 下不可能就寫 X。

• 核心規則：SC 要求每個處理器內部保持程式順序，但處理器之間可以任意交錯
• 判斷「不可能」時，把各處理器的順序限制與「讀到舊值」所要求的先後關係畫成圖，看有沒有矛盾（環）

第 6 題：從命中率反推快取規格（20%）

只能觀測到三組存取序列的命中率，要推出快取的四個參數。

快取在第一組序列開始時是空的，但第二、三組開始時不是（三組連續執行）。

• 6.1（5%）｜區塊大小（8／16／32／64／128 B）
• 6.2（5%）｜關聯度（1／2／4／8-way）
• 6.3（5%）｜容量（4 或 8 KB）
• 6.4（5%）｜置換策略（LRU 或 FIFO）

做法是逐一假設再驗證：先從最單純的那組序列切入定出一個參數，再帶著它去解下一組。三組序列是連續執行的，後兩組開始時快取裡已經有東西，這一點很容易忘。題目明訂「要解釋才給分」——不能只寫答案。

這份考卷的難點

1. 第 6 題是十年最像逆向工程的一題。 要從「只有命中率」這個唯一的觀測量，推出區塊大小、關聯度、容量、置換策略四個參數，而且四個參數互相牽連，先定錯一個後面全錯。
2. 第 4 題的重用區間概念是課本沒有的。 題目自己定義了 RI，要現場理解並套用，再依 RI 決定 32 個 SRAM 元素怎麼分配。這實際上是 AI 加速器設計的核心問題（dataflow 選擇）。
3. 第 1.4 題要自己設未知數。 深管線的誤判罰則沒有給值，要設成未知數再反求條件。這種「反求條件」的題型在中山很常見。
4. 第 5 題要判斷哪些狀態在 SC 下不可能。 構造可能的序列不難，難的是證明「不可能」。

準備建議

• 112 年全卷都是「反推／設計」題，沒有純套公式的。 準備方向是練「把觀測到的現象反推回設計參數」的能力，而不是背公式
• 從命中率反推快取規格（第 6 題）：練習區塊大小、關聯度、容量、置換策略各自會在存取序列上留下什麼痕跡
• 重用區間（RI）與資料流選擇（第 4 題）是 AI 加速器設計的核心。中山 112 年是八年唯一一次考，但這個方向與台大 113/115、成大 115 的 AI 題呼應
• DRAM refresh 的開銷計算（第 2 題）：匯流排是「每通道」、bank 是「每 bank」。114 年第 1 題又考了一次
• 循序一致性下的可能狀態列舉（第 5 題）：要會構造合法交錯，也要會證明不可能
• 「深管線是否值得」的條件推導（第 1.4 題）：練習設未知數比較兩種設計
• 100 分鐘六大題全是思考題——時間極度緊迫，建議先把第 1、2 題的計算做完，再投入第 4、6 題