111 年國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《計算機系統（計算機組織）》考古題與詳解

Question 1

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 1. (15%) The three MIPS instruction formats are shown below: Name | Field size | Fields | Comments ------- | -------- | -------- | -------- R-format | 6 bits | op | rs | rt | rd | shamt | funct | All MIPS instructions are 32 bits long I-format | 6 bits | op | rs | rt | address/immediate | Arithmetic instruction format J-format | 6 bits | op | target address | Transfer, branch, imm. format | | | | Jump instruction format Consider the following while loop in MIPS assembler code: Loop: sll $t1, $t2, 2 add $t1, $t1, $s6 lw $t0, 0($t1) bne $t0, $s5, Exit addi $s3, $s3, 1 j Loop Exit: If we assume the loader places the Loop starting at location 80000 in memory, please determine the values of (a), (b), (c), (d), and (e), respectively, in order…

Accepted Answer

核心觀念 MIPS 指令依格式切分欄位： - R-format：op, rs, rt, rd, shamt, funct - I-format：op, rs, rt, immediate - J-format：op, target address 分支指令的立即數以「指令字」為單位，相對於 PC + 4 計算： $$ 	ext{branch offset}=\frac{	ext{目標位址}-(PC+4)}{4} $$ 跳躍指令的目標欄位則存放目標位址除以 $4$ 的結果。 解題方法 依序把每個空格對應到該指令的格式欄位。 1. sll $t1, $t2, 2 是 R-format。其 shamt 欄位就是位移量 $2$，所以 (a) = 2。 2. add $t1, $t1,

Question 2

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機組織(計算機組織)(300A) 2. (10%) (a) (5%) Suppose that the register $t1 contains the value of 0x10000000H and the register $t2 contains the value of 0x10000010H. Note that the MIPS architecture utilizes the big-endian addressing. Assume that the data (in hexadecimal) stored in memory at address 0x10000000H is: 0x44332211. What value is stored at the register pointed to by the register $t2? lbu $t0, 0($t1) sw $t0, 0($t2) (b) (5%) Followed by (a), what is the value of the register $t3 after the following instructions? slt $t3, $0, $t0 bne $t3, $0, ELSE j DONE ELSE: addi $t3, $t3, 2 DONE:

Accepted Answer

核心觀念 本題考查大端序的位元組排列、lbu 的零延伸、sw 的字組儲存，以及 slt 與條件分支的執行結果。 大端序表示較高位元組放在較低位址。lbu 讀取一個位元組並以零延伸至 32 位元；sw 則將 32 位元的值寫入指定記憶體位址。 解題方法 (a) 計算記憶體寫入值 位址 0x10000000 起的 32 位元資料為 0x44332211。依大端序排列： | 記憶體位址 | 位元組 | |---|---| | 0x10000000 | 0x44 | | 0x10000001 | 0x33 | | 0x10000002 | 0x22 | | 0x10000003 | 0x11 | 因此，lbu $t0, 0($t1) 從 0x10000000 讀出 0x44，並零延伸為： $$

Question 3

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 3. (10%) In this problem, we examine how data dependences affect execution in the classical 5- stage pipelined MIPS processor. (a) (5%) Assume that there is no delay slot and the branches execute in the ID stage. Assume further that there is full forwarding applied in the datapath. Please indicate hazards and add NOP instructions to eliminate them. add $t1, $s2, $s3 add $t2, $s4, $s5 beq $t1, $t2, Target (b) (5%) Followed by (a), please indicate hazards and add NOP instructions to eliminate them. lw $t1, 0($s1) beq $t1, $s2, Target

Accepted Answer

核心觀念 本題考典型五階段 MIPS 管線中的資料相依（RAW hazard）。指令依序經過 IF、ID、EX、MEM、WB；分支指令在 ID 階段比較暫存器，因此它必須在 ID 階段取得正確的比較值。 完整前遞可以把較早產生的結果送到分支比較器，但不能讓結果提早於它實際產生的階段： - ALU 指令的結果在 EX 階段產生；緊接著使用該結果的分支，需要等一個週期才能在 ID 階段取得前遞值。 - lw 的資料在 MEM 階段末才取得；緊接著使用該資料的分支，需要等兩個週期，才能在 ID 階段取得正確值。 解題方法 (a) beq 讀取 $t1、$t2。前兩個 add 分別寫入這兩個暫存器，形成 RAW 相依。第二個 add 是緊鄰 beq 的產生者，因此分支需停等一個週期。停等後，$t2 可由前遞取得，較早產生的 $t1 也可由前遞取得。

