113 年 國立中山大學電機工程學系碩士班己組《計算機結構》

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

第 1 題20 分

In hardware, SYS-1 system has a CPU with a base CPI of XX, where XX is larger than zero, assuming all references hit in the primary cache (L1) and a CPU clock rate of 2GHz. Assume that the main memory access time is 160 ns, including all the cache miss handling. Suppose the miss rate per instruction at L1 is 5%. Based on the construction of SYS-1 system, there are two systems shown as follows.

(i) SYS-2 system includes SYS-1 and an additional secondary cache (L2). The access time of L2 is 28 ns for either a hit or a miss. Suppose the miss rate per instruction at L2 is YY, where 0<Y<10 < Y < 1.
(ii) SYS-3 system includes SYS-2 and an additional tertiary cache (L3). The access time of L3 is 44 ns for either a hit or a miss. Suppose the miss rate per instruction at L3 is 0.1%.

We know that SYS-2 system is faster than SYS-1 system by 2 times. In addition, SYS-3 system is faster than SYS-2 system by 1.25 times. Please answer the following questions.

(a) As regards SYS-1 system, please calculate the memory-stall cycles per instruction.
(b) Please calculate XX.
(c) Please calculate YY.
(d) According to the result calculated in (b), the program has three different instruction categories, such as A, B, and C. We know that CPI for A, B, and C is 3, 5, and 6, respectively. The instruction count of A and B is 48 and 30, respectively. Please calculate the instruction count of C.

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

這一題的完整詳解

(a) 記憶體停頓週期／指令

主記憶存取延遲=160 ns,時脈周期=12 GHz=0.5 ns\text{主記憶存取延遲}=160\text{ ns},\qquad \text{時脈周期}= \frac{1}{2\text{ GHz}} =0.5\text{ ns}

Miss Penalty=1600.5=320 cycles\text{Miss Penalty}= \frac{160}{0.5}=320\text{ cycles}

L1 Miss Rate=0.05\text{L1 Miss Rate}=0.05

Stall CPI=0.05×320=16 cycles/instruction\boxed{\text{Stall CPI}=0.05 \times 320 = 16\text{ cycles/instruction}}

(b) 求基礎 CPI XX

SYS‑1 CPI：C ⁣1=X+16C_{\!1}=X+16

SYS‑2 停頓 CPI

L2 命中延遲 28 ns=5628\text{ ns}=56 cycles，
L2 未命中再至主記憶，總延遲 28+160=188 ns=37628+160=188\text{ ns}=376 cycles。

Stall2=(0.05−Y)×56+Y×376=2.8+320Y\text{Stall}_{2}= (0.05-Y)\times56 + Y\times376 = 2.8 + 320Y

C ⁣2=X+2.8+320YC_{\!2}=X+2.8+320Y

已知 SYS‑2 速度是 SYS‑1 的 2×2\times → CPI 減半：

X+2.8+320Y=X+162⇒X=10.4−640Y(1)X+2.8+320Y = \frac{X+16}{2}\qquad\Rightarrow\qquad X = 10.4-640Y \tag{1}

SYS‑3 停頓 CPI

L3 命中延遲 44 ns=8844\text{ ns}=88 cycles，
L3 未命中再至主記憶，總延遲 44+160=204 ns=40844+160=204\text{ ns}=408 cycles。

🔒

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

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

免費註冊

第 2 題10 分

A program, SVM, has the total execution time of 500 ns and can be well-divided into P1 - P4 parts. P1 - P3 can be modified to increase or decrease the individual execution time by the certain approaches. But P4 still keeps identical without any influence. The execution time of P1 - P4 is denoted as T1 - T4, respectively. Assume that T1 - T4 originally are 144 ns, 108 ns, 120 ns, and 128 ns, respectively. There are three different design scenarios as follows.

◆ Design scenario 1: If T1 and T2 are improved by X and Z times, respectively, T3 is increased to 1.34 times accordingly. The corresponding total execution time is decreased to 476 ns.
Design scenario 2: If T1 and T3 are improved by Y and Z times, respectively, T2 is increased to 1.5 times accordingly. The corresponding total execution time is decreased to 490 ns.
◆ Design scenario 3: If T2 and T3 are improved by Y and X times, respectively, T1 is increased to 1.375 times accordingly. The corresponding total execution time is increased to 512 ns.

Which one is the possible solution of (X, Y, Z)?
(single choice)
(A) (1.25, 1.5, 1.4)
(B) (1.25, 1.2, 1.75)
(C) (1.4, 1.2, 1.25)
(D) (1.25, 1.5, 1.6)
(E) (1.5, 1.2, 1.25)
(F) (1.4, 1.2, 1.5)
(G) (1.75, 1.4, 1.5)
(H) (1.25, 1.2, 1.25)
(I) (1.25, 1.5, 1.25)
(J) (1.4, 1.75, 1.5)
(K) (1.25, 1.2, 1.5)
(L) (1.4, 1.6, 1.5)

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

