114 年國立成功大學資訊工程系碩士班《計算機組織與系統》考古題與詳解

Question 1

$LALB$

Accepted Answer

核心觀念

兩層記憶體階層中，成本較高的上層記憶體通常設計為容量較小、存取較快；成本較低的下層記憶體則用來提供較大的儲存容量。因此，合理的階層配置應滿足 $L_A<L_B$ 。

解題方法

原卷圖中可讀到 $C_A>C_B$ ，且處理器先查詢 $A$ ；若 $A$ 沒有資料，再由 $B$ 提供資料並填入 $A$ 。為了降低平均存取延遲， $A$ 必須比 $B$ 快，也就是 $L_A<L_B$ 。

若 $A$ 命中率為 $h$ ，平均存取延遲可表示為

hL_A+(1-h)(L_B+L_A)

Question 2

$SA CASB CB$

Accepted Answer

核心觀念 $CA$、$CB$ 是每位元的成本，$SA$、$SB$ 是容量，因此兩層記憶體的總成本分別為 $$ 	ext{Cost}A=SA CA,\qquad 	ext{Cost}B=SB CB $$ 已知 $CACB$，只代表 A 的單位容量成本較高；這不足以比較兩者的總成本。總成本比較還需要知道 $SA$ 與 $SB$ 的大小或比例。 解題方法 直接檢查題目給的條件能否推出 $SA CASB CB$。題目沒有提供容量關係，因此這個不等式不能由 $CACB$ 單獨推出。例如，若 A 容量小到 $SA CA<SB CB$，不等式便不成立；若 A 容量較大，則可能成立。

Question 3

None is true.

Accepted Answer

核心觀念 這是兩層記憶體階層（$A$ 在上、$B$ 在下）：處理器先存取 $A$，未命中才到 $B$ 取資料並放進 $A$。要達到「具成本效益、平均存取延遲最小」的設計，上層 $A$ 必須是小而快（每位元貴），下層 $B$ 是大而慢（每位元便宜）： $$ 	ext{AMAT}=LA+(1-h)\cdot(	ext{未命中代價}), $$ 讓大部分存取在快的 $A$ 命中，大量資料則放在便宜的 $B$。 解題方法 本小題「None is true」要先判斷同組的 (a)、(b)：

Question 4

$Pr(XA\geq 101\mid XA\geq 100)=Pr(XA\geq 111\mid XA\geq 110)$

Accepted Answer

核心觀念 指數分布具有無記憶性。若 $X\sim\operatorname{Exp}(\lambda)$，則對任意 $s,t\geq 0$： $$ \Pr(X\geq s+t\mid X\geq s)=\Pr(X\geq t) $$ 也就是說，已經存活 $s$ 時，接下來至少再存活 $t$ 的機率，與先前已存活多久無關。 解題方法 題目兩側都使用 $XA$，因此皆採用 $\lambdaA=100$。指數分布的存活函數為： $$ \Pr(XA\geq x)=e^{-\lambdaA x} $$ 利用條件機率公式：

Question 5

If we employ the shortest job scheduling, then $A$ shall be scheduled first and then $B$.

Accepted Answer

核心觀念

Shortest Job Scheduling（最短工作優先排程）會先執行預期執行時間較短的工作。指數分布的機率密度函數為

f(x)=\lambda e^{-\lambda x},\qquad x\ge 0

其期望值為

E[X]=\frac{1}{\lambda}

因此， $\lambda$ 越大，平均執行時間越短。

解題方法

比較兩個程序的平均執行時間：

E[X_A]=\frac{1}{\lambda_A}=\frac{1}{100}

Question 6

For any scheduling policy, the total expected time to finish both tasks is $300$.

Accepted Answer

核心觀念 指數分布的機率密度函數為 $f(x)=\lambda e^{-\lambda x}$，其期望值為 $$ \mathbb{E}[X]=\frac{1}{\lambda} $$ 因此，$\lambda$ 是執行時間的速率參數，並非平均執行時間。單一處理器依序完成兩個工作時，若排程不讓處理器閒置，完成兩個工作的總時間等於兩者所需執行時間之和。 解題方法 兩個工作都在時間 $0$ 就緒。單一處理器完成兩者所需的總服務時間為 $XA+XB$，所以總完成時間的期望值為

Question 7

