109 年 國立中山大學資訊工程學系碩士班乙組《計算機結構》

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊

第 1 題10 分

  1. (10% total) Assume a 32-bit, byte-addressed machine with virtual addressing. The two high-order bits are treated as unmapped. These addresses are only accessible by the operating system and bypass virtual address translation. The answers need to express as a multiple of a power of 2, or in terms of KB, MB, GB, or TB as appropriate.
    1.1 (2%) What is the maximum amount of physical memory this system can address?
    1.2 (2%) What is the maximum amount of virtual memory any single process on this system can address?
    1.3 (2%) How many virtual pages are available to each process, assuming 4KB pages?
    1.4 (2%) Assume each page table entry is 4 bytes, how much memory would a single-level page table require?
    1.5 (2%) Assuming a two-level page table where half the bits of the virtual page number are used to index the first level, and the other half are used to index the second level, how many second-level page tables can a process use if its total page table size is limited to 400KB?

登入後即可作答並保存紀錄。

這一題的完整詳解

1.1

在 32-bit 位元組定址（byte-addressed）系統中，實體位址長度為 32 bits。可定址的最大實體記憶體容量為：
232 Bytes=4 GB2^{32} \text{ Bytes} = 4 \text{ GB}

【答案】 4 GB

1.2

題目給定虛擬位址最高 2 bits 為 unmapped（由 OS 直接存取並繞過分頁轉譯），因此需透過分頁轉譯的虛擬位址空間剩餘 32−2=3032 - 2 = 30 bits。單一程序可透過轉譯機制存取的最大虛擬記憶體容量為：
230 Bytes=1 GB2^{30} \text{ Bytes} = 1 \text{ GB}

【答案】 1 GB

1.3

分頁大小（Page Size）為 4KB =212 Bytes= 2^{12} \text{ Bytes}，故頁內偏移量（Page Offset）占 12 bits。
虛擬頁號（VPN）位元數為 30−12=1830 - 12 = 18 bits。
單一程序可用的虛擬分頁數量為：
218=256K 個(262,144 個)2^{18} = 256\text{K} \text{ 個} \quad (262,144 \text{ 個})

【答案】 2182^{18}（或 256K 個）

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 2 題15 分

  1. (15% total) The instruction latency for a given CPU is shown in Table 1.
    Table 1.
    Instructions | Breakdown | Latency
    ------------ | --------- | -------
    load | 5% | 3 cycles
    add | 10% | 5 cycles
    divide | 10% | 8 cycles
    branch | 50% | 2 cycles
    shift left | 15% | 5 cycles
    shift right | 10% | 1 cycles

2.1 (3%) Calculate the CPI of the given CPU?
2.2 (4%) Variant 1: All add instructions are replaced with corresponding subtract instructions that take the same amount of time. Calculate the CPI of the Variant 1?
2.3 (4%) Variant 2: Remove the highest-latency instruction, and replace all those instructions with additional latency of three cycles for the lowest latency instruction in the mix. Calculate the CPI of the Variant 2 (relative to the original instruction count)?
2.4 (4%) Variant 3: Reduce the latency for divides by a factor of four, but increase the latencies of branches by 50%. Calculate the CPI of the Variant 3?

登入後即可作答並保存紀錄。

這一題的完整詳解

2.1

觀念與推導：
平均每指令週期數（CPI）為各類指令比例（Breakdown）與其執行週期（Latency）之加權總和：
CPI=∑(Instruction Ratioi×Latencyi)\text{CPI} = \sum (\text{Instruction Ratio}_i \times \text{Latency}_i)

帶入原始數據計算：
CPI=0.05×3+0.10×5+0.10×8+0.50×2+0.15×5+0.10×1\text{CPI} = 0.05 \times 3 + 0.10 \times 5 + 0.10 \times 8 + 0.50 \times 2 + 0.15 \times 5 + 0.10 \times 1
CPI=0.15+0.50+0.80+1.00+0.75+0.10=3.3\text{CPI} = 0.15 + 0.50 + 0.80 + 1.00 + 0.75 + 0.10 = 3.3

【答案】CPI=3.3\text{CPI} = 3.3

2.2

觀念與推導：
Variant 1 將所有 add 指令替換為執行時間相同的 subtract 指令（延遲同為 5 cycles），指令比例與對應延遲皆未改變，故 CPI 與原 CPU 相同。

