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

📄 試題原卷　免費註冊後即可對照原始考卷 PDF免費註冊
📄 以下 5 題共用同一段題幹

All the following questions are multiple-choice questions. Please explain your reasons for the choices, which you don’t select.

第 1-(1) 題2 分

A computer has 128 MB128\text{ MB} of memory. Each word in the computer is eight bytes. How many bits at least are needed to address any single word in memory?

(A) 88 bits
(B) 1616 bits
(C) 2424 bits
(D) 3232 bits

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

這一題的完整詳解

核心觀念

題目考查字組定址與位址位元數的關係。若記憶體可存放 NN 個字組，每個位址需唯一識別其中一個字組，則至少需要 kk 個位元，使：

2k≥N2^k \ge N

因此，所需位址位元數為 ⌈log⁡2N⌉\lceil \log_2 N\rceil。

解題方法

記憶體容量為 128 MB128\text{ MB}。依計算機結構常用的二進位容量換算：

128 MB=128×220 bytes=227 bytes128\text{ MB}=128\times 2^{20}\text{ bytes}=2^{27}\text{ bytes}

每個字組為 88 bytes，即 232^3 bytes，因此記憶體共有：

227 bytes23 bytes/word=224 words\frac{2^{27}\text{ bytes}}{2^3\text{ bytes/word}}=2^{24}\text{ words}

要為 2242^{24} 個字組各編配一個位址，至少需要 2424 位元。

🔒

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

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

免費註冊

第 1-(2) 題2 分

In modern computer architectures, TLB is usually involved to improve the efficiency of the memory hierarchy. If we meet a situation of TLB miss, which of the following descriptions is true?

(A) The data requested by the CPU must be not in the cache.
(B) The data requested by the CPU must be not in the main memory.
(C) The CPU has failed to get the physical address of the required data.
(D) The CPU must send a request to access the main memory immediately.

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

這一題的完整詳解

核心觀念

TLB（轉譯後備緩衝區）快取的是「虛擬頁號 → 實體頁框號」的對映。CPU 發出虛擬位址後，先查 TLB：

  • TLB 命中：取得對映，形成實體位址。
  • TLB 未命中：TLB 沒有這筆對映，CPU 尚未由 TLB 取得實體位址，須再查頁表。頁表查詢成功後，才能形成實體位址並繼續存取快取或主記憶體。
  • 頁面錯誤：頁表指出該頁不在主記憶體，才需要作業系統處理並從儲存裝置載入。

因此，TLB 未命中與快取未命中、主記憶體未命中是不同事件。

解題方法

沿著位址轉譯與資料存取的順序判斷：先查 TLB，再查頁表取得實體位址，最後才進入快取與主記憶體階層。題目問的是 TLB 未命中的直接意義，不應將它誤當成資料不在快取或主記憶體。

選項分析

🔒

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

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

免費註冊

第 1-(3) 題2 分

To solve the cache coherence problem, Snoopy protocol is the simplest. Regarding the Snoopy coherence protocol, which of the following descriptions is true?

(A) Any CPU should invalidate the cache block if it receives a write miss signal to the data in the local cache block from the bus.
(B) Any CPU should invalidate the cache block if it receives a read miss signal to the data in the local cache block from the bus.
(C) The Snoopy coherence protocol is an atomic operation.
(D) The Snoopy coherence protocol is proper to apply to a single-core system.

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

這一題的完整詳解

核心觀念

Snoopy（匯流排監聽）一致性協定用於多處理器共享記憶體系統。各處理器的快取控制器會監聽共用匯流排上的交易，並依照其他處理器的讀寫要求，更新或失效本地快取中的對應快取區塊，以維持快取一致性。

常見匯流排交易包括：

  • 讀取未命中（BusRd）：處理器要讀取的區塊不在本地快取，向匯流排要求資料。其他快取若持有該區塊，可能提供資料或改變狀態；通常不會因此一律失效。
  • 寫入未命中／讀取獨占（BusRdX）：處理器要寫入的區塊不在本地快取，要求取得該區塊的獨占權。其他快取若持有該區塊，必須使其失效，避免不同快取各自保有可寫入的副本。

解題方法

判斷各選項描述的匯流排事件，以及其他快取應採取的動作。關鍵是分清：

  • 其他處理器讀取某區塊時，既有副本通常仍可保留。
  • 其他處理器要求寫入獨占權時，其他快取中的同一區塊必須失效。

