[CS311] 4. 단일 사이클 프로세서 설계

KAIST CS311 전산기조직 (Spring 2023) 교재: Computer Organization and Design: The Hardware/Software Interface (Patterson & Hennessy, MIPS Edition)

MIPS Implementation 개요

프로세서는 명령어를 실행하는 하드웨어이다. 프로세서 설계의 핵심 질문은 **“각 명령어를 어떻게 하드웨어로 구현할 것인가?”**이다.

MIPS 프로세서 구현을 다룰 때, 크게 두 가지 설계 방식을 비교한다:

Single Cycle (단일 사이클): 한 클럭 사이클 안에 하나의 명령어를 완전히 실행
Pipelined (파이프라인): 여러 명령어를 단계별로 겹쳐서 실행

이번 글에서는 단일 사이클 프로세서의 설계를 집중적으로 다룬다.

Clocking Methodology

Clocking methodology란 clock signal 하에서 state element(상태 소자)의 데이터가 “언제” valid하고 stable한지를 정의하는 방법론이다.

        ┌───┐   ┌───┐   ┌───┐   ┌───┐
Clock:  │   │   │   │   │   │   │   │
     ───┘   └───┘   └───┘   └───┘   └───
        ↑       ↑       ↑       ↑
     rising  rising  rising  rising
      edge    edge    edge    edge

Edge-triggered clocking: 모든 state change는 clock edge (보통 rising edge)에서 발생한다
Clock edge 사이의 시간 동안 combinational logic이 값을 계산하고, 다음 edge에서 결과가 state element에 저장된다

Single Cycle Design

단일 사이클 설계의 핵심 원칙:

하나의 명령어가 정확히 하나의 클럭 사이클에 완료된다 → CPI = 1
하나의 명령어 실행 중 같은 datapath 자원을 두 번 이상 사용할 수 없다
따라서 일부 자원은 **복제(duplicate)**되어야 한다:
- Instruction Memory와 Data Memory 분리 (Harvard Architecture)
- Adder 복제 (PC+4 계산용, branch offset 계산용)

Cycle Time 결정

단일 사이클에서 클럭 주기는 Critical Path (가장 긴 경로)에 의해 결정된다. 가장 오래 걸리는 명령어는 **load word (lw)**이다:

Instruction Critical Path (각 단계의 소요 시간 예시)

             Instr.  I Mem  Reg Rd  ALU Op  D Mem  Reg Wr  Total
            ─────── ────── ─────── ─────── ────── ─────── ──────
  R-type    │ 200  │ 100  │  200  │       │ 100  │       │ 600
  load      │ 200  │ 100  │  200  │  200  │ 100  │       │ 800 ← Critical Path
  store     │ 200  │ 100  │  200  │  200  │      │       │ 700
  beq       │ 200  │ 100  │  200  │       │      │       │ 500
  jump      │ 200  │      │       │       │      │       │ 200

→ lw 명령어의 critical path가 800ps이므로, 클럭 사이클은 최소 800ps가 되어야 한다.

Single Cycle의 장단점

장점: 간단(simple)하고 이해하기 쉬움
단점:
- 시간 낭비: 모든 명령어가 가장 느린 명령어의 시간에 맞춰야 한다
- 면적 낭비: 일부 기능 유닛(functional unit)이 복제되어야 한다

Datapath Elements

MIPS 단일 사이클 프로세서의 datapath를 구성하는 핵심 요소들을 살펴보자.

1. PC (Program Counter)

현재 실행할 명령어의 주소를 저장하는 32-bit 레지스터이다.

               ┌──────┐
  Updated PC  →│      │→ Current PC
   [32-bit]    │  PC  │    [32-bit]
               │      │
               └──────┘
                  ↑
                clock

입력: 갱신된 PC 주소 [32-bit]
출력: 현재 PC 주소 [32-bit]
매 클럭 edge마다 입력 값으로 업데이트됨

2. Instruction Memory