Question 4

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 4. (10%) Consider the following sequence of MIPS instructions being executed on a classical 5- stage pipelined datapath: addr5, r2, r1 lw r3, 4 (r5) lw r2, 0(r2) or r3, r5, r3 sw r3, 0(r5) Assume the following cycle time is required for different implementations: | Implementation | Without Forwarding | With Full Forwarding | |---|---|---| | Cycle Time | 200ps | 280ps | (a) (5%) If there is no forwarding or hazard detection, insert NOP instructions, if necessary, to ensure correct execution. What is the total execution time to execute the code sequence? (b) (5%) If the processor has full forwarding, insert NOP instructions, if necessary, to ensure correct execution. What is the total execution time to execute the code sequence?

Accepted Answer

核心觀念

本題考查 5 階段 MIPS 管線中的資料相依（RAW hazard），以及插入 NOP 後的執行時間。管線階段為：

\text{IF} \rightarrow \text{ID} \rightarrow \text{EX} \rightarrow \text{MEM} \rightarrow \text{WB}

不使用 forwarding 時，消費者必須等到生產者在 WB 階段寫回後，才能在 ID 階段讀到正確資料。以下採用常見假設：同一個週期內先寫回、再讀取，因此消費者可在生產者 WB 的同一週期讀取。

使用完整 forwarding 時，資料可由管線中的後續階段直接轉送給需要它的指令；本題依「完整 forwarding」的設定，包含轉送給 sw 的存入資料。

解題方法

將第一行依圖中指令讀作 add r5, r2, r1。原始指令序列為：

add r5, r2, r1
lw  r3, 4(r5)
lw  r2, 0(r2)
or  r3, r5, r3
sw  r3, 0(r5)

先找出會影響執行的資料相依：

add 產生 r5，下一條 lw 用 r5 當位址基底。
第一條 lw 產生 r3，or 會使用 r3；中間隔了一條 lw。
or 產生 r3，下一條 sw 將 r3 存入記憶體。

(a) 沒有 forwarding、沒有 hazard detection

沒有 forwarding 時，消費者的 ID 階段不能早於生產者的 WB 階段。

add 到第一條 lw：兩條指令相鄰，插入 2 個 NOP，讓 lw 在 add 的 WB 週期讀取 r5。

Question 5

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 5. (5%) When a program is running on multiple processors in a multiprocessor system, the execution time on each processor is comprised of computing time and the overhead time required for synchronization and to send data from one processor to another. Assume a program requires t = 100ms of execution time on one processor. When run p processors, each processor requires t/p ms, as well as an additional 40 ms of overhead, irrespective of the number of processors. Please compute for the speedup ratio for p = 8 and p = 16 processors, respectively.

Accepted Answer

核心觀念

加速比（speedup ratio）是單處理器執行時間除以多處理器的總執行時間：

\text{加速比}=\frac{\text{單處理器執行時間}}{\text{多處理器執行時間}}

題目給定單處理器執行時間 $t=100\text{ ms}$ 。使用 $p$ 個處理器時，計算時間為 $t/p$ ，另有固定 $40\text{ ms}$ 的同步與資料傳送額外負擔，因此：

T_p=\frac{t}{p}+40\text{ ms}

解題方法

$p=8$ ：

T_8=\frac{100}{8}+40=12.5+40=52.5\text{ ms}

Question 6

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 6. [10%] Consider two different implementations of the same instruction set architecture. The instructions can be divided into four classes according to their CPI (class A, B, C, and D). P1 with a clock rate of 2.5GHz and CPIs of 1, 3, 2, and 2, and P2 with a clock rate of 3 GHz and CPIs of 2, 2, 2, and 2. (a) [3%] The result of the benchmark running on the machine has an instruction count of 2.5E12, and execution time of 800 s, and a reference time of 9000 s. Find the CPI if the clock cycle time is 0.25 ns. (b) [3%] Find the increase in CPU time if the number of instructions of the benchmark is increased by 20% and the CPI is increased by 10%. (c) [4%] Given a program with a dynamic instruction count of 1.0E6 instructions divided into c…