選項分析

🔒

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

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

免費註冊

第 1-(4) 題2 分

Regarding cache miss, which of the following descriptions is true?

(A) Compulsory miss indicates that the cache cannot contain all blocks required for the execution.
(B) Coherence miss only happens in multi-core systems.
(C) The miss rate will go down while the block size is made very large.
(D) Increasing the associativity decreases miss rate due to lower compulsory miss.

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

這一題的完整詳解

核心觀念

快取未命中的 4C 分類：

  • Compulsory（強制／冷啟動）：第一次存取某區塊，快取中不可能有它。
  • Capacity（容量）：快取容量裝不下程式執行所需的所有區塊，被換出後又被用到。
  • Conflict（衝突）：在直接對映或組相聯中，多個區塊對映到同一組而互相替換。
  • Coherence（一致性）：多個處理器核心各有私有快取並共享資料時，某核心寫入使其他核心快取中的該區塊失效，之後再讀而造成的未命中。

選項分析

  • (A) 錯誤。 「快取無法容納執行所需的所有區塊」描述的是 capacity miss。compulsory miss 是第一次存取某區塊時必然發生的未命中，與快取大小無關。
  • **(B) 正確。
🔒

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

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

免費註冊

第 1-(5) 題2 分

Regarding cache design, which of the following descriptions is true?

(A) With the criteria of the identical entries, we need more tag bits in a multi-word cache than in a set-associative cache.
(B) Through interchanging the loops in a code, the cache miss rate cannot be degraded.
(C) Through the way prediction technique, the miss penalty during cache access can be reduced.
(D) If we pipeline the cache access, the cache bandwidth can be improved.

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

這一題的完整詳解

核心觀念

本題考查快取的標籤與索引位元、程式存取順序對區域性的影響，以及快取的路徑預測與管線化。設位址寬度為 AA 位元、每個快取區塊含 BB 個字、快取共有 LL 個區塊，則直接對映快取的標籤位元數為：

Tag bits=A−log⁡2L−log⁡2B\text{Tag bits}=A-\log_2 L-\log_2 B

其中 log⁡2L\log_2 L 是索引位元數，log⁡2B\log_2 B 是區塊內的字偏移位元數。組合式快取若有 WW 路，則集合數為 L/WL/W，標籤位元數為：

Tag bits=A−log⁡2(L/W)−log⁡2B\text{Tag bits}=A-\log_2(L/W)-\log_2 B

此外，快取的命中時間是判斷資料是否命中的時間；未命中代價是發生未命中後，取回資料所需的額外時間；頻寬則表示單位時間內可完成的存取數量。

解題方法

逐一檢查各選項的比較基準與所描述的效能指標。標籤位元要比較索引位元數；迴圈交換要看是否保留空間區域性；路徑預測影響快取存取路徑；管線化則主要提升單位時間內可處理的存取數。

選項分析

  • (A) 錯誤。 在位址寬度、區塊大小與快取區塊數相同的前提下，多字快取的直接對映索引位元為 log⁡2L\log_2 L。
🔒

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

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

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

Suppose we have a processor with a base CPI of 1.01.0, assuming all references hit in the primary cache, and a clock rate of 5 GHz5\text{ GHz}. Assume a main memory access time of 100 ns100\text{ ns}, including all the miss handling. Suppose the miss rate per instruction at the primary cache is 2%2\%.

第 2-(1) 題10 分

What is the CPI if this single-core processor only has one level of cache?

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

這一題的完整詳解

核心觀念

單層快取下，主快取未命中時須存取主記憶體。實際 CPI 等於理想基礎 CPI 加上每指令平均未命中停滯週期：

CPI=基礎 CPI+每指令未命中率×未命中代價（週期）\text{CPI} = \text{基礎 CPI} + \text{每指令未命中率} \times \text{未命中代價（週期）}

解題方法

處理器時脈為 5 GHz5\text{ GHz}，因此一個時脈週期的時間為：

Tcycle=15×109=0.2 nsT_{\text{cycle}} = \frac{1}{5\times 10^9} = 0.2\text{ ns}

主記憶體存取時間為 100 ns100\text{ ns}，換算成處理器週期：

🔒

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

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

免費註冊

第 2-(2) 題20 分