PC가 가리키는 주소에서 명령어를 읽어오는 읽기 전용(read-only) 메모리이다.

               ┌──────────────────┐
  PC address  →│                  │→ Instruction
   [32-bit]    │ Instruction Mem  │    [32-bit]
               │                  │
               └──────────────────┘

입력: PC 주소 [32-bit]
출력: 명령어 바이너리 [32-bit]

3. Register File

32개의 레지스터를 담고 있는 저장소이다. 동시에 2개의 레지스터를 읽고 1개에 쓸 수 있다.

  Read reg 1 [5-bit] →┌──────────────┐→ Read Data 1 [32-bit]
  Read reg 2 [5-bit] →│              │→ Read Data 2 [32-bit]
  Write reg  [5-bit] →│ Register File│
  Write Data[32-bit] →│              │
           RegWrite  →│              │
                       └──────────────┘

입력: Read register number 1/2 [5-bit], Write register number [5-bit], Write Data [32-bit]
출력: Read Data 1/2 [32-bit]
제어 신호:
- RegDst: Write register를 $rd에서 선택? (아니면 $rt)
- RegWrite: Register File에 쓰기 허용?

4. ALU (Arithmetic Logic Unit)

산술/논리 연산을 수행하는 유닛이다.

  Data 1 [32-bit] →┌───────┐→ ALU Result [32-bit]
  Data 2 [32-bit] →│  ALU  │→ Zero [0/1]
  ALU ctrl [4-bit] →│       │
                    └───────┘

입력: 피연산자 data 1/2 [32-bit]
출력: 연산 결과 [32-bit], zero flag [0/1]
제어 신호:
- ALUSrc: ALU의 두 번째 입력으로 immediate를 사용? (아니면 Read Data 2)
- ALU operation [4-bit]: 어떤 연산을 수행할지

5. Data Memory

데이터를 읽거나 쓰는 메모리이다. lw, sw 명령어에서 사용된다.

  Address   [32-bit] →┌──────────────┐→ Read Data [32-bit]
  Write Data[32-bit] →│  Data Memory │
          MemRead    →│              │
          MemWrite   →│              │
                       └──────────────┘

입력: Address [32-bit], Write Data [32-bit]
출력: Read Data [32-bit]
제어 신호:
- MemRead: 메모리에서 읽기?
- MemWrite: 메모리에 쓰기?

Control Unit

Control Unit은 명령어의 opcode [6-bit]를 입력받아 datapath의 모든 제어 신호를 생성한다.

  Instruction [31-26]    ┌──────────────┐
  (opcode) [6-bit]   ───→│              │──→ RegDst
                         │              │──→ RegWrite
                         │   Control    │──→ ALUOp [2-bit]
                         │    Unit      │──→ ALUSrc
                         │              │──→ MemRead
                         │              │──→ MemWrite
                         │              │──→ MemtoReg
                         │              │──→ Branch
                         │              │──→ Jump
                         └──────────────┘

각 제어 신호의 의미

제어 신호	의미
`RegDst`	Write register로 `$rd`를 선택 (0이면 `$rt`)
`RegWrite`	Register File에 데이터를 쓸지 여부
`ALUOp` [2-bit]	ALU Control Unit에 전달할 연산 종류 힌트
`ALUSrc`	ALU 두 번째 입력으로 immediate 사용 여부
`MemRead`	Data Memory에서 데이터 읽기 여부
`MemWrite`	Data Memory에 데이터 쓰기 여부
`MemtoReg`	Register에 저장할 값: Memory 값 (1) vs ALU 결과 (0)
`Branch`	현재 명령어가 branch인지 여부
`Jump`	Jump target으로 PC를 업데이트할지 여부

그리고 이들 신호의 조합으로 다음이 결정된다:

PCSrc: Branch AND Zero이면 1 → PC 입력을 branch target address로 설정

ALU Control Unit