【答案】CPI=3.3\text{CPI} = 3.3

2.3

觀念與推導：

  1. 最高延遲指令：divide（8 cycles，占比 10%）。
  2. 最低延遲指令：shift right（1 cycle）。
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 3 題10 分

  1. (10% total) A old program needs to be parallelized. Then, it can run faster on modern multicore processors. In order to execute the program with parallel and serial portions more efficiently, a custom heterogeneous processor needs to be designed.
    ➤ The processor has one large core which executes code more quickly but takes greater die area on-chip, the multiple small cores which execute code more slowly but consume less area, all sharing one processor die.
    When program in its parallel portion, all of its threads execute only on small cores.
    When program in its serial portion, the one active thread executes on the large core.
    Performance (execution speed) of a core is proportional to the square root of its area.
    Assume 16 units of die area available. A small core takes 1 unit of die area. The large core can take any number of units of die area n², where n is the positive number. Area not used by the large core will be filled with smaller cores.
    The serial portion is only 10% of total work, and the parallel portion is the remaining 90%.
    3.1 (5%) What would be the speed up for the fastest possible execution of the program?
    3.2 (5%) What would the same program's speedup be if all 16 units of die area were used to build a homogeneous system with 16 small cores, the serial portion ran on one of the small cores, and the parallel portion ran on all 16 small cores?

登入後即可作答並保存紀錄。

這一題的完整詳解

3.1 詳解

設單一小核心面積為 11，效能為 1=1\sqrt{1} = 1。
大型核心佔用面積為 n2n^2，效能為 n2=n\sqrt{n^2} = n，剩餘面積可容納的小核心數量為 16−n216 - n^2 個。

根據異質多核心架構下之執行時間公式：
T(n)=fsPerflarge+fpNumsmall×Perfsmall=0.1n+0.916−n2T(n) = \frac{f_s}{\text{Perf}_{large}} + \frac{f_p}{\text{Num}_{small} \times \text{Perf}_{small}} = \frac{0.1}{n} + \frac{0.9}{16 - n^2}

欲求最快執行時間（即 T(n)T(n) 之極小值），對 nn 求微分：
dT(n)dn=−0.1n2+1.8n(16−n2)2=0\frac{dT(n)}{dn} = -\frac{0.1}{n^2} + \frac{1.8n}{(16 - n^2)^2} = 0
18n3=(16−n2)218n^3 = (16 - n^2)^2

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 4 題15 分

  1. (15% total) An 8-bit byte-addressed virtual address space and the physical memory has 128 bytes. Each page contains 16 bytes. A simple, one level translation scheme is used and the page table resides in physical memory. The initial contents of the frames of the physical memory are shown in Table 2.

Table 2.

Frame NumberFrame Contents
0Empty
1Page 13
2Page 5
3Page 2
4Empty
5Page 0
6Empty
7Page Table

A three-entry translation lookaside buffer (TLB) that uses Least Recently-Used (LRU) replacement is added to this system. Initially, this TLB contains the entries for pages 0, 2, and 13. (Note: LRU is used to select pages for replacement in physical memory.)
References (to pages): 0, 13, 5, 2, 14, 14, 13, 6, 6, 13, 15, 14, 15, 13, 4, 3.

4.1 (4%) What is the hit rate of the TLB for this sequence of references?
4.2 (3%) At the end of this sequence, what three entries are contained in the TLB?
4.3 (8%) What are the contents of the 8 physical frames?

登入後即可作答並保存紀錄。

這一題的完整詳解

4.1 TLB Hit Rate

系統包含 3 個 entry 的 TLB，採用 LRU 替換策略。初始內容為 Page 0, 2, 13。

