課程:Introduction to Computer Organization (CCIT4026) 主題:單周期處理器的控制單元設計與完整執行範例


目錄

  1. 學習目標
  2. 單周期 Datapath 回顧
  3. 兩級解碼設計(Two-Level Decoding)
  4. ALU Control(第二級解碼)
  5. Main Control(第一級解碼)
  6. 9 個控制訊號的意義
  7. 各類指令的控制訊號設定
  8. 控制單元的硬體實作
  9. 完整執行範例
  10. 單周期處理器的特性
  11. 重點整理與小結

學習目標

完成本章後,你應該能夠:

  • 理解 MIPS 單周期處理器中控制單元的設計方法。
  • 說明兩級解碼(Two-Level Decoding)機制:Main Control 與 ALU Control 的職責分工。
  • 為 R-type、lw、sw、beq 指令推導出完整的控制訊號真值表
  • 分析每個控制訊號(RegDst、ALUSrc、MemRead 等)對 Datapath 行為的影響。
  • 透過邏輯閘實作 Main Control 與 ALU Control。
  • 追蹤一段程式碼在單周期處理器上的逐周期執行過程

單周期 Datapath 回顧

第 7 章已建立的單周期 Datapath 包含:

+----------+    +-------------+    +-----------+    +-----------+
| PC + 4   |    | Branch Addr |    |   Jump    |    |   Sign    |
|  Adder   |    |  Generator  |    |   Logic   |    |  Extend   |
+----------+    +-------------+    +-----------+    +-----------+

+----------+    +-------------+    +-----------+    +-----------+
| Instr    |    |  Register   |    |    ALU    |    |   Data    |
| Memory   |    |    File     |    |           |    |  Memory   |
+----------+    +-------------+    +-----------+    +-----------+

+--------- 多個 MUX、控制訊號連接到上述模組 ---------+

但是 — Datapath 本身不知道該對 R-type、lw、sw、beq 做不同的事。它需要控制單元(Control Unit)告訴它:

  • 哪一個 MUX 該選哪一個輸入?
  • ALU 該執行甚麼運算?
  • 是否要寫回暫存器?是否要存取記憶體?

本章主要解決:Control Unit 如何根據指令產生這些控制訊號?

MIPS 三種指令格式回顧

R-type:  | opcode | rs    | rt    | rd    | shamt | funct |
         |  6 bit | 5 bit | 5 bit | 5 bit | 5 bit | 6 bit |
         | [31:26]|[25:21]|[20:16]|[15:11]|[10:6] | [5:0] |

I-type:  | opcode | rs    | rt    |    immediate (16-bit)  |
         |  6 bit | 5 bit | 5 bit |        16 bit          |
         | [31:26]|[25:21]|[20:16]|       [15:0]           |

J-type:  | opcode |     immediate (26-bit)                 |
         |  6 bit |              26 bit                    |
         | [31:26]|              [25:0]                    |

觀察opcode 永遠在 [31:26]funct 永遠在 [5:0](只有 R-type 有意義)。Main Control 從 opcode 解碼,ALU Control 從 funct 解碼。


兩級解碼設計(Two-Level Decoding)

為何要分兩級?

問題:若只用一個大解碼器,輸入要包含 6-bit opcode + 6-bit funct = 12-bit,輸出 9 條控制訊號 + 4-bit ALU control,這會導致真值表過於龐大

解法:分兩級解碼,先用 opcode 產生大部分控制訊號,再針對 ALU 操作(受 funct 影響)做第二級解碼。

兩級解碼架構

                     opcode (6-bit)
                     instr[31:26]
                          │
                          ▼
                  ┌───────────────┐
                  │ Main Control  │
                  │  (1st level)  │
                  └───────┬───────┘
                          │
   ┌──────────────────────┴────────────────────────┐
   │                                                │
   ▼                                                ▼
9 個輸出控制訊號:                            ALUOp (2-bit)
   - RegDst                                         │
   - Branch                              funct (6-bit)
   - MemRead                             instr[5:0]
   - MemtoReg                                       │
   - MemWrite                                       ▼
   - ALUSrc                                ┌────────────────┐
   - RegWrite                              │  ALU Control   │
                                           │  (2nd level)   │
                                           └────────┬───────┘
                                                    │
                                                    ▼
                                              ALUctr (4-bit)
