CCIT4026 Introduction to Computer Organization

HKU SPACE Community College — AY2526

使用說明

本文件對照原始解答 PDF（Assignment_3_wf_ay2526 solution.pdf）逐題重寫，補充每一個推導步驟，並在原 PDF 出現誤植處明確標註並給出依題目原始條件的正確答案：

  1. Q1(d)(ii) 標題：原 PDF 寫成 -998.3125，但題目給的是 -998.125，且解答內文展開為 1111100110.001₂（對應 0.125），故 hex 結果 0xC4798800 對應的是 -998.125。本文以題目為準。
  2. Q2(a) 時鐘頻率：題目寫 P1 = 1 GHz、P2 = 2 GHz，但原 PDF 解答內文卻代入 2e9 與 3e9（對應 2 GHz 與 3 GHz）。本文依題目給定的 1 GHz / 2 GHz 重新計算，並同時附上 PDF 內所用值的計算對照。

目錄

Q1 — 位元模式的多重意義

題目重述

在 Von Neumann 架構中，位元本身沒有固有意義，其代表的數值或指令完全取決於使用方式。考慮以下兩個以十六進位表示的 32-bit 位元樣式：

  • i. 0x22100004
  • ii. 0xAD110000

請依不同詮釋角度回答：

  • (a) 若視為 (i) 二補數整數、(ii) 無號整數，分別代表的十進位值為何？
  • (b) 若放入 Instruction Register 並執行，會是什麼 MIPS 指令？
  • (c) 若視為 IEEE 754 單精度浮點數，代表的十進位值為何？
  • (d) 將下列兩個十進位數依 IEEE 754 單精度格式寫出二進位與十六進位：
  • i. 2821.25
  • ii. -998.125

起手式：先把兩個 hex 轉為 32 位二進位

0x22100004 = 0010 0010 0001 0000  0000 0000 0000 0100
0xAD110000 = 1010 1101 0001 0001  0000 0000 0000 0000

Q1(a) — 2's complement vs Unsigned 整數詮釋

(i) 0x22100004

最高位（MSB）為 0，因此正號。在 32-bit 範圍內，正數的二補數表示與無號表示完全相同（題目強調「不是要求轉換」，是同一個位元樣式被解讀兩次）。

直接展開：

0x22100004
= 2 × 16⁷ + 2 × 16⁶ + 1 × 16⁵ + 0 × 16⁴
+ 0 × 16³ + 0 × 16² + 0 × 16¹ + 4 × 16⁰
= 2 × 268435456 + 2 × 16777216 + 1 × 1048576 + 4
= 536870912 + 33554432 + 1048576 + 4
= 571,473,924
詮釋方式 結果
二補數整數 +571,473,924
無號整數 +571,473,924

(ii) 0xAD110000

MSB 為 1，因此在二補數下為負數；在無號下則是一個非常大的正數。

Step 1：先計算無號值

0xAD110000 = 0xAD × 16⁶ + 0x11 × 16⁴ + 0x00 × 16² + 0x00
           = 173 × 16⁷ ...

更直接地用 4 位元組分塊：

0xAD = 173
0x11 = 17
0x00 = 0
0x00 = 0

無號值 = 173 × 2²⁴ + 17 × 2¹⁶ + 0 × 2⁸ + 0
       = 173 × 16777216 + 17 × 65536
       = 2902458368 + 1114112
       = 2,903,572,480

Step 2：計算二補數值

由於 MSB = 1，須轉為二補數負值：

2's complement value = 無號值 - 2³²
                     = 2,903,572,480 - 4,294,967,296
                     = -1,391,394,816
詮釋方式 結果
二補數整數 -1,391,394,816
無號整數 +2,903,572,480

Q1(b) — 解讀為 MIPS 指令

前置知識：MIPS 主要格式分塊

格式 欄位（由 MSB 至 LSB）
R-type opcode(6) | rs(5) | rt(5) | rd(5) | shamt(5) | funct(6)
I-type opcode(6) | rs(5) | rt(5) | immediate(16)
J-type opcode(6) | address(26)

常見 opcode 速查：

Opcode 二進位 十進位 助憶
000000 0 R-type（看 funct）
001000 8 addi
001001 9 addiu
100011 35 lw
101011 43 sw
000100 4 beq
000010 2 j

(i) 0x22100004

依 6/5/5/16 切欄位：

