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

題型與配分

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

109 年是中山硬體八年裡難度最高的一年：第 3、6、7 題都是「反推設計參數」的題型，而不是套公式。

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

第 1 題：虛擬位址與頁表（10%）

32-bit 位元組定址、虛擬定址，最高兩位為 11 的位址視為未映射（由 OS 專用、繞過位址轉換）。

• 1.1（2%）｜系統最多能定址多少實體記憶體
• 1.2（2%）｜單一程序最多能定址多少虛擬記憶體
• 1.3（2%）｜每個程序有多少虛擬頁（4 KB 頁）
• 1.4（2%）｜單層頁表需要多少記憶體（每個條目 4 bytes）
• 1.5（2%）｜兩層分頁下，若總頁表大小限制在 400 KB，程序最多能用幾個第二層頁表。第一層頁表本身也佔空間，要先扣掉
• 「最高兩位為 11 的位址保留給 OS」這個條件影響的是哪幾小題要想清楚——它限制的是虛擬位址空間還是實體位址空間，是 1.1 與 1.2 的分界

第 2 題：指令延遲表與 CPI（15%）

• 2.1（3%）｜原始 CPI
• 2.2（4%）｜變體 1：把所有 add 換成耗時相同的 subtract
• 2.3（4%）｜變體 2：移除延遲最高的指令，把那些指令改成「延遲最低的指令再加三個週期」。要先從表上找出最高與最低延遲的指令
• 2.4（4%）｜變體 3：divide 的延遲降為 1/4、branch 的延遲增加 50%
• 三個變體都可以從原始 CPI 做增量修正，不必每次重算六項；branch 佔 50%，它的延遲變化對 CPI 的影響特別大

第 3 題：異質多核的面積分配（10%）

規則：

• 晶片共 16 單位面積；小核佔 1 單位、大核佔 n² 單位（n 為正數）
• 核心效能正比於面積的平方根
• 序列段（10%）只在大核上跑、平行段（90%）只在小核上跑
• 大核沒用到的面積全部填滿小核

• 3.1（5%）｜最快執行下的加速比是多少。要自己把總執行時間寫成 n 的函數，再判斷 n 的合理範圍、逐一試值找最小
• 3.2（5%）｜若 16 單位全部做成 16 個小核（序列段在一個小核上跑、平行段用 16 個），加速比是多少，並與 3.1 比較
• 這題是 big.LITTLE 的理論基礎：大核與小核之間的面積取捨，要看序列段與平行段哪一邊的代價比較大

第 4 題：TLB 與實體頁框追蹤（15%）

8-bit 位元組定址的虛擬位址空間、實體記憶體 128 bytes、每頁 16 bytes、單層頁表放在實體記憶體中。初始頁框內容：frame 1 = page 13、frame 2 = page 5、frame 3 = page 2、frame 5 = page 0、frame 7 = 頁表，其餘為空。三條目的 TLB 用 LRU，初始含 page 0、2、13 的條目。

參考序列（頁號）：0, 13, 5, 2, 14, 14, 13, 6, 6, 13, 15, 14, 15, 13, 4, 3

• 4.1（4%）｜TLB 的命中率——要逐步追蹤 TLB 的三個條目在 LRU 下的替換
• 4.2（3%）｜序列結束時 TLB 中是哪三個條目
• 4.3（8%）｜八個實體頁框的最終內容。要注意存放頁表的那個頁框不能被置換，以及空頁框與 LRU 置換的先後。這是全卷最耗時的一小題
• TLB 與實體記憶體是兩套各自的 LRU，要分兩欄同時追蹤，別把兩者的「最近使用」混在一起

第 5 題：七級管線的分支（15%）

七級管線、分支在第六級解析、20% 的指令是分支。

• 5.1（5%）｜每次分支誤判浪費幾道指令的工作。關鍵是「分支在第幾級才解析出來」
• 5.2（5%）｜正確路徑上有 N 道指令、分支預測準確率 A 時，這台機器總共擷取幾道指令（用 N 與 A 表示）
• 5.3（5%）｜若改用雙路徑執行（兩條分支路徑各取相同數量的指令），且分支在取下一個分支前就解析完畢，總共擷取幾道指令（用 N 表示）
• 5.2 與 5.3 可以互相驗算：想一想雙路徑執行在某種意義上等於預測準確率是多少的情況。這題在 114 年第 3.1–3.3 題一字不差地重考，114 年還多加了第四小問

第 6 題：從 tag store 反推區塊大小（10%）