級數 名稱 輸入 輸出
第一級 Main Control opcode (6 bits, instr[31:26]) 9 個控制訊號(含 2-bit ALUOp)
第二級 ALU Control ALUOp (2 bits) + funct (6 bits, instr[5:0]) ALUctr (4 bits) — 控制 ALU 運算

每個控制訊號的值可為01X(don't care,不影響行為時設為 X 可簡化邏輯)。


ALU Control(第二級解碼)

ALUOp 的意義(2-bit)

ALUOp 意義
00 lw / sw — ALU 必須做 add(計算位址 base + offset)
01 beq — ALU 必須做 subtract(比較是否相等)
10 R-type — ALU 動作要看 funct 欄位決定
11 (目前未使用)

ALU Control 真值表

ALUOp Funct (6-bit) ALUctr (4-bit) 對應運算
00 XXXXXX 0010 add (for lw/sw)
01 XXXXXX 0110 subtract (for beq)
10 100000 0010 add (R-type add)
10 100010 0110 subtract (R-type sub)
10 100100 0000 AND (R-type and)
10 100101 0001 OR (R-type or)
10 101010 0111 slt (R-type set-on-less-than)

化簡後的真值表(含 don't care)

由於 ALUOp 不會出現 11,可以利用 don't care 簡化:

ALUOp1 ALUOp0 F5 F4 F3 F2 F1 F0 Operation
0 0 X X X X X X 0010 (add)
X 1 X X X X X X 0110 (sub)
1 X X X 0 0 0 0 0010 (add)
1 X X X 0 0 1 0 0110 (sub)
1 X X X 0 1 0 0 0000 (AND)
1 X X X 0 1 0 1 0001 (OR)
1 X X X 1 0 1 0 0111 (slt)

觀察: - F5、F4 在 R-type 中總是 10,因此可設為 don't care。 - 只用 F3、F2、F1、F0 來區分 R-type 中的不同運算。 - 真值表建構完成後,可以使用 K-map 或 Quine-McCluskey 法最佳化並轉為邏輯閘電路。


Main Control(第一級解碼)

設計觀察

要設計 Main Control,必須觀察各指令格式中 fields 的位置:

R-type:  | opcode |  rs   |  rt   |  rd   | shamt | funct |
                  └──────────┴──── 一定要讀 ──┘   └── R-type 才有 ──┘

I-type:  | opcode |  rs   |  rt   |   immediate (16-bit)   |
                  └────── 一定要讀 ─┘  └── lw/sw 用作 offset ──┘
                  └─ rt 是 lw 的目的暫存器(要寫回) ─┘

J-type:  | opcode |       immediate (26-bit)                |

重要設計觀察

  1. rs 永遠要讀:所有 R-type、I-type 指令都要讀取 rs
  2. rt 大多要讀:R-type 與 sw、beq 要讀 rt;只有 lw 不需讀。
  3. 寫回的目標暫存器:R-type 寫到 rdinstr[15:11]);lw 寫到 rtinstr[20:16])。
  4. 第二 ALU 運算元:R-type、beq 來自 rt;lw、sw 來自 sign-extended immediate。

這就是為何需要 RegDstALUSrc 這兩個 MUX 控制訊號。


9 個控制訊號的意義

Main Control 輸出的 9 個訊號

訊號 1-bit / 2-bit Deasserted (= 0) 的效果 Asserted (= 1) 的效果
RegDst 1-bit 寫入暫存器號碼來自 rt(bits [20:16]) 寫入暫存器號碼來自 rd(bits [15:11])
RegWrite 1-bit 不寫入暫存器 將 Write Data 寫入 Write Register
ALUSrc 1-bit ALU 第二輸入來自 Read Data 2 ALU 第二輸入來自 sign-extended immediate(16-bit)
PCSrc* 1-bit PC ← Adder 輸出(PC + 4) PC ← Branch Target 計算結果
MemRead 1-bit 不讀取記憶體 從 Address 讀出資料到 Read Data
MemWrite 1-bit 不寫入記憶體 將 Write Data 寫入 Address
MemtoReg 1-bit 寫回暫存器的資料來自 ALU 寫回暫存器的資料來自 Data Memory
Branch 1-bit 非分支指令 是分支指令
ALUOp 2-bit 控制 ALU Control 的行為(見前節)

