113 年 國立中正大學電機工程學系碩士班計算機工程組《計算機組織》

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

第 1 題20 分

  1. (20%) Assume compiler A runs a program with a dynamic instruction count of 1.0×1091.0 \times 10^9 and spends 1.1 s, and compiler B runs the same program with a dynamic instruction count of 1.3×1091.3 \times 10^9 and computing time of 1.2 s.
    (a). (10%) What is the average CPI for each compiler with a clock cycle time of 0.5 ns.
    (b). (10%) A new compiler is that uses only 5.0×1085.0 \times 10^8 instructions and has an average CPI of 1.2. What is the speedup of this new compiler comparing to compilers A and B?

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

這一題的完整詳解

核心觀念

本題考查 CPU 執行時間、動態指令數、平均 CPI 與時脈週期時間的關係：

CPU Time=Instruction Count×CPI×Clock Cycle Time\text{CPU Time} = \text{Instruction Count} \times \text{CPI} \times \text{Clock Cycle Time}

因此：

CPI=CPU TimeInstruction Count×Clock Cycle Time\text{CPI} = \frac{\text{CPU Time}} {\text{Instruction Count}\times\text{Clock Cycle Time}}

加速比定義為：

Speedup=原執行時間新執行時間\text{Speedup} = \frac{\text{原執行時間}} {\text{新執行時間}}

時脈週期時間為：

0.5 ns=0.5×10−9 s0.5\text{ ns}=0.5\times10^{-9}\text{ s}

解題方法

先利用已知的執行時間、動態指令數與時脈週期時間求出 A、B 的平均 CPI；再利用新編譯器的指令數與 CPI 求出新執行時間，最後分別與 A、B 的執行時間相比。

(a) 求各編譯器的平均 CPI

編譯器 A：

CPIA=1.1(1.0×109)(0.5×10−9)=1.10.5=2.2\begin{aligned} \text{CPI}_A &= \frac{1.1} {(1.0\times10^9)(0.5\times10^{-9})}\\ &= \frac{1.1}{0.5}\\ &=2.2 \end{aligned}

編譯器 B：

CPIB=1.2(1.3×109)(0.5×10−9)=1.20.65≈1.846\begin{aligned} \text{CPI}_B &= \frac{1.2} {(1.3\times10^9)(0.5\times10^{-9})}\\ &= \frac{1.2}{0.65}\\ &\approx1.846 \end{aligned}

所以：

CPIA=2.2\boxed{\text{CPI}_A=2.2}
🔒

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

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

免費註冊

第 2 題30 分

  1. (30%) As in the table, an MIPS CPU is designed with instructions and latencies. Assume the multiplexors, control unit, PC accesses, and sign extension unit have no delay.
    (a). (10%) What is the critical path if the CPU is working as a single-cycle processor? Why?
    (b). (10%) What is the minimum clock speed of the single-cycle processor?
    (c). (10%) What is the minimum clock speed if the CPU is working as a multi-cycle processor?
InstructionsInstruction fetchRegister readControlMemory accessRegister writeALU
sub300ps100 ps200ps100 ps100ps
sw300ps100 ps200ps300ps100ps
add300ps100 ps200ps100 ps100ps
beq300ps100 ps200ps250ps

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

這一題的完整詳解

核心觀念

單週期處理器中，每一條指令都必須在同一個 clock cycle 內完成，因此：

Tsingle≥最長指令資料路徑延遲T_{\text{single}} \geq \text{最長指令資料路徑延遲}

多週期處理器會將指令拆成多個階段，每一個階段使用一個 clock cycle，因此：

Tmulti≥所有階段中最大的單一階段延遲T_{\text{multi}} \geq \text{所有階段中最大的單一階段延遲}

時脈頻率與週期的關係為：

f=1Tf=\frac{1}{T}

題目同時列出 Control = 200 ps，又明定 control unit 沒有延遲，兩者互相矛盾。本詳解依題幹的明文假設，將 control unit 的有效延遲視為 00，因此不將表格中的 200 ps200\text{ ps} 加入路徑。

解題方法

在單週期處理器中，只需將同一條指令實際依序經過的元件延遲相加。平行執行的路徑不相加，而是取較慢者。

指令實際資料路徑總延遲
addInstruction fetch → Register read → ALU → Register write300+100+100+100=600 ps300+100+100+100=600\text{ ps}
subInstruction fetch → Register read → ALU → Register write300+100+100+100=600 ps300+100+100+100=600\text{ ps}
swInstruction fetch → Register read → ALU → Memory access300+100+100+300=800 ps300+100+100+300=800\text{ ps}
beqInstruction fetch → Register read → ALU（比較）300+100+250=650 ps300+100+250=650\text{ ps}

（a）單週期處理器的 critical path

sw 指令的路徑為：

Instruction fetch→Register read→ALU→Memory access\text{Instruction fetch} \rightarrow \text{Register read} \rightarrow \text{ALU} \rightarrow \text{Memory access}

其延遲為：

Tsw=300+100+100+300=800 psT_{sw}=300+100+100+300=800\text{ ps}