To speed up the process, we increase the CPU cores from a 1-core CPU to a 2-core CPU and retain other design settings. We assume 60%60\% of instructions must be executed sequentially. Please estimate the speedup ratio by using the new architecture.

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

這一題的完整詳解

核心觀念

本題考的是 Amdahl 定律：程式中必須循序執行的部分，即使增加處理器核心數，也無法藉由平行處理加速。若循序比例為 SS、可平行比例為 1−S1-S，使用 NN 個核心時的理想加速比為：

Speedup=1S+1−SN\text{Speedup}=\frac{1}{S+\frac{1-S}{N}}

解題方法

題目給定循序執行比例為 60%60\%，因此可平行執行的比例為 40%40\%。增加至兩個核心，代入 Amdahl 定律：

Speedup=10.60+0.402=10.80=1.25\text{Speedup} =\frac{1}{0.60+\frac{0.40}{2}} =\frac{1}{0.80} =1.25
🔒

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

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

免費註冊

第 3 題20 分

Assume a GPU architecture that contains 1010 SIMD processors. Each SIMD instruction has a width of 3232, and each SIMD processor contains 88 lanes for single-precision arithmetic and load/store instructions. This means that each non-diverged SIMD instruction can produce 3232 results every 44 cycles.

Assume a kernel that has divergent branches that cause, on average, 80%80\% of threads to be active. Assume that 70%70\% of all SIMD instructions executed are single-precision arithmetic and 20%20\% are load/store. Since not all memory latencies are covered, assume an average SIMD instruction issue rate of 0.850.85. Assume that the GPU has a clock speed of 1.5 GHz1.5\text{ GHz}. Please compute the throughput, in GFLOP/sec, for this kernel on this GPU.

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

這一題的完整詳解

核心觀念

單一 SIMD 處理器有 8 條運算 lane，但一條 SIMD 指令的寬度是 32，因此執行一條非分歧 SIMD 指令需要 4 個 cycle，平均每 cycle 產生 32/4=832/4=8 個結果。

計算整體浮點吞吐量時，需依序納入：

  • GPU 中的 SIMD 處理器數量。
  • 每個處理器每 cycle 可產生的結果數。
  • 分歧造成的平均活躍執行緒比例。
  • 浮點運算指令占全部 SIMD 指令的比例。
  • 實際指令發射率。
  • GPU 時脈。

解題方法

每個 SIMD 處理器每 cycle 的基準結果數為：

32 個結果4 cycles=8 個結果/cycle\frac{32\ \text{個結果}}{4\ \text{cycles}} =8\ \text{個結果/cycle}

10 個 SIMD 處理器的基準吞吐量為：

10×8=80 個結果/cycle10\times 8=80\ \text{個結果/cycle}
🔒

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

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

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

You are a system engineer. Today, you need to design a memory hierarchical system, including one CPU, one or two-level cache, one main memory, and one hard disk. Currently, you have the following design policies for the cache-level design:

Policy 1: With only L1 cache by using 2-way associativity.

Policy 2: With direct mapping L1 cache and 2-way associative L2 cache.

Policy 3: With 2-way associative L1 and L2 caches.

Assume that there is one embedded TLB in each cache level and one embedded page table in the main memory (i.e., we do not need extra memory to store the TLB and page table). On the other hand, the specifications of this memory hierarchical system are:

  • This is a 32-bit machine.
  • The base CPI is 1.01.0 and the clock rate is 5 GHz5\text{ GHz}.
  • Each cache block is a single-word block.
  • The L1 cache can contain 8 KB8\text{ KB} data.
  • The L2 cache can contain 16 KB16\text{ KB} data.
  • The page size is 2122^{12} bytes.
  • In the TLB and page table, we need to involve an extra one dirty bit to implement the write-back policy; one reference bit to approximate the LRU replacement policy; one valid bit to judge the data hit/miss.
  • The number of TLB entries in L1 and L2 caches are 1010 and 2020 respectively. Besides, the number of entries in the page table is 3030. To reduce the miss rate, the fully associative policy is adopted to implement the TLB and page table.