這一題的完整詳解
T1=144 ns,  T2=108 ns,  T3=120 ns,  T4=128 ns∑Ti=500 ns\begin{aligned} T_1&=144\ \text{ns},\; T_2=108\ \text{ns},\; T_3=120\ \text{ns},\; T_4=128\ \text{ns}\\ \sum T_i &=500\ \text{ns} \end{aligned}

設計情境方程式（改善＝時間除以因子，惡化＝時間乘以因子）

  1. 144X+108Z+1.34 ⁣× ⁣120+128=476\displaystyle \frac{144}{X}+\frac{108}{Z}+1.34\!\times\!120+128=476

    ⇒144X+108Z=187.2\Rightarrow \displaystyle \frac{144}{X}+\frac{108}{Z}=187.2  (①)

  2. 144Y+1.5 ⁣× ⁣108+120Z+128=490\displaystyle \frac{144}{Y}+1.5\!\times\!108+\frac{120}{Z}+128=490

    ⇒144Y+120Z=200\Rightarrow \displaystyle \frac{144}{Y}+\frac{120}{Z}=200  (②)

  3. 1.375 ⁣× ⁣144+108Y+120X+128=512\displaystyle 1.375\!\times\!144+\frac{108}{Y}+\frac{120}{X}+128=512

🔒

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

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

免費註冊

第 3 題25 分

Assume that X1 - X7 and Y1 - Y7 are well-represented as the 32-bit single-precision format in IEEE-754 standard as shown in TABLE I. We know that the relationship is calculated as follows, W1 = X1 × Y1, W2 = X2 × Y2, ......, W7 = X7 × Y7. Please answer the following questions.

(a) If 10n≤X5≤10n+110^n \le X_5 \le 10^{n+1}, where n∈Zn \in Z, please find out the value of nn.
(b) If −10m≤Y2≤−10m−1-10^m \le Y_2 \le -10^{m-1}, where m∈Zm \in Z, please find out the value of mm.
(c) Please sort these seven numbers (W1 - W7) in descending order.

TABLE I
Bit
31
X1 0 10000011011001100010000000000000
Y1 0 11000101011010011111000000000000
X2 0 00100111010111011001000000000000
Y2 1 10100010001001000110000000000000
X3 0 01101010000011001000000000000000
Y3 1 01011101010100111000000000000000
X4 1 10111001101100010010000000000000
Y4 0 00010010001111110101000000000000
X5 0 00111100010110001100000000000000
Y5 1 10001011000111000100000000000000
X6 1 10011001110111100011000000000000
Y6 1 00101100011111101100000000000000
X7 0 00111101101111110000000000000000
Y7 0 10001000001111010100000000000000
Bit
0
🖼️【此處有附圖，請對照原卷】

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

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

這一題的完整詳解

核心觀念

IEEE-754 單精度浮點數共 3232 位元，依序分成：

  • 符號位元 ss：11 位元。
  • 指數欄位 EE：88 位元，偏移量為 127127。
  • 小數欄位 FF：2323 位元。

本題各數皆為正規化數，因此其數值為

V=(−1)s(1+F223)2E−127.V=(-1)^s\left(1+\frac{F}{2^{23}}\right)2^{E-127}.

令有效數 M=1+F/223M=1+F/2^{23}、實際指數 e=E−127e=E-127，則兩數相乘為

XY=(−1)sX+sY(MXMY)2eX+eY.XY=(-1)^{s_X+s_Y}(M_XM_Y)2^{e_X+e_Y}.

排序時，先分正負，再比較指數與有效數；負數的絕對值越大，數值越小。

解題方法

原卷 TABLE I 的每列由左至右是位元 3131 到位元 00，四位一組的格線只是方便閱讀，並非欄位分界。尤其 X6X_6 的原卷位元為 1100 1100 1110 1111 0001 1000 0000 0000，應切成符號 11、指數 1001100110011001，以及其餘 2323 位小數。

（a）求 nn

由原卷讀得

X5=0⏟s  00111100⏟E  01011000110000000000000⏟F.X_5=\underbrace{0}_{s}\; \underbrace{00111100}_{E}\; \underbrace{01011000110000000000000}_{F}.

因此

E=60,e=60−127=−67,E=60,\qquad e=60-127=-67, M=1+2−2+2−4+2−5+2−9+2−10=13791024.M=1+2^{-2}+2^{-4}+2^{-5}+2^{-9}+2^{-10} =\frac{1379}{1024}.

所以