* PCSrc 並非由 Main Control 直接輸出,而是 Branch AND Zero 邏輯產生的訊號。

規則:「1-bit 控制訊號被「assert」就是設為 1;「deassert」就是設為 0


各類指令的控制訊號設定

Opcode 對照表(Main Control 輸入)

Instruction Opcode (Decimal) Op5 Op4 Op3 Op2 Op1 Op0
R-format 0 0 0 0 0 0 0
lw 35 (0x23) 1 0 0 0 1 1
sw 43 (0x2B) 1 0 1 0 1 1
beq 4 0 0 0 1 0 0

Main Control 輸出表

Instruction RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0
R-format 1 0 0 1 0 0 0 1 0
lw 0 1 1 1 1 0 0 0 0
sw X 1 X 0 0 1 0 0 0
beq X 0 X 0 0 0 1 0 1

這張表是整個 Main Control 的真值表!它即是控制邏輯的規格。

各指令詳細解析

(1) R-format 指令(add / sub / and / or / slt)

R-format: 1 0 0 1 0 0 0 1 0
        RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0

理由分析

訊號 為何?
RegDst 1 目的暫存器是 rd
ALUSrc 0 第二運算元來自 rt 暫存器
MemtoReg 0 寫回的資料來自 ALU 結果,不是記憶體
RegWrite 1 要寫回暫存器
MemRead 0 不讀記憶體
MemWrite 0 不寫記憶體
Branch 0 非分支指令;下一個 PC = PC + 4
ALUOp 10 由 funct 欄位決定 ALU 運算

範例 Datapath:add $a2, $a0, $a1

Instr[25:21] = $a0 ─► Read register 1 ─► Read data 1 ─┐
Instr[20:16] = $a1 ─► Read register 2 ─► Read data 2 ─┤
                                                       ▼
                                                    [ALU] ── Result ──► (RegDst=1)
                                                                          │
Instr[15:11] = $a2 ─► Write register ◄── (RegDst=1)                       │
                                                                          ▼
                                              Write data ◄── (MemtoReg=0, RegWrite=1)

(2) lw 指令

lw: 0 1 1 1 1 0 0 0 0
   RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0

理由分析

訊號 為何?
RegDst 0 目的暫存器是 rt
ALUSrc 1 第二運算元來自 sign-extended immediate(offset)
MemtoReg 1 寫回的資料來自記憶體
RegWrite 1 要將讀到的資料寫回暫存器
MemRead 1 要讀記憶體
MemWrite 0 不寫記憶體
Branch 0 非分支
ALUOp 00 ALU 做 add(計算 base + offset)

範例:lw $a0, 4($a1)

Instr[25:21] = $a1 ─► Read register 1 ─► Read data 1 = ($a1) ─┐
Instr[15:0]  = 4   ─► Sign Extend ─► 4 (32-bit) ──────────────┤
                                                                ▼
                                                              [ALU] ── ($a1) + 4
                                                                         │
                                                                         ▼
                                              Address ──► [Data Memory] ─► Read data
                                                                                │
Instr[20:16] = $a0 ─► Write register                                            │
                                                                                ▼
                                                                Write data ◄── (MemtoReg=1)

(3) sw 指令

sw: X 1 X 0 0 1 0 0 0
  RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0

理由分析

訊號 為何?
RegDst X 不寫暫存器,don't care
ALUSrc 1 第二運算元來自 immediate(與 lw 相同)
MemtoReg X 不寫暫存器,don't care
RegWrite 0 不寫暫存器
MemRead 0 不讀記憶體
MemWrite 1 寫入記憶體
Branch 0 非分支
ALUOp 00 ALU 做 add(計算位址,與 lw 相同)

記憶口訣swlw 的「鏡像」,差別在於:lw 是 Read,sw 是 Write;lw 寫回暫存器,sw 不寫回。

