108 年 國立成功大學人工智慧科技碩士學位學程《計算機組織與系統》

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

第 1 題20 分

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.
35, 149, 43, 90, 191, 91, 148, 14, 42, 190, 69, 15

(1) [8%] For each of these references, identify the tag and the index given a direct-mapped L1 cache with two-word blocks and a total size of 16 words. Also list if each reference is a hit or a miss, assuming the cache is initially empty.
(2) [8%] For each of these references, identify the tag and the index given a four-way set-associative L1 cache with two-word blocks and a total size of 16 words. Also list if each reference is a hit or a miss, assuming the cache is initially empty and LRU replacement is used.
(3) [4%] Given the above memory address reference, what is the average memory access time (AMAT) if the hit time of the directed-mapped L1 is one cycle and main memory access takes 200 cycles. What is the AMAT of the four-way set-associative cache if the hit time is 2 cycles and main memory access also takes 200 cycles?

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

這一題的完整詳解

(1) 直接映射（2‑字塊、16字總容量）

位址Block = ⌊Addr/2⌋Index = Block mod 8Tag = ⌊Block/8⌋命中/未命中
351712Miss
1497429Miss
432152Miss
904555Miss
19195711Miss
914555Hit
1487429Hit
14770Miss
422152Miss
19095711Miss
693424Miss
15770Miss

(2) 四路組合（2‑字塊、16字總容量）

  • 每組 4 行 ⇒ 組數 = 8 塊 ÷ 4 = 2 組
  • Index 位元 = 1 位 (組號)
位址BlockSet = Block mod 2Tag = ⌊Block/2⌋命中/未命中
🔒

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

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

免費註冊

第 2 題15 分

Consider a sequential C program as illustrated in the figure below. The program is divided into four code segments, T1, T2, T3, and T4. We profile the program execution time on the single-core MIPS processor and the execution time for the code segments is: 2ms for T1, 8ms for T2, 16ms for T3, and 2ms for T4. Moreover, two different processor variants are available: one is the quad-core MIPS processor (with the same instruction set architecture as the single-core processor), and the other one is the single-core MIPS processor with an 8-wide SIMD engine. Assume we have converted the program into parallel versions suitable for the two processors, respectively. Please answer the following questions.

void main () {
T1
//Some initialization code.
T2
for (i=0; i <10000; i++)
for (j=0; j<10000; j++)
Y [j] [i] = Y [j-1][i-1]+2;
T3
for (i=0; i <10000; i++)
T4
for (j=0; j<10000; j++)
X [i][j] = Y [j] [i] * 5;
// Some finalization code.
}
🖼️【此處有附圖，請對照原卷】

(1) [6%] Parallelize the program suitable for the multicore processor and calculate the speedup of the parallelized program.
(2) [6%] Parallelize the program suitable for the processor with the SIMD engine and calculate the speedup of the parallelized program.
(3) [3%] Based on the speedups calculated in (1) and (2), please determine which processor is faster? Why?

🖼️ 本題含圖表，以下為原卷對應頁面：
原卷第 2 頁

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

這一題的完整詳解

核心觀念

本題考查平行化、Amdahl 定律，以及多核心與 SIMD 的執行時間比較。

假設平行化沒有額外負擔，若某程式區段可平均分配給 pp 個運算單元，執行時間可估為原時間的 1/p1/p。各區段的總執行時間相加後，速度提升比為

Speedup=單核心原始執行時間平行化後執行時間\text{Speedup} = \frac{\text{單核心原始執行時間}} {\text{平行化後執行時間}}

單核心原始執行時間為

T原始=2+8+16+2=28 msT_{\text{原始}}=2+8+16+2=28\text{ ms}

T1T_1 和 T4T_4 是初始化與收尾區段，題目未給出可平行化的內容，因此視為維持原時間。T2T_2 與 T3T_3 的迴圈中，各次迭代可平行處理。

解題方法

（1）四核心多核心處理器

在 T2T_2 中固定 ii 後，各個 jj 迭代讀取前一欄 Y[j−1][i−1]Y[j-1][i-1]，並寫入不同的 Y[j][i]Y[j][i]，彼此獨立。因此可把內層 jj 迴圈分配給四個核心。T3T_3 的各次迭代也互相獨立，可同樣分配給四個核心。

概念上的平行化方式如下：

T1

for each i:
    parallel_for each j:
        Y[j][i] = Y[j-1][i-1] + 2

parallel_for each (i, j):
    X[i][j] = Y[j][i] * 5

T4

T2T_2 和 T3T_3 仍須依原程式順序執行，因為 T3T_3 會讀取 T2T_2 計算完成的 YY。

四核心下，平行化後執行時間為

T四核心=2+84+164+2=10 msT_{\text{四核心}} = 2+\frac{8}{4}+\frac{16}{4}+2 = 10\text{ ms}