0010 0010 0001 0000 0000 0000 0000 0100

切割：
opcode    rs       rt        immediate
001000    10000    10000     0000 0000 0000 0100
   8       16       16              4
欄位 值 對應
opcode 001000 = 8 addi（I-type）
rs 10000 = 16 $s0
rt 10000 = 16 $s0
immediate 0000_0000_0000_0100 = 4 立即值 4

I-type addi 的語法為 addi rt, rs, imm：

addi $s0, $s0, 4

語意：把 $s0 加 4 後寫回 $s0（典型的指標步進或計數器累加）。

(ii) 0xAD110000

依 6/5/5/16 切欄位：

1010 1101 0001 0001 0000 0000 0000 0000

切割：
opcode    rs       rt        offset
101011    01000    10001     0000 0000 0000 0000
  43       8        17               0
欄位 值 對應
opcode 101011 = 43 sw（I-type）
rs（base） 01000 = 8 $t0
rt（source） 10001 = 17 $s1
offset 全 0 0

sw 的語法為 sw rt, offset(rs)：

sw $s1, 0($t0)

語意：把 $s1 的內容存到記憶體位址 ($t0 + 0)。

Q1(c) — 解讀為 IEEE 754 浮點數

IEEE 754 單精度格式

[ S | E (8 bits) | M (23 bits) ]
數值 = (-1)^S × (1.M)₂ × 2^(E - 127)

(i) 0x22100004

切欄位：

0010 0010 0001 0000 0000 0000 0000 0100

S | E         | M
0 | 01000100  | 00100000000000000000100
欄位 值 解析
S 0 正數
Biased E 01000100₂ = 68 實際指數 = 68 - 127 = -59
Mantissa 00100000000000000000100 隱藏 1 後 = 1.00100000000000000000100

Significand 計算： 把尾數的「1.xxx」展開為 1 加上各個 1 位元的權重：

1.M 中 1 出現在小數第 3 位 (= 2⁻³) 與小數第 21 位 (= 2⁻²¹)

Significand = 1 + 2⁻³ + 2⁻²¹
            = 1 + 0.125 + 0.000000476837...
            = 1.125000477 (取 9 位有效數字)

最終數值：

+ 1.125000477 × 2⁻⁵⁹

2⁻⁵⁹ ≈ 1.7347234759768 × 10⁻¹⁸

值 ≈ 1.125000477 × 1.7347234759768 × 10⁻¹⁸
   ≈ 1.95156473765 × 10⁻¹⁸

答案： +1.125000477 × 2⁻⁵⁹ ≈ +1.95156473765 × 10⁻¹⁸

(ii) 0xAD110000

切欄位：

1010 1101 0001 0001 0000 0000 0000 0000

S | E         | M
1 | 01011010  | 00100010000000000000000
欄位 值 解析
S 1 負數
Biased E 01011010₂ = 90（也可寫 0x5A） 實際指數 = 90 - 127 = -37
Mantissa 00100010000000000000000 隱藏 1 後 = 1.00100010000000000000000

Significand 計算： 1 出現在小數第 3 位與第 7 位：

Significand = 1 + 2⁻³ + 2⁻⁷
            = 1 + 0.125 + 0.0078125
            = 1.1328125

最終數值：

- 1.1328125 × 2⁻³⁷

2⁻³⁷ ≈ 7.27595761 × 10⁻¹²

值 ≈ -1.1328125 × 7.27595761 × 10⁻¹²
   ≈ -8.24229573482 × 10⁻¹²

答案： -1.1328125 × 2⁻³⁷ ≈ -8.24229573482 × 10⁻¹²

Q1(d) — 將十進位轉為 IEEE 754 單精度

(i) 將 2821.25 轉為 IEEE 754 單精度

Step 1：判斷符號

2821.25 > 0 → S = 0

Step 2：將絕對值轉為二進位

整數部分 2821：

2821 = 2048 + 512 + 256 + 4 + 1
     = 2¹¹ + 2⁹ + 2⁸ + 2² + 2⁰
     = 1011 0000 0101₂

驗算：
  2048 + 512 + 256 + 4 + 1
= 2048 + 768 + 5
= 2821 ✓

或用「連除 2」法亦可：