範例:sw $a0, 4($a1)

Instr[25:21] = $a1 ─► Read register 1 ─► Read data 1 = ($a1) ─┐
Instr[20:16] = $a0 ─► Read register 2 ─► Read data 2 = ($a0) ─┐│
                                                              ││
Instr[15:0]  = 4   ─► Sign Extend ─► 4 (32-bit) ──┐           ││
                                                  ▼           ▼│
                                                 [ALU] ── ($a1)+4
                                                              │
                                                              ▼
                                              Address ──► [Data Memory]
                                                              ▲
                                                              │
                                              Write data ◄────┘ (Read data 2 = $a0)
                                              MemWrite=1

(4) beq 指令

beq: X 0 X 0 0 0 1 0 1
   RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp1 ALUOp0

理由分析

訊號 為何?
RegDst X 不寫暫存器,don't care
ALUSrc 0 第二運算元來自暫存器(與 R-type 相同)
MemtoReg X 不寫暫存器,don't care
RegWrite 0 不寫暫存器
MemRead 0 不讀記憶體
MemWrite 0 不寫記憶體
Branch 1 是分支指令
ALUOp 01 ALU 做 subtract(比較是否相等)

PCSrc 的產生

PCSrc = Branch AND Zero

只有當「Branch == 1」且「ALU 的 Zero == 1」時,PC 才會載入 Branch Target Address。

範例:beq $a0, $a1, -6

Instr[25:21] = $a0 ─► Read data 1 ─┐
Instr[20:16] = $a1 ─► Read data 2 ─┤
                                    ▼
                                  [ALU] (做減法)── Zero (1 if $a0 == $a1)
                                                       │
PC + 4 ─────────────┐                                  │
                    ▼                                  │
Sign-extended (-6) × 4 = -24 ─► [Add] ── Branch Target │
                                            │          │
                                            ▼          │
                                        [PC MUX] ◄─────┴─── PCSrc = Branch AND Zero
                                            │
                                            ▼
                                          New PC

控制單元的硬體實作

第一級(Main Control)邏輯實作

從 Main Control 真值表可以看到,每個輸出訊號都是 6-bit opcode(Op5、Op4、Op3、Op2、Op1、Op0)的函式。

例如,R-format = 1 當 opcode = 000000,可以表示為:

R-format = (NOT Op5) AND (NOT Op4) AND (NOT Op3) AND (NOT Op2) AND (NOT Op1) AND (NOT Op0)

每個控制訊號可以表示為某些 opcode 模式的 OR 組合:

RegDst    = R-format
ALUSrc    = lw OR sw
MemtoReg  = lw
RegWrite  = R-format OR lw
MemRead   = lw
MemWrite  = sw
Branch    = beq
ALUOp1    = R-format
ALUOp0    = beq

這些邏輯式可以用簡單的 AND、OR、NOT 邏輯閘實作。

第二級(ALU Control)邏輯實作