因此速度提升比為

Speedup四核心=2810=2.8\text{Speedup}_{\text{四核心}} = \frac{28}{10} = 2.8

（2）八路 SIMD 單核心處理器

🔒

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

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

免費註冊

第 3 題15 分

Determine whether each of the following statements is True (T) or False (F), and explain your answer.

(1) [3%] Graphics applications deliver higher performance because the DRAM chips on GPU cards help reduce memory latency.
(2) [3%] A shared memory can be created for computer clusters to exchange data.
(3) [3%] A GPU is always faster than a CPU at the cost that the GPU has higher power consumption.
(4) [3%] Given the two-level caches, the purpose of the first-level cache is more about miss rate, and the purpose of the second-level cache is more about hit time.
(5) [3%] Associativity of the addition operations holds for both integer and floating-point numbers.

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

這一題的完整詳解

核心觀念

本題綜合考查 GPU 與 CPU、叢集記憶體模型、多層快取，以及整數與浮點數運算的代數性質。

  • 記憶體延遲（latency）：完成一次記憶體存取所需的時間。
  • 記憶體頻寬（bandwidth）：單位時間可傳輸的資料量。
  • 共享記憶體（shared memory）：多個處理器可透過共同位址空間交換資料；叢集也可透過分散式共享記憶體（Distributed Shared Memory, DSM）建立此抽象。
  • 快取效能：由命中時間（hit time）、未命中率（miss rate）與未命中代價共同決定。
  • 加法結合律：
    (a+b)+c=a+(b+c)(a+b)+c=a+(b+c)
    整數通常滿足此性質，但浮點運算會因有限精度與捨入而不滿足。

解題方法

逐項判斷敘述中的因果關係是否正確，特別注意：

  1. GPU 的優勢是平行處理能力與記憶體頻寬，不可把頻寬誤認為延遲。
  2. 區分叢集的實體記憶體架構與可建立的共享記憶體抽象。
  3. 遇到「always」等絕對敘述，檢查是否存在反例。
  4. 以兩層快取的平均記憶體存取時間判斷設計重點。
  5. 對浮點加法直接測試結合律，利用捨入誤差找反例。

選項分析

（1）判定：F

GPU 圖形應用程式的高效能，主要來自：

  • 大量運算單元所提供的資料平行性；
  • GPU 適合以 SIMT 方式同時處理大量相似工作；
  • GDDR 或 HBM 等記憶體提供較高的記憶體頻寬；
  • 大量執行緒可以隱藏記憶體存取延遲。

GPU 卡上的 DRAM 主要改善的是記憶體頻寬，不代表一定降低記憶體延遲。GPU 記憶體的單次存取延遲甚至可能高於 CPU 的快取與記憶體系統，因此本敘述把「高頻寬」錯誤地說成「低延遲」。

（2）判定：T

一般叢集中的每台電腦都有自己的處理器與本地記憶體，原生屬於分散式記憶體系統；節點之間通常透過網路傳送訊息。

不過，可以利用硬體或軟體建立分散式共享記憶體（DSM），將多台節點的記憶體組合成一個共享位址空間，使程式能以讀寫共享記憶體的方式交換資料。

這裡的共享記憶體是邏輯上的抽象，不代表所有節點直接連接到同一顆實體 DRAM。跨節點資料存取仍須經過網路，延遲與一致性管理成本也較高。因此「可以為叢集建立共享記憶體」的敘述正確。

（3）判定：F

GPU 並非在所有工作負載下都比 CPU 快。GPU 適合：

  • 大量獨立且相似的資料平行運算；
  • 矩陣運算、影像處理、深度學習等高吞吐量工作。

CPU 則通常較適合：

  • 順序性高的程式；
  • 分支很多的控制流程；
  • 工作量小但要求低延遲的任務；
  • 作業系統與一般控制工作。
🔒

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

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

免費註冊

第 4 題20 分

Consider a computer with a 64-entry TLB in its main processor. The computer has a hard disk spinning at 5400 RPM and holding 40 sectors per track with a sector size of 512 bytes. In addition, the access latency time for the hard drive is 10 milliseconds, and the seek time is 30 milliseconds.

(1) [4%] Calculate TLB reach when the computer supports memory page sizes of 1 KB and 4 KB, respectively.
(2) [4%] Compute the data transfer rate of the hard disk in KB/s.
(3) [4%] Estimate the I/O times when page faults occur; give your I/O times in milliseconds for handling the page fault of a 1-KB page and a 4-KB page, respectively.
(4) [8%] We assume that the data transfer time of the hard disk is proportional to the page size. What are the I/O times to transfer the same amount of data (i.e., 4KB data) with 1-KB pages and 4-KB pages, respectively? In such a case, if we want to minimize the I/O time on the computer, which page size (1 KB or 4KB) is desired?

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