ALU Control Unit은 ALUOp [2-bit]과 명령어의 funct field [6-bit]를 받아 실제 ALU operation [4-bit]을 결정한다.

  ALUOp [2-bit]  ──→┌──────────────┐
                     │  ALU Control │──→ ALU operation [4-bit]
  funct [6-bit]  ──→│    Unit      │
  (Instruction[5-0]) └──────────────┘

ALUOp 디코딩

ALUOp	명령어 종류	의미
`00`	`lw` / `sw`	주소 계산 → ALU는 add 수행
`01`	`beq`	비교 → ALU는 subtract 수행
`10`	R-type	funct field에 따라 연산 결정

ALU Control 신호 결정

ALUOp	Funct field	ALU operation	연산
`00`	xxxxxx	`0010`	add
`01`	xxxxxx	`0110`	subtract
`10`	`100000` (add)	`0010`	add
`10`	`100010` (sub)	`0110`	subtract
`10`	`100100` (and)	`0000`	AND
`10`	`100101` (or)	`0001`	OR
`10`	`101010` (slt)	`0111`	set on less than

ALUOp이 00이나 01이면 funct field와 무관하게 ALU 연산이 고정된다. ALUOp이 10(R-type)일 때만 funct field를 참조하여 구체적인 연산을 결정한다.

전체 프로세서 회로

Jump 미포함 회로

Jump 명령어를 제외한 단일 사이클 프로세서의 전체 datapath이다.

                                                         PCSrc
                                                     (Branch & Zero)
                                                           │
                    ┌───────────────────────────────┐      │
                    │                   ┌────┐      ▼      │
              ┌───┐ │              ┌───→│Shft│→┌────────┐  │
         ┌───→│Add│─┘              │    │ L2 │ │  MUX   │──┘
         │    └───┘                │    └────┘ │(PCSrc) │
         │      ↑                  │           └───┬────┘
     4───┘      │                  │               │
                │                  │               ▼
  ┌────┐   ┌────────────┐  Instr[31-26]     ┌──────────┐
  │    │──→│ Instruction │──────────────────→│ Control  │
  │ PC │   │   Memory    │                   │   Unit   │
  │    │←──│             │                   └──────────┘
  └────┘   └────────────┘                     │ 제어 신호들
               │    │    │                    ▼
          [25-21] [20-16] [15-11]   RegDst, ALUSrc, MemtoReg,
               │    │      │        RegWrite, MemRead, MemWrite,
               ▼    ▼      ▼        Branch, ALUOp
          ┌──────────────────┐
          │   Register File  │
          │  Read    Read    │
          │  Data1   Data2   │
          └───┬────────┬─────┘
              │        │
              │    ┌────────┐
              │    │  MUX   │←── ALUSrc
              │    │(ALUSrc)│←── Sign-extended Imm
              │    └───┬────┘
              ▼        ▼
           ┌──────────────┐
           │     ALU      │──→ Zero
           │              │
           └──────┬───────┘
                  │ ALU Result
             ┌────────┐
             │  MUX   │←── MemtoReg
             │(MemReg)│←── Data Memory Read Data
             └───┬────┘
                 │
                 ▼
            Write Data → Register File

  ┌────────┐
  │  Sign  │←── Instruction [15-0] (16-bit)
  │ Extend │──→ 32-bit immediate
  └────────┘

  ┌─────────┐
  │  ALU    │←── ALUOp [2-bit] + Instruction [5-0] (funct)
  │ Control │──→ ALU operation [4-bit]
  └─────────┘

Jump 포함 회로

Jump 명령어를 지원하려면 추가 MUX와 Shift Left 2 유닛이 필요하다.

Jump의 target address 계산:

Jump target = { PC+4 [31-28],  Instruction[25-0] << 2 }
              ├─ 상위 4-bit ─┤├──── 하위 28-bit ────┤