ALU Control 的輸入:ALUOp1、ALUOp0、F3、F2、F1、F0(F5、F4 為 don't care)。 輸出:4-bit ALUctr = Operation3、Operation2、Operation1、Operation0。

                        ALUOp1 ──┐
                        ALUOp0 ──┤
                                  │
                  ┌───────────────┘
                  │
                  ▼
        +-----------------+
        | ALU Control     |── Operation 3 (Op3)
        |  Block          |── Operation 2 (Op2)
        |                 |── Operation 1 (Op1)
        |                 |── Operation 0 (Op0)
        +-----------------+
                  ▲
                  │
        F3, F2, F1, F0 (從 instr[5:0] 取得)

整體控制單元的架構

                opcode[5:0]
                    │
                    ▼
        ┌─────────────────────┐
        │   Main Control      │
        │   (1st level)       │
        └──┬──────────────────┘
           │
   ┌───────┴────────────────────────┐
   │                                │
   ▼                                ▼
 (8 個直接輸出訊號)              ALUOp[1:0]
                                    │
                       funct[5:0] ──┤
                                    ▼
                          ┌─────────────────┐
                          │  ALU Control    │
                          │  (2nd level)    │
                          └────────┬────────┘
                                   │
                                   ▼
                              ALUctr[3:0]
                              (送入 ALU)

完整執行範例

題目

下列指令序列在單周期處理器上執行,請追蹤每條指令在每條匯流排上的資料:

L1: sw    $t1, 5($s0)        # 101011 10000 01001 0000 0000 0000 0101
    sub   $t0, $s1, $s2      # 000000 10001 10010 01000 00000 100010
    beq   $t0, $t1, L1       # 000100 01000 01001 1111 1111 1111 1101

執行前的初始狀態

暫存器/記憶體
$s0 100
$s1 500
$s2 300
$t1 200
L1 1000
mem[105] 6

註:因為 L1: sw...,所以 L1 的位址(即 sw 指令所在位址)= 1000。


指令 1:sw $t1, 5($s0)(PC = 1000)

指令解碼

opcode = 101011 (43d) → sw
   rs  = 10000  (16d) → $s0
   rt  = 01001  (9d)  → $t1
offset = 0000 0000 0000 0101 (5d)

控制訊號

訊號
RegDst X
ALUSrc 1
MemtoReg X
RegWrite 0
MemRead 0
MemWrite 1
Branch 0
ALUOp 00
ALUctr 0010 (add)

資料路徑追蹤

匯流排 說明
PC 1000 目前 PC
Instruction (上述機器碼) 從 Instr Mem 讀出
Read register 1 $s0 = 16 rs
Read register 2 $t1 = 9 rt
Read data 1 100 ($s0) 的值
Read data 2 200 ($t1) 的值
Sign Extend(5) 5 32-bit
ALU 第二輸入 5 ALUSrc=1
ALU 結果 105 100 + 5
Memory Address 105 ALU 結果
Memory Write Data 200 $t1 的值
結果 mem[105] = 200 寫入完成
下一個 PC 1004 PC + 4

指令 2:sub $t0, $s1, $s2(PC = 1004)

指令解碼

opcode = 000000 (0)  → R-type
   rs  = 10001 (17d) → $s1
   rt  = 10010 (18d) → $s2
   rd  = 01000 (8d)  → $t0
 shamt = 00000
 funct = 100010 → sub

控制訊號

訊號
RegDst 1
ALUSrc 0
MemtoReg 0
RegWrite 1
MemRead 0
MemWrite 0
Branch 0
ALUOp 10
ALUctr 0110 (sub)

資料路徑追蹤

匯流排 說明
PC 1004 目前 PC
Read register 1 $s1 = 17 rs
Read register 2 $s2 = 18 rt
Read data 1 500 ($s1)
Read data 2 300 ($s2)
ALU 第二輸入 300 ALUSrc=0,來自 Read data 2
ALU 結果 200 500 - 300
Write register $t0 = 8 RegDst=1,來自 rd
Write data 200 MemtoReg=0,來自 ALU
結果 $t0 = 200 寫回完成
下一個 PC 1008 PC + 4

指令 3:beq $t0, $t1, L1(PC = 1008)

指令解碼

opcode = 000100 (4)  → beq
   rs  = 01000 (8d)  → $t0
   rt  = 01001 (9d)  → $t1
offset = 1111 1111 1111 1101 (-3,補碼)

控制訊號

訊號
RegDst X
ALUSrc 0
MemtoReg X
RegWrite 0
MemRead 0
MemWrite 0
Branch 1
ALUOp 01
ALUctr 0110 (sub)

資料路徑追蹤

匯流排 說明
PC 1008 目前 PC
Read register 1 $t0 = 8 rs
Read register 2 $t1 = 9 rt
Read data 1 200 ($t0),剛剛被寫入
Read data 2 200 ($t1)
ALU 結果 0 200 - 200 = 0
Zero 1 結果為 0,相等!
PC + 4 1012
Sign-extended offset × 4 -12 -3 × 4
Branch target 1000 1012 + (-12) = 1000
PCSrc 1 Branch=1 AND Zero=1
下一個 PC 1000 跳回 L1

觀察beq 條件成立,PC 跳回 1000,回到 sw 指令。形成一個迴圈。


單周期處理器的特性

一條指令在單周期 Datapath 中的五個步驟

雖然「單周期」表示一個時脈周期內完成所有事情,但邏輯上仍可分成五個步驟:

步驟 名稱 動作
1 Instruction Fetch 從 Instr Memory 讀指令;PC ← PC + 4
2 Instruction Decode / Register Read 解碼指令;讀取 rs、rt 暫存器值
3 Execution / Address Computation / Branch Completion ALU 執行運算;分支指令計算 target、判斷是否分支
4 Memory Access / R-type Completion lw/sw 存取資料記憶體;R-type 已完成
5 Write-back R-type / lw 將結果寫回暫存器

不同指令所需的步驟(時間長度比較)

ALU指令(R-type):
   |Instr Fetch|Reg Read|  ALU  |Reg Write|

Load (lw):
   |Instr Fetch|Reg Read|  ALU  |Memory Read|Reg Write|   ◄ 最長路徑

Store (sw):
   |Instr Fetch|Reg Read|  ALU  |Memory Write|

Branch (beq):
   |Instr Fetch|Reg Read|  ALU  |

Jump (j):
   |Instr Fetch| Decode |

關鍵特性

  1. One clock cycle per instruction (CPI = 1):每條指令只需一個時脈周期。
  2. Long cycle time(時脈周期長):時脈周期必須等於最慢指令所需的時間(即 lw)。
  3. No functional unit can be used twice in one clock cycle:在同一個時脈周期內,一個功能單元最多只能被使用一次(這是為甚麼需要分開的 PC+4 Adder、Branch Target Adder、ALU)。
  4. 資源浪費:例如 R-type 不需要 Memory,但 Memory 在每個周期都存在;Jump 不需要 ALU,但 ALU 仍須等待時脈周期結束。

結論:單周期處理器簡單但效能差。下一章將介紹多周期處理器,每條指令依其需求使用不同數量的時脈周期,以提高整體效能。


重點整理與小結

核心觀念

  1. 控制單元採用兩級解碼: - Main Control:以 6-bit opcode 為輸入,產生 9 個控制訊號。 - ALU Control:以 ALUOp + funct 為輸入,產生 4-bit ALUctr。

  2. 9 個主要控制訊號: - RegDstRegWriteALUSrcALUOp[1:0]MemReadMemWriteMemtoRegBranch

  3. PCSrc 並非 Main Control 的直接輸出,而是 Branch AND Zero 的邏輯結果。

  4. don't care (X):當訊號的值不影響行為時,標為 X 可簡化邏輯設計。

重要真值表(背起來!)

Instruction RegDst ALUSrc MemtoReg RegWrite MemRead MemWrite Branch ALUOp
R-format 1 0 0 1 0 0 0 10
lw 0 1 1 1 1 0 0 00
sw X 1 X 0 0 1 0 00
beq X 0 X 0 0 0 1 01

解題步驟(控制訊號題型)

當題目給你一個 MIPS 指令,要你列出控制訊號時:

  1. 觀察 opcode:是 R-type、lw、sw 還是 beq?
  2. 查表:根據上面的真值表填入 9 個控制訊號。
  3. 若是 R-type,再依 funct 決定 ALUctr: - 100000 → add → 0010 - 100010 → sub → 0110 - 100100 → AND → 0000 - 100101 → OR → 0001 - 101010 → slt → 0111

單周期處理器的優缺點

優點 缺點
設計簡單、容易理解 時脈周期長(受最慢指令限制)
CPI = 1 資源利用率低(功能單元常常閒置)
控制邏輯為純組合邏輯(無狀態) 必須複製多份功能單元(如多個 Adder)
容易除錯 難以擴展為高效能處理器

下一章預告

  • 第 9 章:將介紹多周期處理器(Multi-cycle Processor)
  • 每條指令依其需求使用 3~5 個時脈周期。
  • 每個時脈周期較短(由最慢的功能單元決定)。
  • 功能單元可在不同周期內重複使用(如同一個 ALU、同一個 Memory)。
  • 控制單元由有限狀態機(FSM) 實作,較單周期更複雜。