[CS311] 5. 파이프라인 프로세서와 해저드

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

파이프라인 설계

앞서 Single Cycle 프로세서를 설계했다. 모든 명령어가 한 클럭 사이클에 실행되어 구조는 단순하지만, 가장 느린 명령어에 맞춰 클럭을 설정해야 하므로 성능에 한계가 있다. 이번 글에서는 파이프라인(Pipeline) 기법을 도입하여 throughput을 높이는 방법과, 파이프라인에서 발생하는 해저드(Hazard) 및 그 해결책을 다룬다.

Instruction Critical Path

각 명령어 유형별 실행 시간은 다음과 같다:

명령어 유형	실행 시간
R-type	600 ps
Load (lw)	800 ps
Store (sw)	700 ps
Branch (beq)	500 ps
Jump (j)	200 ps

Single Cycle에서는 모든 명령어가 한 클럭 사이클에 완료되어야 하므로, 클럭 사이클은 가장 느린 명령어인 **load instruction(800 ps)**에 맞춰야 한다. 이것이 Single Cycle의 critical path이다.

Single Cycle Design의 한계

장점:

구조가 단순하고 이해하기 쉽다

단점:

클럭 사이클이 가장 느린 명령어에 맞춰져야 한다
빠른 명령어(jump = 200 ps)도 느린 클럭(800 ps)에 맞춰 실행되므로 자원이 낭비된다
면적(area) 낭비가 심하다

이런 비효율을 해결하기 위해 파이프라인을 도입한다.

5-Stage Pipeline

MIPS 파이프라인은 명령어 실행을 **5개의 단계(stage)**로 나눈다:

┌──────┐   ┌──────┐   ┌──────┐   ┌──────┐   ┌──────┐
│  IF  │──▶│  ID  │──▶│  EX  │──▶│ MEM  │──▶│  WB  │
│IFetch│   │ Dec  │   │ Exec │   │ Mem  │   │Write │
│      │   │      │   │      │   │      │   │ Back │
└──────┘   └──────┘   └──────┘   └──────┘   └──────┘

각 단계의 역할은 다음과 같다:

IF (Instruction Fetch): Instruction Memory에서 명령어를 읽고 PC를 업데이트한다
ID (Instruction Decode): 명령어를 해독하고 Register File에서 레지스터 값을 읽는다
EX (Execute): ALU를 사용하여 R-type 연산을 수행하거나, 메모리 주소를 계산한다
MEM (Memory Access): Data Memory에서 읽기/쓰기를 수행한다
WB (Write Back): 결과 데이터를 Register File에 기록한다

파이프라인의 핵심 아이디어는 세탁소 비유와 같다. 빨래 한 묶음이 건조기에 들어가 있는 동안, 다음 빨래를 세탁기에 넣을 수 있다. 마찬가지로 하나의 명령어가 EX 단계에 있을 때, 다음 명령어는 ID 단계에, 그 다음 명령어는 IF 단계에 있을 수 있다.

Time →   CC1    CC2    CC3    CC4    CC5    CC6    CC7    CC8    CC9
       ┌──────┬──────┬──────┬──────┬──────┐
Instr1 │  IF  │  ID  │  EX  │ MEM  │  WB  │
       └──────┴──────┴──────┴──────┴──────┘
              ┌──────┬──────┬──────┬──────┬──────┐
Instr2        │  IF  │  ID  │  EX  │ MEM  │  WB  │
              └──────┴──────┴──────┴──────┴──────┘
                     ┌──────┬──────┬──────┬──────┬──────┐
Instr3               │  IF  │  ID  │  EX  │ MEM  │  WB  │
                     └──────┴──────┴──────┴──────┴──────┘
                            ┌──────┬──────┬──────┬──────┬──────┐
Instr4                      │  IF  │  ID  │  EX  │ MEM  │  WB  │
                            └──────┴──────┴──────┴──────┴──────┘
                                   ┌──────┬──────┬──────┬──────┬──────┐