Instruction[25-0]을 2-bit 왼쪽 시프트 → 28-bit
PC+4의 상위 4-bit과 결합 → 32-bit jump target address

  Instruction [25-0]
        │
        ▼
    ┌────────┐     ┌──────────────────┐
    │Shift   │────→│                  │
    │Left 2  │     │  Concatenation   │
    └────────┘     │  {PC+4[31-28],   │
                   │   shifted[27-0]} │
  PC+4 [31-28]───→│                  │
                   └────────┬─────────┘
                            │ Jump target [32-bit]
                            ▼
                       ┌─────────┐
                       │  MUX    │←── Jump (control signal)
                       │ (Jump)  │←── PCSrc MUX output
                       └────┬────┘
                            │
                            ▼
                         Next PC

전체 회로에서의 MUX 목록:

MUX	제어 신호	선택 0	선택 1
RegDst MUX	`RegDst`	`$rt` (Instr[20-16])	`$rd` (Instr[15-11])
ALUSrc MUX	`ALUSrc`	Read Data 2	Sign-extended Imm
MemtoReg MUX	`MemtoReg`	ALU Result	Memory Read Data
PCSrc MUX	`Branch & Zero`	PC+4	Branch target
Jump MUX	`Jump`	PCSrc MUX 출력	Jump target

기타 주요 요소:

Adder 2개: PC+4 계산 / PC + branch offset 계산
Shift Left 2 유닛 2개: branch offset « 2 / jump target « 2
Sign Extend 1개: 16-bit immediate → 32-bit

Control Signal 진리표

각 명령어 유형별 제어 신호 값을 정리하면 다음과 같다:

제어 신호	R-type	`lw`	`sw`	`beq`	`j`
`RegDst`	1	0	X	X	X
`ALUSrc`	0	1	1	0	X
`MemtoReg`	0	1	X	X	X
`RegWrite`	1	1	0	0	0
`MemRead`	0	1	0	0	0
`MemWrite`	0	0	1	0	0
`Branch`	0	0	0	1	0
`ALUOp`	10	00	00	01	XX
`Jump`	0	0	0	0	1

R-type: RegDst=1 ($rd에 저장), RegWrite=1, ALUOp=10 (funct에 따라 결정)
lw: ALUSrc=1 (immediate offset), MemRead=1, MemtoReg=1 (메모리 값을 레지스터에), RegWrite=1
sw: ALUSrc=1 (immediate offset), MemWrite=1
beq: Branch=1, ALUOp=01 (subtract로 비교)
j: Jump=1만 활성화, 나머지 대부분 don’t care (X)

명령어 실행 흐름 예시

각 명령어 유형이 datapath를 어떻게 거치는지 추적해보자.

R-type (예: `add $rd, $rs, $rt`)

1. IF:  PC → Instruction Memory → Instruction 읽기
2. ID:  Instruction[25-21] → Read reg 1 ($rs)
        Instruction[20-16] → Read reg 2 ($rt)
3. EX:  Read Data 1 + Read Data 2 → ALU (funct에 따른 연산)
4. WB:  ALU Result → Register File의 $rd에 저장
        (RegDst=1, MemtoReg=0, RegWrite=1)

Load Word (`lw $rt, offset($rs)`)

1. IF:  PC → Instruction Memory → Instruction 읽기
2. ID:  Instruction[25-21] → Read reg 1 ($rs)
        Instruction[15-0] → Sign Extend → 32-bit offset
3. EX:  Read Data 1 + Sign-extended offset → ALU (add)
4. MEM: ALU Result → Data Memory Address → Read Data
5. WB:  Memory Read Data → Register File의 $rt에 저장
        (RegDst=0, MemtoReg=1, RegWrite=1)

Store Word (`sw $rt, offset($rs)`)

1. IF:  PC → Instruction Memory → Instruction 읽기
2. ID:  Instruction[25-21] → Read reg 1 ($rs)
        Instruction[20-16] → Read reg 2 ($rt) → Write Data
        Instruction[15-0] → Sign Extend → 32-bit offset