2821 ÷ 2 = 1410 ... 1
1410 ÷ 2 =  705 ... 0
 705 ÷ 2 =  352 ... 1
 352 ÷ 2 =  176 ... 0
 176 ÷ 2 =   88 ... 0
  88 ÷ 2 =   44 ... 0
  44 ÷ 2 =   22 ... 0
  22 ÷ 2 =   11 ... 0
  11 ÷ 2 =    5 ... 1
   5 ÷ 2 =    2 ... 1
   2 ÷ 2 =    1 ... 0
   1 ÷ 2 =    0 ... 1
→ 由下往上讀: 1011 0000 0101₂ ✓

小數部分 0.25：

0.25 × 2 = 0.5 → 0
0.5  × 2 = 1.0 → 1
→ 0.25₁₀ = 0.01₂

合併：

2821.25₁₀ = 1011 0000 0101.01₂

Step 3：正規化

把小數點移動到第一個 1 之後（共向左移 11 位）：

1011 0000 0101.01₂ = 1.011 0000 0101 01 × 2¹¹

Step 4：計算 Biased Exponent

Biased E = 11 + 127 = 138
138 = 128 + 8 + 2 = 2⁷ + 2³ + 2¹
138 = 1000 1010₂

Step 5：寫出 23 位 Mantissa

從正規化後 1.M 取出 M 部分，補 0 至 23 位：

M_raw = 011 0000 0101 01 (13 bits)
M     = 011 0000 0101 0100 0000 0000 (23 bits, 補 10 個 0)
      = 01100000101010000000000

Step 6：組合最終 32 位

S | E         | M
0 | 1000 1010 | 0110 0000 1010 1000 0000 000

連寫：0_1000_1010_0110_0000_1010_1000_0000_000
     = 0100_0101_0011_0000_0101_0100_0000_0000

切 4 位 → 十六進位：
  0100 0101 0011 0000 0101 0100 0000 0000
   4    5    3    0    5    4    0    0

答案：

  • 二進位：0 10001010 01100000101010000000000
  • 十六進位：0x45305400

驗算： 1.011 0000 0101 01 × 2¹¹

1.0110000010101 × 2048
≈ (1 + 0.25 + 0.125 + 2⁻⁹ + 2⁻¹¹ + 2⁻¹³) × 2048
= (1 + 0.25 + 0.125 + 0.001953125 + 0.00048828125 + 0.0001220703125) × 2048
= 1.376953125 × 2048
= 2821.25 ✓ (有限位剛好可精確表示)

(ii) 將 -998.125 轉為 IEEE 754 單精度

Step 1：符號

-998.125 < 0 → S = 1

Step 2：絕對值轉二進位

整數部分 998：

998 = 512 + 256 + 128 + 64 + 32 + 4 + 2
    = 2⁹ + 2⁸ + 2⁷ + 2⁶ + 2⁵ + 2² + 2¹
    = 1111 1001 10₂  (10 bits)

驗算：512+256+128+64+32 = 992；992+4+2 = 998 ✓

連除驗證：

998 ÷ 2 = 499 ... 0
499 ÷ 2 = 249 ... 1
249 ÷ 2 = 124 ... 1
124 ÷ 2 =  62 ... 0
 62 ÷ 2 =  31 ... 0
 31 ÷ 2 =  15 ... 1
 15 ÷ 2 =   7 ... 1
  7 ÷ 2 =   3 ... 1
  3 ÷ 2 =   1 ... 1
  1 ÷ 2 =   0 ... 1
→ 1111100110₂ ✓

小數部分 0.125：

0.125 × 2 = 0.25 → 0
0.25  × 2 = 0.5  → 0
0.5   × 2 = 1.0  → 1
→ 0.125₁₀ = 0.001₂

合併：

998.125₁₀ = 1111100110.001₂

Step 3：正規化

1111100110.001₂ = 1.111100110001 × 2⁹

Step 4：Biased Exponent

Biased E = 9 + 127 = 136 = 128 + 8 = 1000 1000₂

Step 5：23 位 Mantissa

M_raw = 111100110001 (12 bits)
M     = 1111 0011 0001 0000 0000 000 (23 bits, 補 11 個 0)
      = 11110011000100000000000

Step 6：組合最終 32 位

S | E         | M
1 | 1000 1000 | 1111 0011 0001 0000 0000 000

連寫：1_1000_1000_1111_0011_0001_0000_0000_000
     = 1100_0100_0111_1001_1000_1000_0000_0000