存取序列 (共 16 次) 追蹤過程如下：

  1. Page 0：Hit (TLB 更新為 [2,13,0][2, 13, 0]，最右側為 MRU)
  2. Page 13：Hit (TLB 更新為 [2,0,13][2, 0, 13])
  3. Page 5：Miss，剔除 LRU (2)，放入 5 (TLB 更新為 [0,13,5][0, 13, 5])
  4. Page 2：Miss，剔除 LRU (0)，放入 2 (TLB 更新為 [13,5,2][13, 5, 2])
  5. Page 14：Miss，剔除 LRU (13)，放入 14 (TLB 更新為 [5,2,14][5, 2, 14])
  6. Page 14：Hit (TLB 更新為 [5,2,14][5, 2, 14])
  7. Page 13：Miss，剔除 LRU (5)，放入 13 (TLB 更新為 [2,14,13][2, 14, 13])
  8. Page 6：Miss，剔除 LRU (2)，放入 6 (TLB 更新為 [14,13,6][14, 13, 6])
  9. Page 6：Hit (TLB 更新為 [14,13,6][14, 13, 6])
  10. Page 13：Hit (TLB 更新為 [14,6,13][14, 6, 13])
  11. Page 15：Miss，剔除 LRU (14)，放入 15 (TLB 更新為 [6,13,15][6, 13, 15])
  12. Page 14：Miss，剔除 LRU (6)，放入 14 (TLB 更新為 [13,15,14][13, 15, 14])
  13. Page 15：Hit (TLB 更新為 [13,14,15][13, 14, 15])
  14. Page 13：Hit (TLB 更新為 [14,15,13][14, 15, 13])
  15. Page 4：Miss，剔除 LRU (14)，放入 4 (TLB 更新為 [15,13,4][15, 13, 4])
  16. Page 3：Miss，剔除 LRU (15)，放入 3 (TLB 更新為 [13,4,3][13, 4, 3])

總存取次數為 16 次，TLB Hit 次數為 7 次 (第 1, 2, 6, 9, 10, 13, 14 次存取)。

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 5 題15 分

  1. (15% total) Assume a machine with a 7-stage pipeline. Assume that branches are resolved in the sixth stage. Assume that 20% of instructions are branches. Answer the following questions.
    5.1 (5%) How many instructions of wasted work are there per branch misprediction on this machine?
    5.2 (5%) Assume N instructions are on the correct path of a program and assume a branch predictor accuracy of A. Write the equation for the number of instructions that are fetched on this machine in terms of N and A.
    5.3 (5%) If the machine were modified so that it used the dual path execution (where an equal number of instructions are fetched from each of the two branch paths). Assume that branches are resolved before new branches are fetched. Write how many instructions would be fetched in this case as a function of N.

登入後即可作答並保存紀錄。

這一題的完整詳解

5.1

分支指令於第 1 階段擷取（Fetch），並於第 6 階段確定跳躍方向（Resolve）。在第 6 階段解析完成前，管線中位於該分支指令之後已擷取的指令數為：
6−1=5 個指令6 - 1 = 5 \text{ 個指令}
因此，每次分支預測錯誤會造成 5 個指令的無用工作（須將管線中該 5 個錯誤路徑上的指令清除）。

【答案】 5 個指令

5.2

程式正確執行路徑上的指令總數為 NN。

  1. 分支指令數量為 0.2N0.2N。
  2. 分支預測錯誤率為 1−A1 - A，預測錯誤的分支次數為 0.2N(1−A)0.2N(1 - A)。
  3. 每次預測錯誤會額外擷取 5 個錯誤路徑的指令。
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 6 題10 分

  1. (10% total) A byte-addressable system with 16-bit address ships with a three-way set associative, write-back cache. The cache implements a true LRU replacement policy using the minimum number of replacement policy bits necessary to implement it. The tag store requires a total of 264 bits of storage. What is the block size of the cache?

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念

本題考查快取位址切割與標籤儲存容量計算：

  • 位址長度：1616 bits。
  • 系統為 byte-addressable，因此位移欄位表示區塊內的「位元組數」。
  • 三路組合式快取：每組有 33 個 cache line。
  • Write-back cache 每個 cache line 需要 1 個 dirty bit。
  • 每個 cache line 需要 1 個 valid bit。
  • 三路 true LRU 的狀態共有 3!=63!=6 種，因此至少需要
⌈log⁡2(6)⌉=3\left\lceil \log_2(6)\right\rceil=3

bits，而且這 33 bits 是每組共用，不是每個 cache line 各有 33 bits。

解題方法

設：

  • 區塊大小為 2b2^b bytes，因此 block offset 為 bb bits。
  • 組數為 2s2^s 組，因此 set index 為 ss bits。
  • Tag 長度為 tt bits。

位址切割關係為

t+s+b=16t+s+b=16