Accepted Answer

核心觀念

處理器的 CPU 執行時間由指令數、平均每指令週期數（CPI）與時脈週期時間共同決定：

\text{CPU 時間}=\text{指令數}\times\text{平均 CPI}\times\text{時脈週期時間}

不同指令類別的 CPI 不同時，平均 CPI 要依各類指令所占比例加權計算。

解題方法

(a) 求平均 CPI

已知指令數為 $2.5\times10^{12}$ ，執行時間為 $800$ 秒，時脈週期時間為 $0.25\text{ ns}=0.25\times10^{-9}$ 秒。代入公式：

\text{CPI} =\frac{\text{CPU 時間}}{\text{指令數}\times\text{時脈週期時間}} =\frac{800}{(2.5\times10^{12})(0.25\times10^{-9})} =\frac{800}{625} =1.28

參考時間 $9000$ 秒不影響 CPI 的計算。

(b) 指令數與 CPI 增加後的 CPU 時間

Question 7

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 7. [10%] For the following calculation: (a) [3%] Assume 185 and 120 are unsigned 8-bit decimal integers store in sign-magnitude format. Calculate 185+122. As it is overflow, using the saturating arithmetic is needed. (b) [3%] Calculate the time necessary to perform a multiply using the approach (31 adders stacked vertically). If an integer is 8 bits wide and an adder takes 5 time unit. (c) [4%] What decimal number does the bit pattern 0x0E000000 represent if it is a floating point number? Use the IEEE 754 standard.

Accepted Answer

解題方法 原卷第 7 題 (a) 前句列出 185 與 120，運算式則是 $185+122$，並同時寫了 unsigned 與 sign-magnitude；以下依運算式及 8 位元無號整數解讀。(b) 題目列出 31 個垂直堆疊的加法器、8 位元整數與每個加法器 5 個時間單位；(c) 給定的位元樣式為 $0x0E000000$。其中 (b) 未交代「31 個加法器」是否指乘法路徑上的 31 個串接級，以下依原文數量作字面解讀，並列出標準 8 位元乘法的級數供對照。 核心觀念 - 8 位元無號整數的範圍是 $0$ 到 $2^8-1=255$。飽和運算在結果超出範圍時，將結果限制在可表示的最大值或最小值。 - 串接加法器的延遲由資料必須依序通過的級數決定：總延遲等於級數乘上單級延遲。 - IEEE 754 單精度浮點數由 1 位元符號、8 位元指數與 23 位元尾數組成；正規化數的指數需扣除偏移量 127。 (a) 無號 8 位元飽和加法 依題目明列的算式： $$ 185+122=307 $$ 無號 8 位元最大值為： $$ 2^8-1=255 $$ 因為 $307255$，飽和後取最大可表示值： $$ \boxed{255} $$ 若前句的 120 才是原意，則 $185+120=305$，仍超過 255，飽和結果也相同。8 位元 sign-magnitude 的範圍為 $-127$ 至 $127$，無法表示 185，因此本小題依「無號 8 位元」解讀。 (b) 乘法所需時間 依原文將 31 個垂直堆疊的加法器視為 31 個串接級，每級耗時 5 個時間單位：

Question 8

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 8. [10%] For a direct-mapped cache design with 32-bit address [31-0], the following bits of the address are used to access the cache: Tag field [31-14] Index field [13-5] Offset field [4-0] (a) [3%] How many entries does the cache have? (b) [3%] If 1 bit for the valid field is used, what is the total number of Kibits in a direct-mapped cache? (c) [4%] Assume the miss rate of an instruction cache is 4% and the miss rate of the data cache is 3%. The frequency of all loads and stores instruction is 32%. If a processor has a CPI of 2 without any memory stalls and the miss penalty is 100cycles for all misses, how much faster a processor would run with a perfect cache that never missed.

Accepted Answer