切 4 位 → 十六進位：
  1100 0100 0111 1001 1000 1000 0000 0000
   C    4    7    9    8    8    0    0

答案：

  • 二進位：1 10001000 11110011000100000000000
  • 十六進位：0xC4798800

⚠️ 原 PDF 標註說明 原 PDF 在 (ii) 標題寫 -998.3125，但同段內文的二進位展開 1111100110.001₂ 對應的是 0.125 而非 0.3125。題目給的是 -998.125，故本答案以題目為準（0xC4798800）。

若真的要計算 -998.3125：

text 0.3125 = 0.0101₂ 998.3125 = 1111100110.0101₂ = 1.1111001100101 × 2⁹ M = 11110011001010000000000 Hex = 0xC4799400

兩者 hex 不同，應依題目實際值（-998.125）作答。

Q2 — 兩種實作的效能比較

題目重述

同一指令集有兩種實作 P1 與 P2，指令分為 5 類（A~E）。 P1 時鐘頻率 = 1 GHz；P2 時鐘頻率 = 2 GHz。各類別 CPI 如下：

類別 CPI on P1 CPI on P2
A 1 2
B 2 3
C 3 3
D 3 4
E 4 4

(a) Peak Performance（執行最快指令序列的速率）以「每秒指令數」表示，P1 與 P2 各為多少？

(b) 若程式中除了 B 類出現次數為其他類別的 3 倍外，其餘各類等量出現，P2 比 P1 快多少倍？

Q2(a) — Peak Performance

⚠️ 原 PDF 解答誤植 原 PDF 解答內文使用 2e9 cycles/s（P1）與 3e9 cycles/s（P2），對應 2 GHz 與 3 GHz；但題目明定 1 GHz / 2 GHz。本文依題目原始條件重算，並在末尾附上原 PDF 數值的對照。

Peak Performance 公式：

Peak IPS = Clock Rate / (CPI_min)

「最快」指令序列即 CPI 最小的指令類別連續執行。

P1：

P1 上 CPI 最小 = 1（A 類）。

Peak_P1 = 1 × 10⁹ cycles/s ÷ 1 cycle/instr
        = 1 × 10⁹ instructions/s
        = 1000 MIPS

P2：

P2 上 CPI 最小 = 2（A 類；B/C/D/E 都 ≥ 3）。

Peak_P2 = 2 × 10⁹ cycles/s ÷ 2 cycles/instr
        = 1 × 10⁹ instructions/s
        = 1000 MIPS

答案（依題目 1 GHz / 2 GHz）：

機器 Peak Performance
P1 1000 MIPS
P2 1000 MIPS

對照（原 PDF 用 2 GHz / 3 GHz）：

Peak_P1 = 2e9 / 1 = 2000 MIPS
Peak_P2 = 3e9 / 2 = 1500 MIPS

Q2(b) — 加權 CPI 與相對速度

Step 1：計算各機器的平均 CPI

設 A、C、D、E 各佔 1 份，B 佔 3 份，總共 7 份：

P1 平均 CPI = (1×1 + 2×3 + 3×1 + 3×1 + 4×1) / 7
            = (1 + 6 + 3 + 3 + 4) / 7
            = 17/7
            ≈ 2.4286 cycles/instr

P2 平均 CPI = (2×1 + 3×3 + 3×1 + 4×1 + 4×1) / 7
            = (2 + 9 + 3 + 4 + 4) / 7
            = 22/7
            ≈ 3.1429 cycles/instr

Step 2：計算各機器的執行速率（IPS）

IPS_P1 = Clock_P1 / Avg_CPI_P1 = 1×10⁹ ÷ (17/7) = 7×10⁹ / 17
IPS_P2 = Clock_P2 / Avg_CPI_P2 = 2×10⁹ ÷ (22/7) = 14×10⁹ / 22 = 7×10⁹ / 11

Step 3：比較

Speedup = IPS_P2 / IPS_P1
        = (7×10⁹ / 11) ÷ (7×10⁹ / 17)
        = 17 / 11
        ≈ 1.5455

答案（依題目 1 GHz / 2 GHz）：

P2 約為 P1 的 17/11 ≈ 1.545 倍。

對照（原 PDF 用 2 GHz / 3 GHz 算出）：

Speedup = (3e9 / (22/7)) ÷ (2e9 / (17/7))
        = (3 × 7 × 17) / (2 × 22 × 7)
        = 51 / 44
        ≈ 1.159