Partition $S$ into a number of disjoint blocks $\{s\}$, i.e., $S=\bigcup\{s\}$. Each block $s\in S$ serves as a fetching unit between the memory and disk subsystems. Given $(x,y)\in s$, we allocate a memory block $m$ to store $s$ copied from the disk. Then, retrieve $(x,y)$ from $m$ and deliver the result for $\operatorname{READ}(\cdot)$. For efficiency, the keys in $m$ shall be organized in a balanced search tree, for example.

Accepted Answer

核心觀念 本題考磁碟區塊快取＋記憶體內索引。磁碟存取延遲比記憶體高好幾個數量級，因此： 1. 以「區塊」為單位在磁碟與記憶體之間搬資料，一次 I/O 就帶回同一區塊內的多組鍵值，後續存取同區塊的鍵值不必再讀磁碟（利用區域性）。 2. 區塊載入記憶體後，用平衡搜尋樹組織其中的鍵，查找時間為 $O(\log n)$（$n$ 為區塊內鍵數），比線性掃描快。 解題方法 依題意逐步檢查這個 READ 設計： - 把 $S$ 切成互斥區塊 $\{s\}$，每個區塊是磁碟與記憶體之間的搬移單位——這就是快取區塊（block／page）的作法。

Question 8

For $\operatorname{WRITE}(\cdot)$, update $(x,y)$ in $m$. When $m$ is replaced, $m$ shall be written back to $\mathcal{F}$ and the original $s\in\mathcal{F}$ may be overwritten.

Accepted Answer

核心觀念 本題考查寫回式快取（write-back cache）。將資料先更新在較快的主記憶體 $m$ 中，延後到快取項目被替換時才寫回磁碟檔案 $\mathcal{F}$，可縮短 WRITE 等待磁碟寫入的時間。 這種設計要維持正確性，讀取時必須先檢查 $m$，確保取得最新值；READ 與 WRITE 並行時，也須同步存取共享資料。 解題方法與選項分析 此設計將 $(x,y)$ 先寫入 $m$，而非每次呼叫 WRITE 都立即更新 $\mathcal{F}$。因此，寫入可以較快完成；

Question 9

We shall additionally create a local file index $J$ in the file system for locating $(x,y)$ in $S$. That is, $J$ helps rapidly identify which $s\in S$ stores $(x,y)$. $J$ shall be replicated in the memory (denoted by $J^$) to minimize the number of I/O operations performed over the disk subsystem. $J^$ is updated for newly arriving $(x,y)$ due to $\operatorname{WRITE}(\cdot)$. Consequently, $J^$ and $J$ may be inconsistent.

Accepted Answer

核心觀念 本題考索引的記憶體快取（write-back 式的索引）。磁碟上的索引 $J$ 可以快速找到某個鍵 $(x,y)$ 在哪一個區塊 $s$；把 $J$ 複製一份 $J^$ 放在記憶體中，查索引就不必讀磁碟。 解題方法 逐項檢查這個設計： 1. 建立索引 $J$：不用掃描整個檔案就能定位 $(x,y)$ 所在的區塊，減少讀取時的磁碟 I/O。 2. 在記憶體保留副本 $J^$：每次 READ／WRITE 查索引都在記憶體完成，進一步省掉讀索引的 I/O。 3. WRITE 新增鍵值時只更新 $J^$：避免每次寫入都要同步寫磁碟上的索引，降低 WRITE 的延遲。

Question 10

Possibly, multiple $\operatorname{WRITE}(\cdot)$ operations address the identical key $x$. These $\operatorname{WRITE}(\cdot)$ operations may be concurrently invoked by distinct clients. One potential implementation is that each $\operatorname{WRITE}(\cdot)$ successfully acquires the locks for accessing both $m$ and $J^$ before the $\operatorname{WRITE}(\cdot)$ can proceed to update the value of $x$. Once the value is committed, both locks are released. With such an implementation, it is NOT possible to introduce deadlock due to various $\operatorname{WRITE}(\cdot)$ operations.

Accepted Answer

