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

題型與配分

全卷 3 頁、6 題、100 分，考試時間 100 分鐘，不可使用計算機，全部是問答申論題。

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

• 1.1（5%）｜miss 延遲 10 個週期，direct-mapped cache 的 hit 延遲 2 個週期，miss rate 15%，平均記憶體延遲
• 1.2（5%）｜miss 延遲 10 個週期，set-associative cache 的 hit 延遲 3 個週期，miss rate 要多少，平均延遲才會低於 miss rate 15% 的 direct-mapped cache
• 1.3（5%）｜工作負載有 30% 是分支，branch prediction 準確率 66.66%（misprediction rate 33.33%），可忽略記憶體操作，簡單五級 pipeline 誤判罰則 3 個週期、其他指令的延遲都是 1 個週期，這個工作負載的 CPI
• 1.4（5%）｜同樣的工作負載（30% 分支、misprediction rate 33.33%），在什麼條件下，core clock rate 加倍的更深 pipeline 會勝過較淺的 pipeline

第 2 題：DRAM refresh（15%）

記憶體系統有 4 個通道，每個通道有 2 個 rank 的 DRAM 晶片，每個通道由各自的記憶體控制器控制，每個 rank 有 8 個 bank，每個 bank 有 32K 列，每列 8 KB。系統中所有 DRAM 列的最短保留時間為 64 ms，為了確保資料不遺失，每一列每 64 ms refresh 一次。每次列 refresh 由記憶體控制器的命令發起，佔用對應通道的命令 bus 5 ns、對應的 bank 40 ns。考慮 1.024 秒的時間區間，使用率定義為某項資源（bus 或 bank）被 refresh 命令佔用的時間占總時間的比例。每小題的答案可以用 2 的冪次與 10 的冪次化簡後表示。

• 2.1（5%）｜1.024 秒內，所有四個通道的記憶體控制器總共執行幾次 refresh
• 2.2（5%）｜DRAM refresh 直接造成的命令 bus 使用率（跨所有通道）
• 2.3（5%）｜DRAM refresh 直接造成的 bank 使用率（所有 bank 的平均）

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

基準程式在以 struct node（含 key、指向下一節點的 pointer 與指向資料項目的 pointer）建成的 linked list 中搜尋某個 key。RISC-V 程式的核心如下：

loop: LW   x3, 0(x1)    # load a key
      LW   x4, 4(x1)    # load the next pointer
      SEQ  x3, x3, x2   # set x3 if x3 == x2
      BNEZ x3, end      # find the entry
      ADD  x1, x0, x4
      BNEZ x4, loop     # check the next node
end:

在 single-issue in-order 處理器上執行：每週期可以擷取並發射一道指令，指令因 data dependence 無法發射時處理器 stall，整數指令執行一個週期且結果可以在下一個週期使用（例如 SEQ 在週期 1 執行，BNEZ 可以在週期 2 執行），並假設 branch predictor 完美，taken 與 not-taken 都沒有 penalty。

• 3.1（5%）｜系統沒有 cache，每次記憶體操作直接存取 main memory，要 50 個 CPU 週期，load/store 單元 fully pipelined 且 non-blocking，處理器發出記憶體操作後可以繼續執行指令，直到遇到依賴尚未完成的記憶體操作的指令，穩態下執行一次迴圈要幾個週期
• 3.2（5%）｜在 pipeline 加入零開銷的 multithreading：處理器執行多個 thread，每個 thread 各做一個獨立的搜尋，硬體每個週期 schedule 一個 thread。第一種實作用固定 round robin 每個週期切換到不同的 thread，N 個 thread 各自每 N 個週期執行一道指令，要完全利用處理器（每週期執行一道指令）最少需要幾個 thread
• 3.3（5%）｜改成只在指令因 data dependence 無法執行時才切換到不同的 thread（data-dependent switching），要完全利用處理器最少需要幾個 thread，注意每個 thread 內指令依序發射，提示：考慮每個 thread 在穩態下可以執行幾道指令

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

對某個運算 kernel，定義張量的重用區間（reuse interval，RI）為同一個元素每次被重新參考之間，被參考過的該張量不同元素的個數。題目給的範例：

for m in [0, M)
  for n in [0, N)
    Z[m, n] = A[m] * B[n]