X5=137910242−67≈9.12546×10−21.X_5=\frac{1379}{1024}2^{-67} \approx 9.12546\times10^{-21}.

代入題目範圍可得

10−21≤X5≤10−20,10^{-21}\le X_5\le10^{-20},

故 n=−21n=-21。

（b）求 mm

由原卷讀得

Y2=1⏟s  01000010⏟E  00100100011000000000000⏟F.Y_2=\underbrace{1}_{s}\; \underbrace{01000010}_{E}\; \underbrace{00100100011000000000000}_{F}.

因此

E=66,e=66−127=−61,E=66,\qquad e=66-127=-61, M=1+2−3+2−6+2−10+2−11=23392048.M=1+2^{-3}+2^{-6}+2^{-10}+2^{-11} =\frac{2339}{2048}.

所以

Y2=−233920482−61≈−4.95302×10−19.Y_2=-\frac{2339}{2048}2^{-61} \approx-4.95302\times10^{-19}.

代入題目範圍：

−10−18≤Y2≤−10−19.-10^{-18}\le Y_2\le-10^{-19}.

與 −10m≤Y2≤−10m−1-10^m\le Y_2\le-10^{m-1} 對照，得到 m=−18m=-18。

（c）將 W1W_1 至 W7W_7 由大到小排序

逐列解讀符號及指數，再將有效數相乘，得到下表。其中 eX,eYe_X,e_Y 均已扣除偏移量 127127。

🔒

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

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

免費註冊

第 4 題20 分

The following mathematical equation shows the relationship among different elements in the array, A[ ]. After executing the MIPS codes listed in Figure 1, the value of A[i+S] can be computed based on A[i] - A[i+3], where i and S are two positive integers. C0 - C3 denote four integer coefficients. We know that the base address of A[ ] is stored in $s0. Please answer the following questions.

(a) Please calculate C0, C1, C2, and C3.
(b) Please calculate i and S.
(c) Please calculate the value of A[i+S] while (A[i], A[i+1], A[i+2], A[i+3]) = (-8, 10, -11, 7).
(d) In hardware implementation, we can utilize a 5-stage pipelined MIPS CPU to execute this program. If considering the forwarding (bypass) technique to fix or relax the possible data hazard, what is the minimum number of total clock cycles to complete this program?

🖼️【此處有附圖，請對照原卷】

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

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

這一題的完整詳解

核心觀念

這題考兩個重點：

  1. 由 MIPS 暫存器運算反推陣列係數：lw 從陣列載入元素，後續的加減與位移可逐步化簡成 A[i]A[i] 到 A[i+3]A[i+3] 的線性組合。
  2. 五階段管線的資料冒險：有 forwarding 時，多數相鄰指令相依可直接轉送結果；但 lw 的載入資料要到較後階段才可用，緊接著使用載入值時仍須停等一個 cycle。

題目中的陣列元素是 32-bit 整數，因此每個元素占 4 bytes。sll $t2, $t2, 3 等同乘以 23=82^3=8。

解題方法

依原卷 Figure 1，指令可整理如下：

lw   $a0, 128($s0)
lw   $a1, 132($s0)
sub  $t0, $a0, $a1
lw   $a2, 136($s0)
add  $t1, $a2, $a2
sub  $t1, $t1, $a1
add  $t2, $t1, $t1
add  $t2, $t2, $t0
sll  $t2, $t2, 3
sub  $t2, $t2, $a0
lw   $a3, 140($s0)
sll  $t0, $a3, 2
sub  $t0, $t0, $a3
add  $t2, $t2, $t0
sub  $t1, $t2, $t1
addi $t2, $t1, -5
sw   $t2, 264($s0)

(a) 求 C0,C1,C2,C3C_0,C_1,C_2,C_3

設四個載入值依序為 A[i],A[i+1],A[i+2],A[i+3]A[i],A[i+1],A[i+2],A[i+3]。

前三個暫存器中間值為：

t0=A[i]−A[i+1]t_0=A[i]-A[i+1] t1=2A[i+2]−A[i+1]t_1=2A[i+2]-A[i+1] t2=2t1+t0=A[i]−3A[i+1]+4A[i+2]t_2=2t_1+t_0 =A[i]-3A[i+1]+4A[i+2]

接著左移 3 位並減去 A[i]A[i]：

8t2−A[i]=7A[i]−24A[i+1]+32A[i+2]8t_2-A[i] =7A[i]-24A[i+1]+32A[i+2]

另一條運算路徑為：

4A[i+3]−A[i+3]=3A[i+3]4A[i+3]-A[i+3]=3A[i+3]

將兩條路徑相加，再減去 $t_1

🔒

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

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

免費註冊

其他考古題

中山大學《計算機結構》其他年度

112 年111 年109 年108 年

其他學校的電機系考古題

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