核心觀念 這題考多執行緒的死結（deadlock）與鎖定順序。死結可能發生的必要條件之一，是不同執行緒各自持有資源，並等待對方持有的資源。若兩個寫入操作都要取得互斥鎖 $m$ 與 $J^$，取得鎖的順序會影響是否可能形成死結。 解題方法 檢查能否安排出一個執行順序，使兩個寫入操作各持有一把鎖，同時等待另一把鎖。若能，題目所稱「不可能發生死結」便不成立。 選項分析 題述為錯誤（$	imes$）。題目沒有規定所有寫入操作必須按同一順序取得兩把鎖，因此可能發生以下情況：

Question 11

In the design of a microprocessor, the instruction set architecture of the processor completely hides all physical implementation details.

Accepted Answer

核心觀念 指令集架構（ISA）是軟體與處理器硬體之間的介面，定義程式可見的行為，例如指令功能、暫存器、資料型態、記憶體定址方式、例外處理與記憶體一致性規則。不同處理器可以用不同的微架構實作同一套 ISA，執行相同程式並產生符合 ISA 規範的結果。 微架構與實體設計則描述處理器如何實際完成這些行為，例如管線深度、快取配置、執行單元、電路與版圖。 解題方法 判斷關鍵在於區分「ISA 抽象掉多數實作細節」與「ISA 完全隱藏所有實體細節」。只要仍有硬體行為會影響程式可觀察的結果，或 ISA 本身規範了某些硬體相關行為，就不能說是完全隱藏。 選項分析

Question 12

For a given problem, the speedup achieved by a multicore processor is a critical factor in assessing the processor design. A multicore system exhibits strong scaling when the speedup is achieved without increasing the problem size, $S$, where the memory size utilized by each processor core is $S$.

Accepted Answer

核心觀念 這題考查平行系統的強擴展（strong scaling）與弱擴展（weak scaling），關鍵在於增加處理器核心時，總問題規模是否固定。 若總問題大小固定為 $S$，使用 $p$ 個核心時，每個核心平均分配的工作量約為 $S/p$。這是強擴展。其加速比可寫為： $$ \operatorname{Speedup}(p)=\frac{T1(S)}{Tp(S)} $$ 其中 $T1(S)$ 是單核心處理規模為 $S$ 的問題所需時間，$Tp(S)$ 是 $p$ 個核心處理同一規模問題所需時間。 解題方法 判斷敘述中的問題大小如何隨核心數改變。強擴展要求增加核心數時，總問題大小維持為 $S$。

Question 13

In the design of a multi-level processor cache, it is critical to balance between miss rate and miss penalty. The design of the first-level caches focuses on miss rate reduction, so larger cache blocks are desired to reduce the miss rate. The design of the second-level caches puts emphasis on miss penalty improvement to avoid higher memory access latencies.

Accepted Answer

核心觀念

多層快取的目標，是降低處理器平均記憶體存取時間（AMAT），而不是只追求某一層的最低未命中率。兩層快取的簡化公式為：

\mathrm{AMAT} = T_{L1} + MR_{L1}\bigl(T_{L2}+MR_{L2}\times P_{\mathrm{mem}}\bigr)

其中 $T_{L1}$ 、 $T_{L2}$ 是各層命中時間， $MR_{L1}$ 、 $MR_{L2}$ 是各層的區域未命中率， $P_{\mathrm{mem}}$ 是主記憶體存取所造成的未命中代價。

解題方法與敘述判斷

判斷快取區塊大小時，要看它對命中時間、未命中率與未命中代價的影響，而不能只看區塊變大是否能利用空間區域性。

**第一層快取（L1）**緊接處理器，命中時間對整體效能影響很大，因此設計重點是快速命中。區塊變大雖能利用空間區域性，降低部分未命中，卻也可能增加命中時間、區塊填入時間與頻寬需求。因此 L1 常採用較小的區塊，以兼顧快速命中與較低的未命中代價。

Question 14

In the design of a pipelined processor, it is important to allow instructions to take fewer clock cycles in order to increase overall pipeline performance. A common practice is to make ALU instructions take fewer cycles to improve the processor throughput.

Accepted Answer

核心觀念 本題考查指令延遲（latency）與處理器吞吐量（throughput）的差別。 - 延遲：一條指令從開始執行到完成所需的時間或時脈週期數。 - 吞吐量：單位時間內完成多少條指令。 - 在理想的 $k$ 階管線中，指令可能需要 $k$ 個週期才完成，但管線填滿後，理想情況下仍可每個週期完成一條指令。因此，單條指令所需週期數較少，不代表整體吞吐量必然提高。 解題方法 判斷敘述時，先看它把哪種效能指標和哪種設計手段連在一起。題目主張「讓指令使用較少時脈週期」是提升管線處理器吞吐量的重要方法，並舉 ALU 指令為例。這把減少單一指令的延遲直接當成提升整體吞吐量，兩者並不等價。