所以

t=16−s−bt=16-s-b

三路組合式快取共有

3⋅2s3\cdot 2^s

個 cache line。

每個 cache line 的 tag store 儲存：

  • Tag：tt bits
  • Valid bit：11 bit
  • Dirty bit：11 bit

因此每個 cache line 需要

t+2t+2

bits。

所有 cache line 的儲存量為

3⋅2s(t+2)3\cdot 2^s(t+2)

每組的 LRU 欄位需要 33 bits，總共 2s2^s 組，因此 LRU 儲存量為

3⋅2s3\cdot 2^s

題目給定 tag store 總容量為 264264 bits：

3⋅2s(t+2)+3⋅2s=2643\cdot 2^s(t+2)+3\cdot 2^s=264

整理得

🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊

第 7 題10 分

  1. (10% total) A byte-addressable processor is connected to a single memory channel that has a single rank of DRAM. The physical address space is 32 bits, and the processor uses the following mapping shown in Table 3, to index the DRAM. Each DRAM row has a certain number of columns, where a column has the same size of a cache line. The processor uses 64-byte cache lines. The Columns is 6 bits and the Cache Line Offset is also 6 bits. In addition, the row size is 4 KB.
    Table 3 Mapping from the physical address to DRAM
    MSB | Rows | Columns | Banks | Cache Line Offset | LSB
    ---|---|---|---|---|---

7.1 (What is the minimum number of banks required for the DRAM to finish processing all four requests in 320 cycles?) (Assume A row buffer hit takes 50 cycles, A row buffer conflict takes 250 cycles. Requests going to different banks can be processed by the banks in parallel. All the row buffers are closed at times 0. The controller cannot issue two requests at the same time. Each request takes 10 cycles to process, so it takes 10 cycles between issuing two separate requests to the memory. The controller employs First Ready-First Come First Serve (FR-FCFS) scheduling policy.)

登入後即可作答並保存紀錄。

這一題的完整詳解

核心觀念與時間分析

  1. 記憶體控制器發送間隔：控制器發送每個要求需耗時 10 cycles10\text{ cycles}，故 4 個要求的發送時間分別為 t=0,10,20,30 cyclest = 0, 10, 20, 30\text{ cycles}。
  2. 存取延遲：
    • 時間 t=0t = 0 時所有 Row Buffer 均為關閉狀態，故各 Bank 的第一個要求均為 Row Conflict/Miss，處理時間為 250 cycles250\text{ cycles}。
    • 若同一 Bank 後續要求命中已開啟的 Row Buffer（Hit），處理時間為 50 cycles50\text{ cycles}。
  3. 多 Bank 平行處理：不同 Bank 可同時平行處理各自的要求。

最少 Bank 數推導

1. 單一 Bank 處理極限

若所有要求皆在同一 Bank 執行：

  • 最佳情況為 1 個 Miss 搭配 3 個 Hit。
  • 完成 2 個要求的所需時間：0+250+50=300 cycles0 + 250 + 50 = 300\text{ cycles}。
  • 完成 3 個要求的所需時間：300+50=350 cycles>320 cycles300 + 50 = 350\text{ cycles} > 320\text{ cycles}。
🔒

後續完整解題步驟與【答案】

免費註冊，享三天全站完整詳解閱覽。

免費註冊
📄 以下 4 題共用同一段題幹

(15% total) Please answer the following questions.

第 8.1 題4 分

Give two disadvantages of static code scheduling.

登入後即可作答並保存紀錄。

這一題的完整詳解
載入中…

第 8.2 題4 分

Give two disadvantages of dynamic code scheduling.

登入後即可作答並保存紀錄。

這一題的完整詳解
載入中…

第 8.3 題4 分

What are two mechanisms that dynamic code scheduling uses to mitigate the shortcomings of static code scheduling, and why does each mechanism help?

登入後即可作答並保存紀錄。

這一題的完整詳解
載入中…

第 8.4 題3 分

What types of dependencies can occur during out-of-order execution?

登入後即可作答並保存紀錄。

這一題的完整詳解
載入中…

其他考古題

其他學校的資工系考古題

臺灣大學36清華大學3陽明交通大學24成功大學24中央大學51中正大學34臺北大學13高雄大學7暨南國際大學6嘉義大學4臺南大學2