Instr5                             │  IF  │  ID  │  EX  │ MEM  │  WB  │
                                   └──────┴──────┴──────┴──────┴──────┘

SC vs Pipeline 비교

항목	Single Cycle	Pipeline
Clock Cycle	가장 느린 명령어	가장 느린 stage
Latency	= Clock Cycle	= Clock Cycle × 파이프라인 단계 수
CPI	1	≥ 1 (이상적으로 1, stall 삽입 시 > 1)
Throughput (T)	T_sc = 1/CC	T_p = 1/CC × (1/단계 수) ≈ 단계 수 배 향상

핵심: 파이프라인은 개별 명령어의 latency를 줄이지 않는다. 오히려 pipeline register로 인해 약간 늘어난다. 파이프라인이 향상시키는 것은 throughput(단위 시간당 완료되는 명령어 수)이다.

MIPS가 Pipelining에 유리한 이유

MIPS ISA는 파이프라인에 최적화된 설계를 가지고 있다:

모든 명령어가 32-bit 고정 길이 → Fetch와 Decode가 쉽다
명령어 포맷이 적고 규칙적 (R/I/J 세 가지) → Decode와 Register Read가 간단하다
Load/Store 구조 → 주소 모드(addressing mode)가 하나뿐이므로 EX에서 주소 계산, MEM에서 메모리 접근으로 깔끔하게 나뉜다
메모리 피연산자의 정렬(Alignment) → 메모리 접근이 한 사이클에 완료된다

이런 특성 덕분에 MIPS는 5단계 파이프라인에 자연스럽게 매핑된다.

Pipeline Registers

파이프라인의 각 stage 사이에는 **pipeline register(= state register, latch)**가 존재한다:

        IF/ID        ID/EX        EX/MEM       MEM/WB
          │            │            │            │
┌────┐    │   ┌────┐   │   ┌────┐   │   ┌────┐   │   ┌────┐
│ IF │────┤   │ ID │───┤   │ EX │───┤   │MEM │───┤   │ WB │
└────┘    │   └────┘   │   └────┘   │   └────┘   │   └────┘
          │            │            │            │
     ┌────┴────┐  ┌────┴────┐  ┌────┴────┐  ┌────┴────┐
     │ IF/ID   │  │ ID/EX   │  │ EX/MEM  │  │ MEM/WB  │
     │ Register│  │ Register│  │ Register│  │ Register│
     └─────────┘  └─────────┘  └─────────┘  └─────────┘

Pipeline register의 역할:

각 stage를 isolate하는 latch 역할
각 stage에 필요한 Data와 Control Signal을 저장
한 cycle당 signal은 latch에서 다음 latch까지만 전송된다 (latch 단위로 끊김)

PC와 모든 pipeline register는 동일한 System Clock signal로 구동된다 → 같은 타이밍에 동작한다.

Control Signals

파이프라인의 control signal은 Single Cycle에서와 동일하다. opcode로부터 8 + 1개의 control signal이 생성된다. 핵심은 ID stage에서 모든 control signal을 생성한 뒤, pipeline register를 따라 필요한 stage까지 전달한다는 점이다.

                    ID에서 생성
                        │
           ┌────────────┼────────────────────────────────┐
           │            │                                │
           ▼            ▼                                ▼
        ┌──────┐    ┌──────────┐    ┌──────────┐    ┌──────────┐
        │ ID/EX│    │  EX/MEM  │    │  MEM/WB  │    │          │
        ├──────┤    ├──────────┤    ├──────────┤    │          │
  EX:   │ALUOp │    │          │    │          │    │          │
        │ALUSrc│──▶ │          │    │          │    │          │
        │RegDst│    │          │    │          │    │          │
        ├──────┤    ├──────────┤    │          │    │          │
  MEM:  │MemRd │    │ MemRead  │    │          │    │          │
        │MemWr │──▶ │ MemWrite │    │          │    │          │
        │Branch│    │ Branch   │    │          │    │          │
        ├──────┤    ├──────────┤    ├──────────┤    │          │
  WB:   │RegWr │    │ RegWrite │    │ RegWrite │    │          │
        │Mem2R │──▶ │ MemtoReg │──▶ │ MemtoReg │    │          │
        └──────┘    └──────────┘    └──────────┘    └──────────┘
         ID/EX        EX/MEM         MEM/WB