核心觀念 直接對映快取的位址切分為標籤、索引與位移欄位： - 索引欄位決定快取有幾個區塊（entries）。 - 位移欄位決定每個區塊可存多少位元組。 - 每個區塊所需位元數，包含資料、標籤與有效位元。 - 快取未命中造成的平均額外週期數，需分別計算指令快取與資料快取的影響。 （a）快取有幾個 entries？ 索引欄位為 $[13-5]$，共有 $13-5+1=9$ 個位元，因此快取 entries 數為： $$ 2^9=512 $$ 答案：512 個 entries。 （b）快取總容量 位移欄位為 $[4-0]$，共有 5 個位元，因此每個區塊可存： $$ 2^5=32	ext{ bytes}=32	imes 8=256	ext{ bits} $$ 標籤欄位 $[31-14]$ 有 $31-14+1=18$ 個位元。再加上 1 個有效位元，每個 entry 的總位數為： $$ 256+18+1=275	ext{ bits} $$ 快取共有 512 個 entries，總位數為： $$ 512	imes275=140{,}800	ext{ bits} $$ 以 $1	ext{ Kibit}=1024	ext{ bits}$ 換算：

Question 9

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 9. [10%] Caches are important to providing a high-performance memory hierarchy to processors. Below is a list of 32-bit memory address references, given as word addresses. 180, 3, 2, 43, 191, 88, 190, 14, 181, 44, 186, 253 (a) [3%] Assuming the cache is initially empty. For each of these references, given a direct- mapped cache with two-word blocks and a total size of 8 blocks. What is the hit rate? (b) [3%] If the miss stall time is 25 cycles and 3 cycles for access time, what is the total cycles for this cache? (c) [4%] For a three-way set associative cache (Way-0, Way-1 and Way-2) with two-word blocks and a total size of 24 words. Use LRU replacement. After the last word address "253" is accessed, what is the content of Way-1?

Accepted Answer

核心觀念

快取以「區塊」為單位存取。題目給的是字組位址，且每個區塊含 2 個字組，因此位址 $A$ 所在的區塊編號為

B=\left\lfloor\frac{A}{2}\right\rfloor

直接對映快取有 8 個區塊時，索引為 $B\bmod 8$ 。三路組合快取總容量為 24 個字組，每區塊 2 個字組，因此共有 12 個快取區塊、4 個組；索引為 $B\bmod 4$ 。

解題方法

(a) 直接對映快取命中率

逐筆計算區塊編號與索引，並依序更新快取內容：

位址	區塊編號 $B$	索引 $B\bmod 8$	結果
180	90	2	未命中
3	1	1	未命中
2	1	1	命中
43	21	5	未命中
191	95	7	未命中
88	44	4	未命中
190	95	7	命中
14	7	7	未命中
181	90	2	命中
44	22	6	未命中
186	93	5	未命中
253	126	6	未命中

位址 14 對應的區塊 7 與原先索引 7 的區塊 95 衝突，因此未命中並取代區塊 95。總計 12 次存取中命中 3 次：

\text{命中率}=\frac{3}{12}=25\%

(b) 快取總週期數

未命中次數為 $12-3=9$ 。每次存取需 3 週期，且每次未命中另外增加 25 週期停滯時間，因此

🔒

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

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

免費註冊

Question 10

台灣聯合大學系統111學年度碩士班招生考試試題 類組:電機類 科目:計算機系統(計算機組織)(300A) 10. [10%] Listed below are key page table parameters. A 4-entry TLB (translation-lookaside buffer) is used. Virtual address size 32 bits Page size 16 KiB Page table entry size 4 bytes (a) [3%] Which is the following statement correct? A. A larger page size reduces the TLB miss rate. B. A larger page size can lead to higher fragmentation and lower utilization of the physical memory. C. Fully associative TLB has a lower miss rate. D. On page fault, the page must be fetched from disk and write-through is strategy preferred. (b) [3%] For a single-level page table, how much physical memory is needed for storing the page table? (c) [4%] For a two-level page table approach with 256 entries. Assume each entry of the main page table is 6 bytes. C…

Accepted Answer