雖然 PDF 答案 51/44 ≈ 1.159 與其使用的 2 GHz / 3 GHz 一致，但與題目給定的 1 GHz / 2 GHz 不符。建議以本文 17/11 ≈ 1.545 為正確答案。

Q3 — Amdahl's Law 加速分析

題目重述

一個 benchmark 程式在某機器上跑 80 秒，其中浮點運算佔了 70% 的時間。

(a) 若硬體團隊將浮點運算加速 4 倍，整體加速比為何？

(b) 若硬體只能加速 2.4 倍，軟體團隊要把浮點運算的時間佔比調整到多少，才能達成 (a) 中的整體加速比？

Amdahl's Law 提示

T_new = (T_old × f_part) / k + T_old × (1 - f_part)

Speedup = T_old / T_new = 1 / ( f_part/k + (1 - f_part) )

其中：
  f_part = 被加速部分原佔的時間比例
  k      = 該部分的加速倍數

Q3(a) — 硬體加速 4 倍時的整體加速比

已知：

  • T_old = 80 秒
  • f_part = 0.7（浮點佔比）
  • k = 4

Step 1：計算新時間

T_new = (0.7 × 80) / 4 + (1 - 0.7) × 80
      = 56 / 4 + 0.3 × 80
      = 14 + 24
      = 38 秒

Step 2：計算加速比

n = T_old / T_new = 80 / 38 ≈ 2.105

亦可直接從公式推：

1 / n = 0.7/4 + 0.3 = 0.175 + 0.3 = 0.475
n = 1 / 0.475 ≈ 2.105

答案：整體加速比 n ≈ 2.105（即新時間約 38 秒）

Q3(b) — 反推所需的浮點時間佔比

已知：

  • T_old = 80 秒
  • 目標仍為 (a) 中的 n = 2.105，即新時間需仍 = 80 × 0.475 = 38 秒
  • k = 2.4

Step 1：列方程式

設 x = 浮點部分原佔的時間（秒）（不是比例）；非浮點部分為 (80 - x) 秒。

T_new = x / 2.4 + (80 - x) = 38

Step 2：求解 x

x / 2.4 + 80 - x = 38
x / 2.4 - x      = 38 - 80
x (1/2.4 - 1)    = -42
x × (1 - 2.4)/2.4 = -42
x × (-1.4 / 2.4)  = -42
x = 42 × 2.4 / 1.4
x = 100.8 / 1.4
x = 72 秒

Step 3：換算為佔比

新的浮點時間佔比 = 72 / 80 = 0.90 = 90%

答案：浮點運算的時間佔比需提高到 90%。

Step 4：驗算

T_new = 72 / 2.4 + (80 - 72)
      = 30 + 8
      = 38 秒 ✓

n = 80 / 38 ≈ 2.105 ✓ (與 (a) 一致)

全題答案總覽

Q1

子題 (i) 0x22100004 (ii) 0xAD110000
(a) 2's complement +571,473,924 -1,391,394,816
(a) Unsigned +571,473,924 +2,903,572,480
(b) MIPS addi $s0, $s0, 4 sw $s1, 0($t0)
(c) IEEE 754 +1.125000477 × 2⁻⁵⁹ ≈ +1.95 × 10⁻¹⁸ -1.1328125 × 2⁻³⁷ ≈ -8.24 × 10⁻¹²
子題 (i) 2821.25 (ii) -998.125
(d) Binary 0 10001010 01100000101010000000000 1 10001000 11110011000100000000000
(d) Hex 0x45305400 0xC4798800

Q2（依題目 1 GHz / 2 GHz）

子題 結果
(a) Peak P1 1000 MIPS
(a) Peak P2 1000 MIPS
(b) Speedup（P2 vs P1） 17/11 ≈ 1.545×

Q3

子題 結果
(a) 整體加速比 n ≈ 2.105
(b) 所需浮點佔比 90%

延伸閱讀

  • MIPS 指令編碼 / 反組譯：可參考工作區檔案 MIPS_Assembly_Instruction_Set.md、MIPS_Assembly_to_Machine_Code_Guide.md
  • IEEE 754 完整教材：IEEE_754_Floating_Point.md（含浮點加減乘除運算與捨入模式）
  • Amdahl's Law / CPI 分析：可參考 Chapter1_Introduction.md 中的效能評估章節