각 pipeline register가 전달하는 control signal:

ID/EX: ALUOp(2-bit), ALUSrc, RegDst — EX stage에서 사용
EX/MEM: MemRead, MemWrite, Branch — MEM stage에서 사용
MEM/WB: RegWrite, MemtoReg — WB stage에서 사용

추가로 Jump 관련 control signal도 있다:

Jump (0/1): PC를 Jump target으로 업데이트할지 결정
IF/ID를 noop으로 업데이트할지 결정

파이프라인 해저드

파이프라인은 이상적으로 매 사이클마다 하나의 명령어를 완료(CPI = 1)하지만, 현실에서는 **해저드(Hazard)**가 발생하여 파이프라인이 멈추거나 잘못된 결과를 낼 수 있다. 해저드는 세 가지 유형이 있다:

Structural Hazard: 2개의 stage가 같은 resource를 사용하려고 함
Data Hazard: 아직 준비되지 않은(unready) data를 사용하려고 함
Control Hazard: 분기 조건이나 새로운 PC 주소가 아직 계산되지 않음

Structural Hazard

두 개의 stage가 같은 하드웨어 자원을 동시에 사용하려 할 때 발생한다.

해결책: Duplicate Resource 또는 Stall (waiting = bubble)

Register 충돌: ID (read) & WB (write)

ID stage에서 레지스터를 읽고, 동시에 WB stage에서 같은 레지스터에 쓰는 경우:

Time →     CC1    CC2    CC3    CC4    CC5
         ┌──────┬──────┬──────┬──────┬──────┐
Instr i  │  IF  │  ID  │  EX  │ MEM  │  WB  │  ← Write Register
         └──────┴──────┴──────┴──────┴──────┘
                              ┌──────┬──────┬──────┬──────┬──────┐
Instr i+3                     │  IF  │  ID  │  EX  │ MEM  │  WB  │
                              └──────┴──────┴──────┴──────┘──────┘
                                       ↑
                                  Read Register (같은 CC5에서!)

해결: Half Cycle 기법

클럭의 전반부(First Half): Write 수행
클럭의 후반부(Last Half): Read 수행
Register access가 빠르기 때문에 한 사이클을 반으로 나눠도 충분하다

Memory 충돌: IF & MEM

IF stage에서 명령어를 읽고, 동시에 MEM stage에서 데이터 메모리에 접근하는 경우:

         ┌──────┬──────┬──────┬──────┬──────┐
Instr i  │  IF  │  ID  │  EX  │ MEM  │  WB  │  ← Data Memory 접근
         └──────┴──────┴──────┴──────┴──────┘
                              ┌──────┐
Instr i+3                     │  IF  │  ← Instruction Memory 접근
                              └──────┘
                                 ↑
                          같은 Memory를 동시 접근?

해결: Duplicate Memory

Instruction Memory와 Data Memory를 분리한다
실제로는 Instruction Cache와 Data Cache를 사용한다 (진짜 물리적으로 duplicate된 것은 아님)
메모리 접근은 느리기 때문에 Register처럼 Half Cycle로는 해결할 수 없다

Data Hazard

이전 명령어의 결과가 아직 준비되지 않았는데, 다음 명령어가 그 값을 사용하려 할 때 발생한다. 가장 빈번하고 복잡한 해저드이다.

add $s0, $t0, $t1      # $s0에 결과 기록 (WB에서 완료)
sub $t2, $s0, $t3      # $s0 값 필요 (ID에서 읽음) ← 아직 준비 안 됨!

Result와 Need 시점

각 명령어 유형별로 결과가 생성되는 시점(Result)과 값이 필요한 시점(Need)이 다르다:

명령어	Result 시점	Need 시점
R-type (`add $r3, $r1, $r2`)	EX 끝날 때 (ALU 계산 완료)	EX 시작할 때 (ALU 입력 필요)
Load (`lw $r1, 12($r2)`)	MEM 끝날 때 (Memory에서 값 로드)	EX 시작할 때 (주소 계산 필요)
Store (`sw $r1, 12($r2)`)	—	EX 시작할 때 (주소), MEM 시작할 때 (저장할 값)
Branch (`beq $r1, $r2, lab1`)	ID 끝날 때 (분기 여부 & target)	ID 시작할 때 (비교할 값 필요)
Jump	ID 끝날 때 (jump target)	—
Fetch	—	IF 시작할 때 (올바른 PC 값 필요)

Data Forwarding (Bypassing)

Data Hazard의 주요 해결책은 **Data Forwarding(= Bypassing)**이다. Pipeline register에 이미 존재하는 result data를 다음 명령어의 Functional Unit에게 직접 전달(forwarding)하여 해결한다.

           CC1    CC2    CC3    CC4    CC5    CC6
         ┌──────┬──────┬──────┬──────┬──────┐
add $s0  │  IF  │  ID  │  EX  │ MEM  │  WB  │
         └──────┴──────┴──┬───┴──────┴──────┘
                          │ Forward!
                          ▼
                ┌──────┬──────┬──────┬──────┬──────┐
sub $t2,$s0     │  IF  │  ID  │  EX  │ MEM  │  WB  │
                └──────┴──────┴──────┴──────┴──────┘

R-type의 경우, result는 EX 끝에 나오고 다음 명령어의 need는 EX 시작이므로, EX/MEM pipeline register에서 ALU 입력으로 직접 forwarding할 수 있다.

EX Forward Unit

EX Forward Unit은 바로 다음 명령어(1 cycle 뒤)와의 data dependency를 해결한다. EX/MEM pipeline register의 결과를 현재 EX stage의 ALU 입력으로 forwarding한다.

ForwardA (Rs 소스에 대한 forwarding):

if (EX/MEM.RegWrite
    and EX/MEM.RegisterRd != 0
    and EX/MEM.RegisterRd == ID/EX.RegisterRs)
    ForwardA = 10    // EX/MEM에서 forward

ForwardB (Rt 소스에 대한 forwarding):

if (EX/MEM.RegWrite
    and EX/MEM.RegisterRd != 0
    and EX/MEM.RegisterRd == ID/EX.RegisterRt)
    ForwardB = 10    // EX/MEM에서 forward

MEM Forward Unit

MEM Forward Unit은 2 cycle 뒤의 명령어와의 data dependency를 해결한다. MEM/WB pipeline register의 결과를 forwarding한다.

ForwardA:

if (MEM/WB.RegWrite
    and MEM/WB.RegisterRd != 0
    and EX/MEM.RegisterRd != ID/EX.RegisterRs   // EX forward 우선!
    and MEM/WB.RegisterRd == ID/EX.RegisterRs)
    ForwardA = 01    // MEM/WB에서 forward

ForwardB:

if (MEM/WB.RegWrite
    and MEM/WB.RegisterRd != 0
    and EX/MEM.RegisterRd != ID/EX.RegisterRt   // EX forward 우선!
    and MEM/WB.RegisterRd == ID/EX.RegisterRt)
    ForwardB = 01    // MEM/WB에서 forward

주의: EX Forward와 MEM Forward가 동시에 해당되는 경우, EX Forward(더 최신 값)가 우선한다. 이를 위해 MEM Forward 조건에 EX/MEM.RegisterRd != ID/EX.RegisterRs 조건이 추가된다.

Forwarding 경로를 MUX로 선택하는 구조:

ForwardA/B 값:
  00 = ID/EX register (forwarding 없음, 정상 경로)
  10 = EX/MEM register에서 forward (1 cycle 전 결과)
  01 = MEM/WB register에서 forward (2 cycle 전 결과)

                    ForwardA
                      │
              ┌───────┴───────┐
              │   3-to-1 MUX  │
              ├───────────────┤
         00 → │ ID/EX.ReadData1│
         10 → │ EX/MEM.ALUResult│
         01 → │ MEM/WB.ReadData │
              └───────┬───────┘
                      │
                      ▼
                   ALU input A