位元組定址、16-bit 位址、3-way 組相聯、write-back、真 LRU（用最少的位元數實作），tag store 總共需要 264 bits。求區塊大小。

• 要自己列出 tag store 的組成：每一路要存什麼、每一個 set 還要額外存什麼
• 三個容易漏的東西：valid 位元、write-back 需要的那一個位元、3-way 真 LRU 最少要幾個位元（要從「3 路有幾種排列順序」去想）
• 列出式子後會有 set 數與區塊大小兩個未知數，要利用「都是 2 的冪、答案必須是整數」這個限制去試值

這題要同時處理四件事：tag 位元數的表示式、每路的控制位元、真 LRU 的位元數、以及解一個含兩個未知數的方程式。

第 7 題：從 FR-FCFS 反推 DRAM bank 數（10%）

實體位址 32 bits，映射為 [Rows | Banks | Columns | Cache Line Offset]；cache line 64 bytes、Columns 6 bits、row 大小 4 KB。

四個待處理請求（時間 0）：A（最舊）0x00004000、B 0x00001040、C 0x00003040、D（最新）0x00004a00

條件：row buffer 命中 50 cycles、衝突 250 cycles、不同 bank 可平行處理、所有 row buffer 初始關閉、控制器每 10 cycles 才能發出下一個請求、採 FR-FCFS 排程。

若處理完四個請求共花 320 cycles，這個 rank 至少有幾個 bank？

• 第一步是切位址：從 offset 與 columns 的位元數定出 bank 欄位從哪一位開始
• bank 數是未知數，所以 bank 欄位的寬度也是未知數——要對不同的 bank 數分別算出四個請求落在哪個 bank、哪個 row
• FR-FCFS 的規則要熟：「row buffer 命中優先，其次才看先來後到」
• 「row buffer 初始關閉」這個條件決定了第一次存取某個 bank 的代價
• 最後依時序推出每種 bank 數下的總時間，找出最少要幾個 bank 才會是 320 cycles

第 8 題：靜態與動態程式碼排程（15%）

• 8.1（4%）｜靜態程式碼排程的兩個缺點
• 8.2（4%）｜動態程式碼排程的兩個缺點
• 8.3（4%）｜動態排程用哪兩個機制彌補靜態排程的不足？各自為何有幫助
• 8.4（3%）｜亂序執行期間可能出現哪些相依。不只是暫存器之間的三種資料相依，要想到其他來源的相依
• 8.1 與 8.2 是一體兩面：靜態排程缺的是什麼資訊、動態排程付出了什麼代價，兩題的論點要能互相對應

這份考卷的難點

1. 第 3 題要自己列出目標函數再逐一試值。 n 的合理範圍要自己判斷，算出最佳值之後還要和 3.2 的同質設計比較。這是 Amdahl's Law 在異質架構下的應用。
2. 第 6 題要解一個含兩個未知數的方程式。 tag store 的組成少算任何一項都解不出整數解，這一點反而可以拿來檢查自己有沒有漏項。
3. 第 7 題要從位址映射反推 DRAM 的組織。 要先切出 row/bank/column 各佔幾位元，算出四個請求的 bank 與 row，再依 FR-FCFS 的規則排出時序。10 分但工作量極大。
4. 第 4.3 題的實體頁框追蹤要同時維護 TLB 與實體記憶體兩套 LRU，16 次參考，是全卷最耗時的一小題。

準備建議

• 109 年的三道「反推」題（第 3、6、7 題）是中山硬體八年最難的一組。準備方向不是背公式，而是練「把設計參數設成未知數、列出方程式再解」的能力
• 異質多核的面積分配（第 3 題）是 big.LITTLE 的理論基礎，Hennessy & Patterson 多核章節的習題值得做一遍
• tag store 總位元數的完整組成（第 6 題）：每一路要存什麼、LRU 要幾個位元，n-way 真 LRU 的位元數要會自己推
• DRAM 的位址映射與 FR-FCFS（第 7 題）：row buffer 命中、衝突、不同 bank 平行，三種情況的時序要會排
• 分支誤判的浪費工作量（第 5 題）要能自己推出通式。114 年第 3 題把這題原樣重考，並延伸到信心估計器
• CPI 的加權平均與變體比較（第 2 題）是送分題，但四個小問要算四次，時間要控制
• 中山 100 分鐘要寫完八大題，時間壓力極大。建議先掃過全卷，把第 2、5 題這類純套公式的先做完，再處理第 3、6、7 題