Question 15

In the design of arithmetic logic units, the speed of addition depends highly on the number of bits involved. As the number of bits increases, more 1-bit adders are required to calculate the sum of each bit, and it leads to longer delays to obtain the sum for all bits involved.

Accepted Answer

核心觀念

加法器的延遲取決於進位如何傳遞，不只取決於位元數。常見的漣波進位加法器（ripple-carry adder）由每一位的全加器串接而成，某一位產生的進位必須依序傳到高位，因此位元數增加時，最壞情況的延遲也會增加。

對第 $i$ 位，可用產生進位與傳遞進位表示：

G_i = A_iB_i,\qquad P_i = A_i \oplus B_i

C_{i+1}=G_i+P_iC_i

在漣波進位架構中， $C_{i+1}$ 必須等待 $C_i$ ，進位逐位傳遞；若每級延遲近似固定， $n$ 位加法器的最壞延遲約與 $n$ 成正比，即 $O(n)$ 。

解題方法與敘述分析

判斷此敘述時，要區分「漣波進位加法器」與「所有加法器設計」。題目描述的「更多 1-bit 加法器串接，導致更長延遲」符合漣波進位加法器，但不能推廣到所有算術邏輯單元中的加法器

Question 16

For the PC-relative addressing in RISC-V processors, the SB-format branches have a 12-bit address immediate and the UJ-format jumps have a 20-bit address immediate. These formats mean that a RISC-V program can branch within $\pm 2^{10}$ words of the current instruction and jump within $\pm 2^{18}$ words of the current instruction, if the PC is used as the register to be added to the address.

Accepted Answer

核心觀念 本題考查 RISC-V 的 PC-relative 定址，以及 SB（分支）與 UJ（JAL 跳躍）格式如何由編碼欄位還原位移量。雖然格式分別編碼 12 位與 20 位立即值，位移量的最低位元固定為 $0$，因此實際位移的範圍比欄位位數所表示的範圍多一個位元。 解題方法 RISC-V 的分支與 JAL 目標位址皆以目前指令的 PC 為基準： $$ 	ext{target} = PC + 	ext{sign-extended immediate} $$ SB 格式的立即值經符號延伸後，最低位補 $0$，所以位移量以 2 位元組為單位，範圍為： $$ -2^{12} \leq 	ext{offset} \leq 2^{12}-2 $$ 若以 4 位元組為一個 word 換算，這相當於約 $-2^{10}$ 到 $+2^{10}$ 個 word 的範圍。 UJ 格式同樣將符號延伸後的立即值最低位補 $0$，位移量範圍為： $$ -2^{20} \leq 	ext{offset} \leq 2^{20}-2 $$

Question 17

Which variables demonstrate temporal locality in their references?

Accepted Answer

核心觀念 時間區域性（temporal locality）是指某個記憶體位置被存取後，短時間內很可能再次被存取。空間區域性（spatial locality）則是指存取某位置後，附近位置也很可能被存取。 解題方法 固定一個 $x$，內層迴圈讓 $y$ 從 $0$ 跑到 $7999$。 - $M[x][0]$ 在每次內層迴圈都會被讀取，因此同一個元素會連續被引用 $8000$ 次，具有明顯的時間區域性。 - 迴圈變數 $x$、$y$ 在每次迭代都被讀取（比較、遞增、計算位址），同一個變數反覆使用，也具有時間區域性（它們通常放在暫存器中）。

Question 18

Which variables demonstrate spatial locality in their references?

Accepted Answer

核心觀念 空間區域性（spatial locality）是指：程式存取某個記憶體位置後，接著也會存取附近的記憶體位置。若陣列每列連續儲存，沿著欄索引逐一存取同一列的元素，就會呈現空間區域性。 每個元素是 32 位元浮點數，因此每個元素占 $4$ bytes。相鄰欄位的位址相差 $4$ bytes。 解題方法 固定 $x$，內層迴圈讓 $y$ 從 $0$ 遞增至 $7999$： - N[x][y] 每次讀取並寫回目前元素；下一次存取的是 N[x][y+1]。兩者在記憶體中相鄰，位址只差 $4$ bytes，因此 N 的參考具有空間區域性。 - M[x][0] 在同一列的內層迴圈中始終是同一個元素。重複存取同一位址屬於時間區域性，不是空間區域性。