Load-Use Hazard

Forwarding으로도 해결할 수 없는 경우가 있다. Load 명령어 직후에 그 결과를 사용하는 경우이다.

lw  $s0, 0($t0)     # Result: MEM 끝날 때
add $t2, $s0, $t3   # Need: EX 시작할 때 ← 1 cycle 부족!

           CC1    CC2    CC3    CC4    CC5    CC6
         ┌──────┬──────┬──────┬──────┬──────┐
lw $s0   │  IF  │  ID  │  EX  │ MEM  │  WB  │
         └──────┴──────┴──────┴──┬───┴──────┘
                                 │ Result here (MEM 끝)
                                 │
                ┌──────┬──────┬──────┬──────┬──────┐
add $t2,$s0     │  IF  │  ID  │  EX  │ MEM  │  WB  │
                └──────┴──────┴──────┴──────┴──────┘
                               ↑
                          Need here (EX 시작)
                          시간적으로 앞서 있어 forward 불가!

Load의 결과는 MEM stage가 끝나야 나오는데, 다음 명령어는 EX stage 시작에 값이 필요하다. 시간을 거슬러 갈 수는 없으므로 forwarding만으로는 불가능하다.

Hazard Detection Unit

이 상황을 감지하기 위해 Load-Use Hazard Detection Unit이 ID stage에 존재한다:

if (ID/EX.MemRead
    and (ID/EX.RegisterRt == IF/ID.RegisterRs
     or  ID/EX.RegisterRt == IF/ID.RegisterRt))
    stall the pipeline

조건 해석:

ID/EX.MemRead: 현재 EX stage에 있는 명령어가 load인가?
ID/EX.RegisterRt: load의 목적지 레지스터 (= $rt)
IF/ID.RegisterRs/Rt: 다음 명령어의 소스 레지스터

조건이 참이면, 파이프라인을 1 cycle stall한다:

           CC1    CC2    CC3    CC4    CC5    CC6    CC7
         ┌──────┬──────┬──────┬──────┬──────┐
lw $s0   │  IF  │  ID  │  EX  │ MEM  │  WB  │
         └──────┴──────┴──────┴──┬───┴──────┘
                                 │ Forward (이제 가능!)
                                 ▼
                ┌──────┬──────┬─STALL┬──────┬──────┬──────┐
add $t2,$s0     │  IF  │  ID  │bubble│  EX  │ MEM  │  WB  │
                └──────┴──────┴──────┴──────┴──────┴──────┘

Stall 구현 방법:

ID/EX pipeline register의 control signal을 모두 0으로 설정 (= bubble/nop 삽입)
IF/ID register와 PC를 freeze (같은 값 유지 → 다음 cycle에 다시 실행)

1 cycle stall 후에는 MEM/WB에서 EX로의 forwarding이 가능해진다.

Control Hazard

분기 명령어(branch)에서 조건 결과나 새로운 PC 주소가 아직 결정되지 않았을 때 발생한다. 분기 결과를 알기 전에 다음 명령어를 이미 fetch하고 있기 때문이다.

           CC1    CC2    CC3    CC4    CC5
         ┌──────┬──────┬──────┬──────┬──────┐
beq ...  │  IF  │  ID  │  EX  │ MEM  │  WB  │
         └──────┴──────┴──────┴──────┴──────┘
                ┌──────┐
next instr      │  IF  │  ← 분기 결과 모르는데 이미 fetch!
                └──────┘

Branch Prediction

매번 분기 결과를 기다리면 파이프라인이 자주 멈추므로, **분기 예측(Branch Prediction)**을 사용한다.

정적 예측(Static Prediction):

Predict Not Taken: 항상 “분기하지 않는다"고 예측 → 다음 sequential instruction을 계속 fetch
Predict Taken: 항상 “분기한다"고 예측