A 的元素在內層迴圈每次都用到，RI 為 1；B 的每個元素在 N 次參考後才被重新參考，RI 為 N；Z 沒有任何元素被重新參考，RI 為無限（沒有重用）。

• 4.1（5%）｜兩個 dense matrix 相乘的 pseudo-code，A 為 M×K、B 為 K×N、Z 為 M×N，迴圈順序為 for m、for n、for k，做 Z[m,n] += A[m,k]*B[k,n]，A、B、Z 三個矩陣的 RI，以 M、N、K 表示
• 4.2（5%）｜把迴圈順序改為 for k、for m、for n，三個矩陣的 RI，以 M、N、K 表示
• 4.3（5%）｜M = 500、N = 1000、K = 30，A、B、Z 都是 dense matrix，計算 kernel 開始時矩陣都在 DRAM 中。要設計矩陣乘法加速器，目標是最大化計算密度（每次 DRAM 存取平均執行的計算次數），硬體預算是：一個輸入與輸出各有一個 flip-flop 的 MAC 單元，以及一個可存 32 個元素的 SRAM array。問 4.1 或 4.2 的迴圈順序要選哪一種，在這個順序下 SRAM 預算要如何分配給不同的元素，可以重新排列 4.1 與 4.2 的迴圈順序，但不能增加迴圈（例如不做 tiling）

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

系統採用 Sequential Consistency（SC），三個 process P1、P2、P3 在不同的處理器上執行（RA、RB、RC 執行前都是 0）：

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

process 全部執行完後，系統可能有多種機器狀態。例如 {RA,RB,RC} = {1,1,1} 在執行順序為 P1.1、P2.1、P3.1、P1.2、P2.2、P3.2 時可能，{1,1,0} 在順序為 P1.1、P1.2、P2.1、P3.1、P2.2、P3.2 時可能。對 {RA,RB,RC} 的狀態 {0,0,0}、{0,1,0}、{1,0,0}、{0,0,1}，各自寫出得到該狀態的指令執行順序，若在 SC 下不可能，就寫 X。

第 6 題：由 hit rate 求快取參數（20%）

要觀察既有的 cache 系統，設計更有效率、針對特定機器的演算法。存取各個位元組的型態可以用來判斷 cache 特性，但在這個系統上唯一能收集的統計是執行下列存取序列後的 cache hit rate：

cache 在第一個序列開始時是空的，第二、三個序列開始時不是空的，三個序列連續執行，之間沒有其他存取，第二（三）個序列開始時的內容與第一（二）個序列結束時相同。根據觀察，說明並回答下列 cache 特性（要解釋才給分）：

• 6.1（5%）｜block size（8、16、32、64 或 128 B）
• 6.2（5%）｜associativity（1、2、4 或 8 路）
• 6.3（5%）｜cache 容量（4 或 8 KB）
• 6.4（5%）｜replacement policy（LRU 或 FIFO）

作答時要注意的地方

1. 第 1、6 題各 20 分，其餘各題 15 分，每小題 5 分。
2. 第 2 題題目說明答案可以用 2 的冪次與 10 的冪次化簡。
3. 第 3.3 題題目給了提示，要考慮每個 thread 在穩態下可以執行幾道指令。
4. 第 4 題的 RI 由題目定義並給了範例，4.3 不可以增加迴圈。
5. 第 5 題在 SC 下不可能的狀態要寫 X。
6. 第 6 題要解釋才給分，三個序列連續執行，後兩個序列開始時 cache 不是空的。

準備方向

• 平均記憶體延遲與 associativity 的取捨（112 第 1.1、1.2 題），108 第 4.5 題、113 第 6 題、115 第 6 題也有。
• 分支誤判的 CPI（112 第 1.3、1.4 題），109 第 5 題、113 第 4 題、114 第 3 題、115 第 5.2 題也有分支。
• DRAM refresh 的使用率（112 第 2 題），107 第 8 題是同一組記憶體規格改成兩個通道，反過來由使用率求每次佔用的時間，114 第 1 題也有。
• multithreading 與最少 thread 數（112 第 3 題），114 第 5 題也有。
• 重用區間與加速器的資料流（112 第 4 題）。
• sequential consistency（112 第 5 題），110 第 1.3 題的 Snoopy 也是多處理器一致性。
• 由 hit rate 反推 cache 參數（112 第 6 題），107 第 4 題同型（四組序列，每組開始時 cache 都是空的），109 第 6 題由 tag store 位元數反推 block size。