比較所有指令：

max⁡(600,600,800,650)=800 ps\max(600,600,800,650)=800\text{ ps}

因此，critical path 是 sw 指令的資料寫入路徑。原因是 sw 必須先讀取暫存器，再由 ALU 計算記憶體位址，最後完成資料記憶體存取；這條路徑比其他指令更長。

（b）單週期處理器的最低 clock speed

🔒

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

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

免費註冊

第 3 題20 分

  1. (20%) Consider a segment MIPS code as below.
    (a). (10%) Find the hazards in the preceding code segment.
    (b). (10%) Reorder the instructions to avoid any pipeline stalls.
lw $s1, 0($t0)
lw $s2, 4($t0)
add $a3, $s1, $s2
sw $a3, 12($t0)
lw $s5, 8($t0)
add $a5, $s1, $s5
sw $a5, 16($t0)

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

這一題的完整詳解

(a) 資料危險 (RAW)

  1. s1→adds1 → add a3 : s1由‘lws1 由 `lw s1,…產生，緊接的add a3,a3,s1,$s2` 需使用，形成 load‑use hazard。
  2. s2→adds2 → add a3 : 同上，lw $s2,… → add $a3,… 產生 load‑use hazard。
  3. s1→adds1 → add a5 : lw $s1,… → add $a5,$s1,$s5 形成 load‑use hazard（在 add $a5 前未插入其他指令）。
  4. s5→adds5 → add a5 : lw $s5,… → add $a5,… 形成 load‑use hazard。

sw $a3,… 與 sw $a5,… 皆只讀取前一條 add 的結果，可用 forwarding 把 ALU 結果直接送至 MEM 階段，不需額外停頓。

(b) 重新排程避免停頓

🔒

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

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

免費註冊

第 4 題30 分

  1. (30%) Assume an adder-subtractor CPU circuit is composed of full-adder (FA) as in the figure. Please find the value for:
    (a). (10%) Find value at (A1,b2,C1,V,M)(A_1, b_2, C_1, V, M) for A-B = 0-0.
    (b). (10%) Find value at (b0,C1,A2,S2,M)(b_0, C_1, A_2, S_2, M) for A-B = -1-(-2).
    (c). (10%) Find value at (A1,B2,C3,S1,M)(A_1, B_2, C_3, S_1, M) for A-B = 0-2.

🖼️【此處有附圖，請對照原卷】
Figure: a 4-bit adder-subtractor built from four full adders (FA). Each BiB_i passes through an XOR gate with the control line MM to give bib_i; the FA of bit ii takes AiA_i, bib_i and carry-in CiC_i, and outputs SiS_i and carry-out Ci+1C_{i+1} (i=0,1,2,3i = 0, 1, 2, 3). MM is also connected to C0C_0; the output CC is C4C_4, and VV is the XOR of C4C_4 and C3C_3.

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

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

這一題的完整詳解

核心觀念

此電路以控制訊號 MM 選擇加法或減法：

  • M=0M=0 時，bi=Bib_i=B_i 且 C0=0C_0=0，執行 A+BA+B。
  • M=1M=1 時，bi=Bi⊕1=Bi‾b_i=B_i\oplus 1=\overline{B_i} 且 C0=1C_0=1，執行二補數減法：
    A−B=A+B‾+1A-B=A+\overline{B}+1

每一位全加器的輸入為 Ai,bi,CiA_i,b_i,C_i，輸出為 Si,Ci+1S_i,C_{i+1}。有號溢位旗標為：
V=C4⊕C3V=C_4\oplus C_3

題目中的負數以 4 位元二補數表示：−1=11112-1=1111_2、−2=11102-2=1110_2。

解題方法

三小題都是減法，因此皆取 M=1M=1，將 BB 逐位反相，並令 C0=1C_0=1。由最低位 i=0i=0 起逐位計算進位與和位。

(a) A−B=0−0A-B=0-0

A=00002A=0000_2、B=00002B=0000_2，所以 b=B‾=11112b=\overline{B}=1111_2，且 C0=1C_0=1。

逐位計算可得 C1=C2=C3=C4=1C_1=C_2=C_3=C_4=1，因此 S=00002S=0000_2。所需值為：

  • A1=0A_1=0
  • b2=1b_2=1
  • C1=1C_1=1
  • V=C4⊕C3=1⊕1=0V=C_4\oplus C_3=1\oplus1=0
  • M=1M=1

因此 (A1,b2,C1,V,M)=(0,1,1,0,1)(A_1,b_2,C_1,V,M)=(0,1,1,0,1)。

(b) A−B=(−1)−(−2)A-B=(-1)-(-2)

A=11112A=1111_2、B=11102B=1110_2，所以 b=B‾=00012b=\overline{B}=0001_2，且 C0=1C_0=1。

🔒

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

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

免費註冊

其他考古題

其他學校的電機系考古題

臺灣大學50臺灣聯合大學系統110成功大學154中央大學13中山大學96暨南國際大學8臺灣科技大學4聯合大學4嘉義大學2