Question 19

If the cache size is unlimited, how many cache blocks, each with 4 words, are required to store all the referenced matrix elements?

Accepted Answer

核心觀念

快取區塊數要計算「所有被存取元素分布在哪些不同的區塊」，而不是計算存取次數。每個元素是 1 個 word，每個區塊可容納 4 個 word。

迴圈會讀寫完整的 $N$ 矩陣，並反覆讀取 $M$ 矩陣每一列的第一個元素 $M[x][0]$ 。同一個元素在迴圈中被重複存取，仍只算其所在的區塊一次。

解題方法

假設兩個矩陣分別存放，且各自從區塊邊界開始。

計算 $N$ 的區塊數：

$N$ 有 8 列，每列 8000 個元素，因此共有

8 \times 8000 = 64000 \text{ 個元素}

由於每個區塊可存放 4 個元素，儲存這些元素需要

\frac{64000}{4} = 16000 \text{ 個區塊}

Question 20

Assume that the data in the two arrays, $N$ and $M$, are streaming over the Internet (similar to a video streaming application) with predictable data accessing patterns. What technique can be used to bring up adjacent cache blocks into a buffer within the processor core to reduce the data accessing time? Note that when the data is found in the buffer, it is considered as a hit and moved into the cache for the next block. Please provide a detailed explanation of how this technique works.

Accepted Answer

核心觀念 本題考查串流緩衝區（stream buffer）預取。當程式的存取模式可預測、且會依序讀取連續記憶體區塊時，處理器可以在目前區塊尚未用完前，先把後續相鄰的快取區塊取入處理器核心內的緩衝區，降低之後存取時等待主記憶體的時間。 串流緩衝區位於一般快取之外，用來暫存預取進來的區塊。若處理器要求的資料已在串流緩衝區中，就視為命中；該區塊會送入快取，供後續存取使用。 解題方法 題目中的陣列採列優先儲存，因此固定 $x$、讓 $y$ 逐一增加時，$N[x][y]$ 是依序存取的連續元素。每個元素為 32 位元，也就是 4 位元組；每次快取區塊通常會包含多個相鄰元素。因此存取一個區塊時，後續的 $N[x][y]$ 很可能位於相鄰區塊，適合採用串流預取。 另一方面，$M[x][0]$ 在固定 $x$ 的內層迴圈中會重複使用 8000 次，具有時間區域性，通常可由快取留存。題目所問的「預先把相鄰區塊放入核心內緩衝區」，主要針對連續掃描的 $N$ 資料流。 串流緩衝區如何運作

114 年 國立成功大學資訊工程系碩士班《計算機組織與系統》

第 1-(a) 題5 分

核心觀念

解題方法

第 1-(b) 題5 分

第 1-(c) 題5 分

核心觀念

解題方法

第 2-(a) 題5 分

核心觀念

解題方法

第 2-(b) 題5 分

核心觀念

解題方法

第 2-(c) 題5 分

第 3-(a) 題5 分

核心觀念

解題方法

第 3-(b) 題5 分

核心觀念

解題方法與選項分析

第 3-(c) 題5 分

核心觀念

解題方法

第 3-(d) 題5 分

第 4-(a) 題5 分

第 4-(b) 題5 分

核心觀念

解題方法

第 4-(c) 題5 分

核心觀念

解題方法與敘述判斷

第 4-(d) 題5 分

核心觀念

解題方法

第 4-(e) 題5 分

核心觀念

解題方法與敘述分析

第 4-(f) 題5 分

第 5-(a) 題5 分

第 5-(b) 題5 分

第 5-(c) 題5 分

核心觀念

解題方法

第 5-(d) 題5 分

核心觀念

解題方法

串流緩衝區如何運作

其他考古題

114 年成功大學的其他科目

成功大學《計算機組織與系統》其他年度

其他學校的資工系考古題

114 年國立成功大學資訊工程系碩士班《計算機組織與系統》