The following access and miss-rate information also applies:

  • Without considering the data transferring time, assume the access time of L2 cache is 5 ns5\text{ ns}, including all the miss handling; the access time of the main memory is 100 ns100\text{ ns}, including all the miss handling; the access time of the hard disk is 1 s1\text{ s}, including all the miss handling.
  • According to the data transference time between each memory level, ignore the data transference time between the L1 and L2 cache and the data transference time between the main memory and the lowest level cache and disk are both 50 ns50\text{ ns}, including all the miss handling.
  • In this system, the TLB will be located at the lowest level. When a data request comes, the TLB must be accessed first. If the TLB miss happens, we need to spend 10 ns10\text{ ns} to handle the TLB-miss exception.
  • When the direct mapping strategy is adopted, the miss rate of the L1 cache and the embedded TLB are both 2%2\%; the miss rate of the L2 cache and the embedded TLB are both 0.5%0.5\%.
  • If the 2-way mapping strategy is applied, the miss rate of the L1 cache and the embedded TLB are both 1%1\%; the miss rate of the L2 cache and the embedded TLB are both 0.1%0.1\%. At last, the miss rate of the main memory is 0.1%0.1\%.
  • During manufacturing, we need to spend 0.010.01 USD to handle one bit in each kind of memory.

第 4-(1) 題10 分

Please determine the number of bits required in the page table, TLB in the L1 cache, and TLB in the L2 cache.

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

這一題的完整詳解

核心觀念

虛擬位址由「虛擬頁號」與「頁內位移」組成。頁大小為 2122^{12} bytes，因此頁內位移需要 1212 bits；在 3232-bit 位址下，虛擬頁號需要 32−12=2032-12=20 bits。

每筆 TLB 或頁表對應一個虛擬頁到實體頁的映射，需保存：

  • 虛擬頁號：2020 bits
  • 實體頁號：2020 bits
  • Dirty、Reference、Valid 位元：各 11 bit，共 33 bits

題目指定頁表與 TLB 都採全相聯，因此每筆都要保存虛擬頁號作為比對標籤。

解題方法

每筆映射所需位元數為：

20+20+1+1+1=43 bits20+20+1+1+1=43\text{ bits}

分別乘上各結構的項目數：

🔒

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

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

免費註冊

第 4-(2) 題10 分

Please determine the number of bits required if:

(a) L1 cache is implemented by using 2-way associative mapping strategy.
(b) L2 cache is implemented by using 2-way associative mapping strategy.

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

這一題的完整詳解

核心觀念

快取的總位元數包含資料欄位與管理欄位。每個快取區塊除了資料，還要儲存標籤與有效位元；若採用 2-way 組相聯並以 LRU 近似替換，還要為每組儲存 1 個替換位元。

本題每個區塊是一個 32-bit word，因此每個區塊的資料欄位為 32 bits。位址以 byte 為單位，單字區塊需要 2 個區塊內位移位元。

解題方法

快取資料容量除以每個區塊的資料大小，可得區塊數。2-way 組相聯的組數為區塊數除以 2。標籤位元數則由位址欄位分割求得：

標籤位元數=32−區塊內位移位元數−組索引位元數\text{標籤位元數} =32-\text{區塊內位移位元數}-\text{組索引位元數}

總位元數計入資料、標籤、每區塊 1 個有效位元、每組 1 個 LRU 替換位元，再加上內嵌在該級快取中的 TLB。題幹指定的 dirty、reference、valid 三個位元是用於 TLB 與頁表；快取本身未指定寫回，因此快取區塊不另加 dirty bit。

TLB 每一筆：32-bit 位址、頁大小 2122^{12} bytes → 虛擬頁號 32−12=2032-12=20 bits、實體頁號 2020 bits；全關聯 TLB 以整個虛擬頁號當標籤，再加 dirty、reference、valid 3 bits：

20+20+3=43 bits / entry20+20+3=43\text{ bits / entry}

(a) L1 採 2-way 組相聯

L1 資料容量為 8 KB=81928\text{ KB}=8192 bytes，每個區塊為 4 bytes：

區塊數=81924=2048\text{區塊數}=\frac{8192}{4}=2048 組數=20482=1024,組索引位元數=log⁡21024=10\text{組數}=\frac{2048}{2}=1024,\qquad \text{組索引位元數}=\log_2 1024=10

區塊內位移需要 log⁡24=2\log_2 4=2 bits，因此標籤需要：

32−2−10=20 bits32-2-10=20\text{ bits}

每個區塊需要 32+20+1=5332+20+1=53 bits；每組另需 1 個 LRU 替換位元：

🔒

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

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

免費註冊

其他考古題

其他學校的資工系考古題

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