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

題型與配分

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

第 1 題：虛擬位址與 page table（10%）

32 位元、以位元組定址、使用 virtual addressing 的機器，最高兩位元為 11 的位址視為 unmapped，只有作業系統可以存取，不經過 address translation。答案要寫成 2 的冪次的倍數，或適當用 KB、MB、GB、TB 表示。

• 1.1（2%）｜這個系統最多能定址多少 physical memory
• 1.2（2%）｜這個系統上單一 process 最多能定址多少 virtual memory
• 1.3（2%）｜頁大小 4 KB 時，每個 process 有多少虛擬頁
• 1.4（2%）｜每個 page table entry 4 bytes，單層 page table 需要多少記憶體
• 1.5（2%）｜兩層 page table，virtual page number 的一半位元用來索引第一層、另一半索引第二層，若 process 的 page table 總大小限制在 400 KB，process 可以使用幾個第二層 page table

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

• 2.1（3%）｜這顆 CPU 的 CPI
• 2.2（4%）｜變體 1：所有 add 換成耗時相同的 subtract，求 CPI
• 2.3（4%）｜變體 2：移除延遲最高的指令，把這些指令全部換成混合中延遲最低的指令再加 3 個週期，求 CPI（相對於原本的指令數）
• 2.4（4%）｜變體 3：divide 的延遲降為原來的四分之一，branch 的延遲增加 50%，求 CPI

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

要把舊程式平行化，設計一顆客製的異質處理器：一個 big core（執行快、佔晶片面積大）與多個 small core（執行慢、佔面積小）共用一顆晶片。

• 平行段的所有 thread 只在 small core 上執行，序列段只有一個 thread 在 big core 上執行
• core 的效能（執行速度）與面積的平方根成正比
• 晶片有 16 單位面積，small core 佔 1 單位，big core 可以佔 n² 單位（n 為正數），沒被 big core 用到的面積全部填滿 small core
• 序列段佔總工作量的 10%，平行段佔其餘 90%

• 3.1（5%）｜程式最快的執行下，speedup 是多少
• 3.2（5%）｜若 16 單位面積全部做成 16 個 small core 的同質系統，序列段在其中一個 small core 上跑、平行段在 16 個 small core 上跑，同一個程式的 speedup 是多少

第 4 題：TLB 與實體 frame（15%）

8 位元以位元組定址的 virtual address space，physical memory 128 bytes，每頁 16 bytes，使用單層轉換，page table 放在 physical memory。physical memory 各 frame 的初始內容：frame 0 空、frame 1 為 page 13、frame 2 為 page 5、frame 3 為 page 2、frame 4 空、frame 5 為 page 0、frame 6 空、frame 7 放 page table。系統另外加上一個三個 entry 的 TLB，使用 LRU replacement，初始放著 page 0、2、13 的 entry（題目註明 physical memory 的 page replacement 也使用 LRU）。

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

• 4.1（4%）｜這個參考序列的 TLB hit rate
• 4.2（3%）｜序列結束時，TLB 內的三個 entry
• 4.3（8%）｜8 個實體 frame 的內容

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

七級 pipeline，分支在第六級解析，20% 的指令是分支。

• 5.1（5%）｜每次分支誤判，浪費多少道指令的工作
• 5.2（5%）｜程式正確路徑上有 N 道指令，branch predictor 準確率為 A，寫出這台機器擷取的指令數（以 N 與 A 表示）
• 5.3（5%）｜若改用 dual-path execution（兩條分支路徑各擷取相同數量的指令），且分支在擷取新的分支之前就解析完畢，寫出這時擷取的指令數（以 N 表示）

第 6 題：由 tag store 求區塊大小（10%）

以位元組定址、16 位元位址、3-way set associative、write-back 的 cache，使用 true LRU replacement，LRU 用實作所需的最少位元數，tag store 總共需要 264 bits。求 cache 的 block size。

第 7 題：FR-FCFS 與 DRAM bank（10%）

以位元組定址的處理器連到單一記憶體通道，通道上只有一個 rank 的 DRAM。physical address 32 位元，處理器用 [Rows | Banks | Columns | Cache Line Offset]（由高位到低位）的映射索引 DRAM，一個 column 與一條 cache line 一樣大，cache line 為 64 bytes，Columns 為 6 位元、Cache Line Offset 也是 6 位元，row 大小為 4 KB。

時間 0 時記憶體請求 queue 有 4 個待處理請求：A（最舊）0x0000-4000、B 0x0000-1040、C 0x0000-3040、D（最新）0x0000-4a00。

• row buffer hit 要 50 個週期，row buffer conflict 要 250 個週期
• 不同 bank 的請求可以由各 bank 平行處理
• 時間 0 時所有 row buffer 都是關閉的
• 控制器不能同時發出兩個請求，每個請求要 10 個週期處理，所以發出兩個請求之間隔 10 個週期
• 控制器使用 First Ready-First Come First Serve（FR-FCFS）scheduling

若處理完這四個請求共需 320 個週期，這個 rank 的 DRAM 至少有幾個 bank。

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

• 8.1（4%）｜static code scheduling 的兩個缺點
• 8.2（4%）｜dynamic code scheduling 的兩個缺點
• 8.3（4%）｜dynamic code scheduling 用哪兩個機制來減輕 static scheduling 的缺點，各自為什麼有幫助
• 8.4（3%）｜out-of-order execution 期間會出現哪些種類的 dependence

作答時要注意的地方

1. 全卷 8 題，配分是 10、15、10、15、15、10、10、15，不可使用計算機。
2. 第 1 題答案要寫成 2 的冪次的倍數，或適當用 KB、MB、GB、TB 表示。
3. 第 3 題的 big core 面積是 n² 單位，n 為正數。
4. 第 4 題題目註明 physical memory 的 page replacement 也使用 LRU，page table 放在 frame 7。
5. 第 6、7 題都是由結果求設計參數，第 6 題給 tag store 的總位元數，第 7 題給總處理時間。

準備方向

• virtual address 與 page table（109 第 1 題），111 第 2 題、113 第 7.1 題、114 第 2 題也有位址拆解與 page table 大小。
• CPI 與指令組合（109 第 2 題），107 第 1 題也是給指令延遲表求 CPI 再改設計，106 第 3 題、108 第 2.4 題、110 第 2.1 題、112 第 1.3 題、113 第 4 題、115 第 1.2、2.1 題也有。
• Amdahl's Law 與 heterogeneous multicore（109 第 3 題），108 第 2 題、110 第 2.2 題、111 第 4.2 題、113 第 1 題、115 第 2.2 題也有 Amdahl's Law。
• TLB 與 frame 追蹤（109 第 4 題），113 第 7.2 題也要追蹤 TLB 與 page table 狀態，108 第 4.4 題、110 第 4.1 題、111 第 1.2 題、114 第 2 題也有 TLB。
• 七級 pipeline 的分支（109 第 5 題），114 第 3.1 到 3.3 題相同，112 第 1.3、1.4 題、113 第 4 題、115 第 5.2 題也有分支。
• Tag store 與 cache 位元數（109 第 6 題），108 第 4.1 到 4.3 題、110 第 4.2 題、111 第 3 題、113 第 5.2 題也有。
• DRAM 的位址映射與 scheduling（109 第 7 題），107 第 8 題、112 第 2 題、114 第 1 題也有 DRAM。
• static 與 dynamic scheduling（109 第 8 題），108 第 5.4 題、114 第 6 題也有，107 第 6 題考 Tomasulo 演算法。