3. EX:  Read Data 1 + Sign-extended offset → ALU (add)
4. MEM: ALU Result → Data Memory Address
        Read Data 2 → Data Memory Write Data
        (MemWrite=1)

Branch Equal (`beq $rs, $rt, offset`)

1. IF:  PC → Instruction Memory → Instruction 읽기
2. ID:  Read reg 1 ($rs), Read reg 2 ($rt)
        Sign Extend offset → Shift Left 2 → branch offset
3. EX:  Read Data 1 - Read Data 2 → ALU (subtract)
        PC+4 + branch offset → branch target address
4. PC:  Zero flag = 1이면 PCSrc=1 → PC = branch target
        Zero flag = 0이면 PCSrc=0 → PC = PC+4
        (Branch=1, ALUOp=01)

Jump (`j target`)

1. IF:  PC → Instruction Memory → Instruction 읽기
2. PC:  Jump target = { PC+4[31-28], Instruction[25-0] << 2 }
        Jump=1 → PC = Jump target

Instruction Critical Path 분석

단일 사이클에서는 가장 느린 명령어의 경로가 전체 성능을 결정한다. 각 단계별 소요 시간(예시)으로 critical path를 분석해보자.

각 유닛의 소요 시간:

유닛	소요 시간
Instruction/Data Memory	200ps
ALU, Adder	200ps
Register File (read/write)	100ps

명령어별 총 시간:

  R-type:  I-Mem(200) + Reg-Read(100) + ALU(200) + Reg-Write(100) = 600ps
  lw:      I-Mem(200) + Reg-Read(100) + ALU(200) + D-Mem(200) + Reg-Write(100) = 800ps
  sw:      I-Mem(200) + Reg-Read(100) + ALU(200) + D-Mem(200) = 700ps
  beq:     I-Mem(200) + Reg-Read(100) + ALU(200) = 500ps
  jump:    I-Mem(200) = 200ps

→ Critical path = lw의 800ps → 클럭 주기 ≥ 800ps

모든 명령어가 800ps를 사용해야 하므로, jump처럼 빠른 명령어도 600ps를 낭비하게 된다. 이것이 단일 사이클 설계의 근본적인 한계이며, 파이프라인(pipeline) 설계의 동기가 된다.

정리

단일 사이클 프로세서의 핵심 특징을 요약하면:

CPI = 1: 모든 명령어가 정확히 한 사이클에 완료
Cycle time은 Critical Path에 의해 결정: 가장 느린 명령어(lw)가 전체 클럭 주기를 결정
자원 복제 필요: Instruction Memory / Data Memory 분리, Adder 복제
Control Unit이 opcode에서 제어 신호 생성, ALU Control Unit이 ALUOp + funct에서 ALU 연산 결정
5개의 MUX가 datapath의 경로를 선택 (RegDst, ALUSrc, MemtoReg, PCSrc, Jump)

단일 사이클 설계는 구조가 단순하여 이해하기 쉽지만, 모든 명령어가 가장 느린 명령어의 시간을 따라야 하는 비효율이 있다. 다음 글에서는 이 문제를 해결하는 파이프라인 프로세서 설계를 다룬다.

MIPS Implementation 개요#

Clocking Methodology#

Single Cycle Design#

Cycle Time 결정#

Single Cycle의 장단점#

Datapath Elements#

1. PC (Program Counter)#

2. Instruction Memory#

3. Register File#

4. ALU (Arithmetic Logic Unit)#

5. Data Memory#

Control Unit#

각 제어 신호의 의미#

ALU Control Unit#

ALUOp 디코딩#

ALU Control 신호 결정#

전체 프로세서 회로#

Jump 미포함 회로#

Jump 포함 회로#

Control Signal 진리표#

명령어 실행 흐름 예시#

R-type (예: add $rd, $rs, $rt)#

Load Word (lw $rt, offset($rs))#

Store Word (sw $rt, offset($rs))#

Branch Equal (beq $rs, $rt, offset)#

Jump (j target)#

Instruction Critical Path 분석#

정리#