核心觀念 本題考查 TLB 的涵蓋範圍、分頁造成的內部碎裂，以及單層與兩層頁表的容量計算。 - TLB：快取近期使用的虛擬頁號與實體頁框對應。其涵蓋範圍為「項目數 $	imes$ 頁面大小」。 - 頁表項目數：每個虛擬頁面對應一個頁表項目，因此 $$ 	ext{虛擬頁面數}=\frac{	ext{虛擬位址空間大小}}{	ext{頁面大小}}。 $$ - 兩層頁表：第一層各項目指向一張第二層表；第二層表可依需求配置，不必一次全部建立。 解題方法 原卷表格給定：虛擬位址為 32 位元、頁面大小為 16 KiB、頁表項目大小為 4 位元組，另有 4 個項目的 TLB。第 (c) 小題未明示 256 個項目所屬層級；以下以 第一層主頁表有 256 個項目，且至少配置一張第二層表 計算最小容量。 (a) 選項分析 A：正確。 固定 TLB 項目數時，頁面越大，TLB 可涵蓋的位址範圍越大。本題原本的涵蓋範圍為 $$ 4	imes16	ext{ KiB}=64	ext{ KiB}。 $$ 增大頁面後，相同大小的工作集合所需頁面數減少，通常可減少 TLB 的容量失誤，降低失誤率。 B：正確。 分頁以整個頁框為單位配置記憶體。程式使用量未填滿最後一頁時，剩餘空間形成內部碎裂。頁面越大，未使用的空間可越多，因此會降低實體記憶體利用率。 C：正確。 全相聯 TLB 允許任一虛擬頁的對應放入任一項目，相較於直接對映或較低相聯度，可消除因映射位置限制產生的衝突失誤，因此有助於降低失誤率；但仍會有首次存取失誤與容量失誤。 D：錯誤。 缺頁時，若所需頁面位於磁碟，須將它載入實體記憶體；但虛擬記憶體通常採用寫回（write-back），只在換出已修改的髒頁時寫回磁碟。寫入直達（write-through）會使每次修改都涉及磁碟寫入，成本過高，並非優先採用的策略。此外，需求零填頁等缺頁也不需要從磁碟讀取既有頁面內容。 因此選 A、B、C。 (b) 單層頁表所需容量 頁面大小為 $$ 16	ext{ KiB}=2^{14}	ext{ 位元組}， $$ 故頁內位移占 14 位元，虛擬頁號占 $$ 32-14=18	ext{ 位元}。 $$

記憶體位址	位元組
`0x10000000`	`0x44`
`0x10000001`	`0x33`
`0x10000002`	`0x22`
`0x10000003`	`0x11`

111 年國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《計算機系統（計算機組織）》

第 1 題15 分

核心觀念

解題方法

第 2 題10 分

核心觀念

解題方法

第 3 題10 分

第 4 題10 分

核心觀念

解題方法

(a) 沒有 forwarding、沒有 hazard detection

第 5 題5 分

核心觀念

解題方法

第 6 題10 分

核心觀念

解題方法

第 7 題10 分

第 8 題10 分

核心觀念

（a）快取有幾個 entries？

（b）快取總容量

第 9 題10 分

核心觀念

解題方法

(a) 直接對映快取命中率

(b) 快取總週期數

第 10 題10 分

核心觀念

解題方法

(a) 選項分析

(b) 單層頁表所需容量

其他考古題

111 年臺灣聯合大學系統的其他科目

臺灣聯合大學系統《計算機系統》其他年度

其他學校的電機系考古題

Address	Opcode	Field 1	Field 2	Field 3	Field 4	(a)
80000	0	0	19	9	(a)	0
80004	0	9	22	(b)	0	32
80008	35	9	8	(c)
80012	5	8	21	(d)
80016	8	19	19	1
80020	2			(e)
80024

111 年 國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《計算機系統（計算機組織）》

第 1 題15 分

核心觀念

解題方法

第 2 題10 分

核心觀念

解題方法

第 3 題10 分

第 4 題10 分

核心觀念

解題方法

(a) 沒有 forwarding、沒有 hazard detection

第 5 題5 分

核心觀念

解題方法

第 6 題10 分

核心觀念

解題方法

第 7 題10 分

第 8 題10 分

核心觀念

（a）快取有幾個 entries？

（b）快取總容量

第 9 題10 分

核心觀念

解題方法

(a) 直接對映快取命中率

(b) 快取總週期數

第 10 題10 分

核心觀念

解題方法

(a) 選項分析

(b) 單層頁表所需容量

其他考古題

111 年臺灣聯合大學系統的其他科目

臺灣聯合大學系統《計算機系統》其他年度

其他學校的電機系考古題

111 年國立臺灣聯合大學系統（清華、政治、陽明交通、中央四校聯招）研究所電機類《計算機系統（計算機組織）》