동적 예측(Dynamic Prediction):

과거 분기 이력을 기반으로 예측 (Branch History Table 등)
정확도가 높을수록 성능 향상

Flush

예측이 틀렸을 때는 이미 파이프라인에 들어온 잘못된 명령어들을 **flush(제거)**해야 한다. 해당 pipeline register의 control signal을 0으로 설정하여 **bubble(nop)**로 바꾼다.

           CC1    CC2    CC3    CC4    CC5    CC6    CC7
         ┌──────┬──────┬──────┬──────┬──────┐
beq taken│  IF  │  ID  │  EX  │ MEM  │  WB  │
         └──────┴──┬───┴──────┴──────┴──────┘
                   │ 예측 실패 감지! → Flush
                   ▼
                ┌──────┐
wrong instr     │  IF  │ ──▶ bubble (flush)
                └──────┘
                       ┌──────┬──────┬──────┬──────┬──────┐
correct instr          │  IF  │  ID  │  EX  │ MEM  │  WB  │
                       └──────┴──────┴──────┴──────┴──────┘

Branch의 결과를 더 일찍 결정할수록 flush되는 명령어 수가 줄어든다. MIPS에서는 ID stage에서 branch를 결정하도록 설계하여, 예측 실패 시 1 cycle만 낭비하도록 한다 (비교 연산 회로를 ID에 추가).

해저드 해결책 요약

┌─────────────────────┬─────────────────────────────────────┐
│     Hazard Type     │           Solution                  │
├─────────────────────┼─────────────────────────────────────┤
│ Structural Hazard   │ - Duplicate Resource                │
│ (자원 충돌)          │   (Instr Mem / Data Mem 분리)       │
│                     │ - Half Cycle (Register R/W)         │
│                     │ - Stall                             │
├─────────────────────┼─────────────────────────────────────┤
│ Data Hazard         │ - Data Forwarding (Bypassing)       │
│ (데이터 의존성)      │   : EX Forward (1-cycle gap)        │
│                     │   : MEM Forward (2-cycle gap)       │
│                     │ - Stall (Load-Use Hazard)           │
│                     │   : Hazard Detection Unit           │
├─────────────────────┼─────────────────────────────────────┤
│ Control Hazard      │ - Branch Prediction                 │
│ (분기 미결정)        │   : Static / Dynamic                │
│                     │ - Flush (예측 실패 시 bubble)        │
│                     │ - Early Branch Resolution (ID에서)   │
└─────────────────────┴─────────────────────────────────────┘

정리

파이프라인은 명령어 실행을 여러 stage로 나누어 throughput을 향상시키는 기법이다
MIPS의 5단계 파이프라인: IF → ID → EX → MEM → WB
Pipeline register(latch)가 각 stage를 격리하며, control signal은 ID에서 생성되어 전파된다
Structural Hazard: 자원 충돌 → Duplicate Resource, Half Cycle
Data Hazard: 데이터 의존성 → Forwarding (EX/MEM forward), Stall (Load-Use)
Control Hazard: 분기 미결정 → Branch Prediction, Flush
Forwarding Unit과 Hazard Detection Unit은 하드웨어로 구현되어 자동으로 동작한다
이상적인 파이프라인의 CPI는 1이지만, 해저드로 인한 stall이 CPI를 증가시킨다

파이프라인 설계#

Instruction Critical Path#

Single Cycle Design의 한계#

5-Stage Pipeline#

SC vs Pipeline 비교#

MIPS가 Pipelining에 유리한 이유#

Pipeline Registers#

Control Signals#

파이프라인 해저드#

Structural Hazard#

Register 충돌: ID (read) & WB (write)#

Memory 충돌: IF & MEM#

Data Hazard#

Result와 Need 시점#

Data Forwarding (Bypassing)#

EX Forward Unit#

MEM Forward Unit#

Load-Use Hazard#

Hazard Detection Unit#

Control Hazard#

Branch Prediction#

Flush#

해저드 해결책 요약#

정리#