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

核心觀念

本題要求設計 MIPS 單週期資料路徑，涵蓋：

• R-type：暫存器對暫存器運算，例如 add $rd,$rs,$rt
• SW：將暫存器資料寫入記憶體
• BNE：兩個暫存器不相等時分支

題目將 SW 與 BNE 和 R-type 並列；嚴格分類上，SW 是 I-type、BNE 也是 I-type，因此本題應理解為「設計可支援 R-type、SW、BNE 的單週期資料路徑」。

MIPS 指令欄位如下：

$$\text{op} = [31:26],\quad rs=[25:21],\quad rt=[20:16],\quad rd=[15:11]$$

I-type 指令的立即數為：

$$\text{imm}=[15:0]$$

分支位址計算公式為：

$$\text{BranchTarget} = PC+4+\left(\text{SignExt}(\text{imm})\ll 2\right)$$

每條指令在一個 clock cycle 內完成，因此不需要多週期控制器；控制訊號由 instruction decoder 根據 opcode 與 funct 欄位產生。

---

指令語意與資料流

1. R-type 指令

R-type 指令的格式為：

op = 000000 | rs | rt | rd | shamt | funct

典型運算：

$$R[rd]\leftarrow R[rs]\ \text{ALU}\ R[rt]$$

資料流：

1. 從 register file 讀取 rs 與 rt
2. ALU 的兩個輸入分別選擇 $R[rs]$ 與 $R[rt]$
3. 根據 funct 決定 ALU 操作
4. 將結果寫回 rd

---

2. SW

SW rt, imm(rs) 的語意為：

$$\text{Memory}[R[rs]+\text{SignExt}(\text{imm})]\leftarrow R[rt]$$

資料流：

1. register file 讀出 $R[rs]$，作為 base address
2. 將 16 位元立即數符號延伸成 32 位元
3. ALU 計算有效位址：

$$\text{Address}=R[rs]+\text{SignExt}(\text{imm})$$

4. 將 $R[rt]$ 的資料寫入 data memory
5. 不寫回 register file

---

3. BNE

BNE rs, rt, imm 的語意為：

$$\text{若 }R[rs]\neq R[rt]\text{，則 }PC\leftarrow PC+4+\left(\text{SignExt}(\text{imm})\ll2\right)$$

資料流：

1. 讀出 $R[rs]$ 與 $R[rt]

核心觀念

本題考查快取記憶體的位址切割與組織方式。32 位元、byte-addressable 機器中：

• 一個 word = $32$ bits = $4$ bytes。
• Cache line 每行存放 $1$ word，因此區塊大小為 $4$ bytes。
• 四路組合（four-way set associative）表示每個 set 包含 $4$ 條 cache line。
• 位址切割公式為：

$$\text{位址位元數} = \text{Tag bits} + \text{Index bits} + \text{Byte-offset bits}$$

其中：

• Byte offset：指定一個 word 中的哪一個 byte。
• Index：指定 cache 中的哪一個 set。
• Tag：用來與該 set 中各 way 的 tag 比對。

---

解題方法

(a) 四路組合快取的結構

Cache 總共有 $1024$ 條 lines，每個 set 有 $4$ 條 lines，因此 set 數量為：

$$\text{Sets} = \frac{1024}{4} = 256 = 2^8$$

所以需要 $8$ 個 index bits。

每條 cache line 存放 $1$ word，而一個 word 為 $4$ bytes，因此需要：

$$\log_2 4 = 2$$

個 byte-offset bits。

Tag 位元數為：

$$32 - 8 - 2 = 22$$

因此 32 位元位址格式如下：

$$\boxed{ \text{Tag }(22\text{ bits}) \mid \text{Index }(8\text{ bits}) \mid \text{Byte offset }(2\text{ bits}) }$$

Cache 可表示如下：

                         32-bit byte address
              ┌────────────────┬──────────┬────────────┐
              │   Tag 22 bits  │ Index 8  │ Offset 2   │
              └────────────────┴──────────┴────────────┘
                                      │
                                      ▼
                              選擇 256 個 sets 之一

Set 0       ┌─────────────────────────────────────────┐
            │ Way 0 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 1 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 2 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 3 │ Valid │ Tag │ 1 word = 32 bits │
            └─────────────────────────────────────────┘

Set 1       ┌─────────────────────────────────────────┐
            │ Way 0 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 1 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 2 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 3 │ Valid │ Tag │ 1 word = 32 bits │
            └─────────────────────────────────────────┘

   ⋮

Set 255     ┌─────────────────────────────────────────┐
            │ Way 0 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 1 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 2 │ Valid │ Tag │ 1 word = 32 bits │
            │ Way 3 │ Valid │ Tag │ 1 word = 32 bits │
            └─────────────────────────────────────────┘

參考書等級：Computer Organization & Design (5 版) – 中等難度，適合作為碩二考前快速複習。

---

(a) 執行總循環數

指令總數：$5\;\text{instr}\times 10=50$
pipeline 起始填充：$4$ cycles

1. 資料冒險

• LW → ADD 產生 load‑use hazard，需插入 1 cycle bubble。
  $10$ 次迭代 $\Rightarrow 10$ cycles。

2. 快取未命中

• 直映快取，行長 $4$ words → 每 $4$ 個存取一次 miss。
  起始地址假設為 $0$，則第 $1,5,9$ 次 LW miss。
  每次 miss 需額外 $10$ cycles（加上 1‑cycle hit）。
  $3$ 次 miss $\Rightarrow 3\times10=30$ cycles。

3. 分支預測

• 第一次分支未見歷史，預測為 not‑taken → 失誤 $2$ cycles。
• 第 $10$ 次迭代不再跳回，預測仍為 taken → 再失誤 $2$ cycles。
  共 $2$ 次失誤 $\Rightarrow 4$ cycles。

4. 合計

(a) 存儲需求

• 隱藏層 1‒3：每層 256 × 256 = 65 536 個權重
  → 3 × 65 536 = 196 608 個權重
• 輸出層：256 × 10 = 2 560 個權重
• 總權重數 = 196 608 + 2 560 = 199 168 個

每個權重、偏置皆為 IEEE 754 single‑precision (4 Byte)

• 權重儲存量：199 168 × 4 = 796 672 Byte
• 偏置數量：隱藏層 3 × 256 + 10 = 778 個
  → 778 × 4 = 3 112 Byte

總儲存量
$796\,672\ \text{Byte} + 3\,112\ \text{Byte}=799\,784\ \text{Byte}\approx 781.4\ \text{KiB}$

【答案】799 784 Byte (≈ 781 KiB)

---

(b) 1 KiB 權重 SRAM 之外的片上需求

• SRAM 大小：1 KiB = 1 024 Byte
• 快取區塊大小：32 Byte → 每塊 8 個權重

位址位元數：
$\lceil\log_2(796\,672)\rceil = 20\ \text{bits}$

快取結構：

• 內部資料行數 = 1 024 / 32 = 32 行
• 內部索引位元 = $\log_2 32 = 5$ bits
• 區塊位元 = $\log_2 32 = 5$ bits

Tag 位元 = 20 − 5 − 5 = 10 bits
每行需儲存 Tag (10 b) + Valid (1 b) = 11 bits

全部 32 行的額外儲存：
$32 \times 11\ \text{bits}=352\ \text{bits}=44\ \text{Byte}$

（若以最小位元組為單位，可視為 48 Byte。）