這一題的完整詳解

核心觀念

本題考查三個作業系統與計算機組織的重要觀念：

  1. TLB reach：TLB 能涵蓋的虛擬記憶體範圍。
    TLB reach=TLB entry 數×page size\text{TLB reach}=\text{TLB entry 數}\times\text{page size}

  2. 硬碟資料傳輸率：由每軌資料量與每秒旋轉圈數決定。
    Transfer rate=每軌資料量×每秒旋轉圈數\text{Transfer rate}=\text{每軌資料量}\times\text{每秒旋轉圈數}

  3. Page fault I/O 時間：包含尋道時間、存取延遲，以及實際資料傳輸時間。
    TI/O=Tseek+Tlatency+TtransferT_{\text{I/O}}=T_{\text{seek}}+T_{\text{latency}}+T_{\text{transfer}}

題目給定的 access latency time 視為每次硬碟 I/O 都需支付的存取延遲 1010 毫秒。

解題方法

（1）計算 TLB reach

TLB 有 6464 個 entries。

Page size = 1 KB

TLB reach=64×1 KB=64 KB\text{TLB reach}=64\times 1\text{ KB}=64\text{ KB}

Page size = 4 KB

TLB reach=64×4 KB=256 KB\text{TLB reach}=64\times 4\text{ KB}=256\text{ KB}

因此，page size 越大，在 TLB entries 數量固定時，TLB 能涵蓋的記憶體範圍越大。

（2）計算硬碟資料傳輸率

硬碟每軌有 4040 個 sectors，每個 sector 為 512512 bytes，因此每軌資料量為：

40×512=20,480 bytes40\times 512=20{,}480\text{ bytes}

因為：

1 KB=1024 bytes1\text{ KB}=1024\text{ bytes}

所以每軌資料量為：

20,4801024=20 KB\frac{20{,}480}{1024}=20\text{ KB}

硬碟轉速為 54005400 RPM：

540060=90 revolutions/s\frac{5400}{60}=90\text{ revolutions/s}

因此硬碟資料傳輸率為：

20 KB/revolution×90 revolutions/s=1800 KB/s20\text{ KB/revolution}\times 90\text{ revolutions/s} =1800\text{ KB/s}

（3）發生 Page fault 時的 I/O 時間

硬碟傳輸率為：

1800 KB/s1800\text{ KB/s}

傳輸 1 KB page

資料傳輸時間：

Ttransfer=1 KB1800 KB/s=11800 sT_{\text{transfer}}=\frac{1\text{ KB}}{1800\text{ KB/s}} =\frac{1}{1800}\text{ s}

換算成毫秒：

11800×1000≈0.556 ms\frac{1}{1800}\times 1000 \approx 0.556\text{ ms}

因此，1 KB page 的 Page fault I/O 時間為：

TI/O=30+10+0.556=40.556 msT_{\text{I/O}}=30+10+0.556 =40.556\text{ ms}

傳輸 4 KB page

資料傳輸時間：

🔒

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

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

免費註冊

第 5 題30 分

Considering the real-time systems, which are waiting for events in runtime to occur, when an event occurs, the system must act and respond to the event as fast as possible. On such systems, event latency is used to denote the amount of the elapsed time from the event occurring time to the time where it is serviced.

(1) [10%] What are the two types of latencies that affect the event latency of such systems?
(2) [5%] Which process scheduling scheme (i.e., preemption- or non-preemption-based scheme) is preferred to provide less latency?
(3) [10%] Suppose that the following processes arrive for execution upon at the arrival time. Each process will run the amount of time as listed below. Based on your answer given in (2), choose FCFS or RR (quantum = 20 milliseconds) to compute the average waiting time and the average turnaround time for the processes.

ProcessArrival TimeBurst Time
P1053
P2017
P3068
P4024

(4) [5%] If FCFS is used to schedule the processes given in (3) on one processor, how many possible different schedules are there?

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

這一題的完整詳解

參考書等級：大學三、四年級或研究所課程

(1) 事件延遲的兩種構成

  • 排隊延遲 (queueing latency)：事件發生後，因資源被佔用而必須等待的時間。
  • 服務延遲 (service latency)：事件被取出後，實際執行服務所需的時間。

(2) 偏好之排程機制

  • 搶占式 (preemptive) 排程 能在事件到達時即刻中斷當前工作，故較少延遲，為首選。

(3) 平均等候時間與平均周轉時間

排程方式平均等候時間 (ms)平均周轉時間 (ms)
FCFS0+53+70+1384=65.25\displaystyle\frac{0+53+70+138}{4}=65.2553+70+138+1624=105.75\displaystyle\frac{53+70+138+162}{4}=105.75
🔒

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

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

免費註冊

其他考古題

108 年成功大學的其他科目

計算機數學程式設計

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

115 年114 年113 年112 年109 年