파이프라이닝 (Pipelining)
파이프라이닝 (Pipelining)¶
개요¶
파이프라이닝은 여러 명령어를 동시에 실행하여 CPU 처리량을 높이는 기술입니다. 세탁기-건조기 비유처럼, 하나의 작업이 끝나기 전에 다음 작업을 시작하여 전체 효율을 높입니다.
목차¶
1. 파이프라이닝 개념¶
기본 아이디어¶
비파이프라인 (순차 실행):
┌─────┐ ┌─────┐ ┌─────┐
│ I1 │────▶│ I2 │────▶│ I3 │
└─────┘ └─────┘ └─────┘
5ns 5ns 5ns 총 15ns
파이프라인 (병렬 실행):
시간: 1ns 2ns 3ns 4ns 5ns 6ns 7ns
I1: [IF]─[ID]─[EX]─[MEM]─[WB]
I2: [IF]─[ID]─[EX]─[MEM]─[WB]
I3: [IF]─[ID]─[EX]─[MEM]─[WB]
총 7ns
세탁기 비유¶
비파이프라인:
세탁1 ──▶ 건조1 ──▶ 세탁2 ──▶ 건조2 ──▶ 세탁3 ──▶ 건조3
파이프라인:
시간: 1 2 3 4 5 6
세탁1 ■
건조1 ■
세탁2 ■
건조2 ■
세탁3 ■
건조3 ■
3배 빨라짐!
2. 5단계 파이프라인¶
MIPS 5단계 파이프라인¶
┌────────────────────────────────────────────────────────────┐
│ 5-Stage Pipeline │
├───────┬───────┬───────┬───────┬───────┐ │
│ IF │ ID │ EX │ MEM │ WB │ │
│(Fetch)│(Decode│(Exec) │(Memory│(Write │ │
│ │ │ │Access)│ Back) │ │
└───────┴───────┴───────┴───────┴───────┘ │
└────────────────────────────────────────────────────────────┘
각 단계 설명¶
| 단계 | 이름 | 동작 |
|---|---|---|
| IF | Instruction Fetch | PC가 가리키는 명령어를 메모리에서 가져옴 |
| ID | Instruction Decode | 명령어 해독, 레지스터 읽기 |
| EX | Execute | ALU 연산 수행, 주소 계산 |
| MEM | Memory Access | 메모리 읽기/쓰기 (load/store) |
| WB | Write Back | 연산 결과를 레지스터에 저장 |
파이프라인 레지스터¶
┌─────┐ ┌─────────┐ ┌─────────┐ ┌──────────┐ ┌─────────┐
│ IF │──▶│ IF/ID │──▶│ ID/EX │──▶│ EX/MEM │──▶│ MEM/WB │
└─────┘ │Register │ │Register │ │Register │ │Register │
└─────────┘ └─────────┘ └──────────┘ └─────────┘
파이프라인 레지스터: 각 단계 사이의 데이터를 임시 저장
- 클럭마다 데이터가 다음 단계로 전달
명령어별 파이프라인 사용¶
명령어 유형별 단계 사용:
R-type (add, sub):
IF ─▶ ID ─▶ EX ─▶ --- ─▶ WB
Load (lw):
IF ─▶ ID ─▶ EX ─▶ MEM ─▶ WB
Store (sw):
IF ─▶ ID ─▶ EX ─▶ MEM ─▶ ---
Branch (beq):
IF ─▶ ID ─▶ EX ─▶ --- ─▶ ---
3. 파이프라인 성능¶
이상적인 속도 향상¶
속도 향상 = 파이프라인 단계 수 (이상적)
5단계 파이프라인 → 최대 5배 속도 향상
실제로는:
- 파이프라인 채우기/비우기 시간
- 해저드로 인한 스톨
- 단계 간 불균형
처리량 계산¶
처리량 (Throughput) = 명령어 수 / 시간
비파이프라인:
- 1 명령어 / 5 사이클
파이프라인 (이상적):
- 1 명령어 / 1 사이클 (풀 파이프라인 상태)
CPI (Cycles Per Instruction):
- 이상적: CPI = 1
- 실제: CPI = 1 + 스톨 사이클
예제: 100개 명령어 실행¶
비파이프라인:
시간 = 100 × 5 = 500 사이클
5단계 파이프라인:
시간 = 5 + (100 - 1) = 104 사이클
↑첫 명령어 ↑나머지 명령어
속도 향상 = 500 / 104 ≈ 4.8배
4. 파이프라인 해저드¶
해저드 유형¶
┌─────────────────────────────────────────────────────────┐
│ 파이프라인 해저드 │
├─────────────────┬─────────────────┬─────────────────────┤
│ 구조적 해저드 │ 데이터 해저드 │ 제어 해저드 │
│ (Structural) │ (Data) │ (Control) │
├─────────────────┼─────────────────┼─────────────────────┤
│ 하드웨어 자원 │ 데이터 의존성 │ 분기 명령어로 │
│ 충돌 │ 으로 인한 문제 │ 인한 문제 │
└─────────────────┴─────────────────┴─────────────────────┘
4.1 구조적 해저드¶
문제: 같은 하드웨어 자원을 동시에 사용하려 함
예: 단일 메모리 사용 시
사이클 4:
- 명령어 1: MEM 단계 (데이터 메모리 접근)
- 명령어 4: IF 단계 (명령어 메모리 접근)
I1: IF─ID─EX─MEM─WB
I4: IF ← 충돌!
해결: 하버드 구조 (명령어/데이터 메모리 분리)
4.2 데이터 해저드¶
세 가지 유형:
1. RAW (Read After Write) - 가장 흔함
add $s0, $t0, $t1 # $s0에 쓰기
sub $t2, $s0, $t3 # $s0 읽기 ← 아직 안 써짐!
2. WAR (Write After Read)
sub $t2, $s0, $t3 # $s0 읽기
add $s0, $t0, $t1 # $s0에 쓰기
3. WAW (Write After Write)
add $s0, $t0, $t1 # $s0에 쓰기
sub $s0, $t2, $t3 # $s0에 쓰기
RAW 해저드 예시¶
add $s0, $t0, $t1
sub $t2, $s0, $t3
시간: 1 2 3 4 5 6 7
add: IF ID EX MEM [WB] ← $s0 기록
sub: IF ID [EX] ← $s0 필요!
↑
문제 발생!
$s0는 사이클 5에 기록되는데,
sub는 사이클 4에 $s0가 필요함
4.3 제어 해저드¶
beq $t0, $t1, target # 분기 여부 결정
add $t2, $t3, $t4 # 실행해야 하나?
sub $t5, $t6, $t7 # 실행해야 하나?
시간: 1 2 3 4 5
beq: IF ID [EX] ← 분기 결정
add: IF ID ← 잘못된 명령어?
sub: IF ← 잘못된 명령어?
분기 결정 전에 이미 다음 명령어들이 파이프라인에 진입
5. 해저드 해결 기법¶
5.1 스톨링 (Stalling)¶
버블(NOP) 삽입으로 파이프라인 일시 정지
add $s0, $t0, $t1
sub $t2, $s0, $t3
시간: 1 2 3 4 5 6 7 8 9
add: IF ID EX MEM WB
--- stall ---
--- stall ---
sub: IF ID EX MEM WB
2 사이클 스톨 발생 → 성능 저하
5.2 포워딩/바이패싱¶
ALU 결과를 바로 다음 명령어에 전달
add $s0, $t0, $t1
sub $t2, $s0, $t3
시간: 1 2 3 4 5 6
add: IF ID [EX] MEM WB
│
└─────▶ 포워딩
sub: IF ID [EX] MEM WB
↑
$s0 값 사용
스톨 없이 실행 가능!
포워딩 경로¶
┌─────────────────────────────────────────────────────────┐
│ 포워딩 유닛 │
│ │
│ EX/MEM.ALUResult ───────────────┐ │
│ ▼ │
│ MEM/WB.ALUResult ─────────────▶ MUX ──▶ ALU 입력 │
│ ▲ │
│ ID/EX.RegisterRs ───────────────┘ │
└─────────────────────────────────────────────────────────┘
포워딩 조건:
1. EX/MEM.RegisterRd == ID/EX.RegisterRs
2. MEM/WB.RegisterRd == ID/EX.RegisterRs
5.3 Load-Use 해저드¶
포워딩으로도 해결 불가능한 경우:
lw $s0, 0($t0) # 메모리에서 로드
add $t2, $s0, $t3 # 바로 사용
시간: 1 2 3 4 5 6 7
lw: IF ID EX [MEM] WB
│
└───▶ 데이터 사용 가능
add: IF ID stall [EX] MEM WB
↑
데이터 필요하지만 아직 없음
1 사이클 스톨 필수 (Load-Use Stall)
5.4 분기 예측¶
정적 예측:
- 항상 Not Taken: 분기 안 함으로 예측
- 항상 Taken: 분기 함으로 예측
- BTFN: 뒤로 가면 Taken, 앞으로 가면 Not Taken
동적 예측:
- 분기 기록을 기반으로 예측
- 다음 레슨에서 상세히 다룸
5.5 지연 분기 (Delayed Branch)¶
분기 명령어 다음 슬롯에 항상 실행되는 명령어 배치
beq $t0, $t1, target
add $t2, $t3, $t4 # 지연 슬롯 (항상 실행)
...
target:
sub $t5, $t6, $t7
컴파일러가 분기와 무관한 명령어를 지연 슬롯에 배치
6. 연습 문제¶
기초 문제¶
-
5단계 파이프라인의 각 단계 이름과 역할은?
-
100개 명령어를 5단계 파이프라인에서 실행할 때 필요한 사이클 수는? (해저드 없다고 가정)
-
다음 중 데이터 해저드의 유형이 아닌 것은?
- (a) RAW
- (b) RAR
- (c) WAR
- (d) WAW
해저드 분석¶
- 다음 코드에서 데이터 해저드를 찾으시오:
add $s0, $t0, $t1
sub $s1, $s0, $t2
and $s2, $s0, $s1
- 포워딩으로 해결할 수 없는 해저드는?
lw $s0, 0($t0)
add $t1, $s0, $t2
성능 계산¶
- 1000개 명령어 중 30%가 분기이고, 분기 예측 실패율이 20%이며, 실패 시 3 사이클 페널티가 있다면 CPI는?
정답
1. IF(인출), ID(해독), EX(실행), MEM(메모리접근), WB(쓰기) 2. 5 + (100 - 1) = 104 사이클 3. (b) RAR - Read After Read는 해저드가 아님 4. - add → sub: $s0에 대한 RAW - add → and: $s0에 대한 RAW - sub → and: $s1에 대한 RAW 5. Load-Use 해저드. lw의 MEM 단계 이후에야 데이터 사용 가능하므로 1 사이클 스톨 필요 6. - 분기 명령어 수: 1000 × 0.3 = 300 - 예측 실패: 300 × 0.2 = 60 - 페널티 사이클: 60 × 3 = 180 - CPI = 1 + 180/1000 = 1.18다음 단계¶
- 12_Branch_Prediction.md - 동적 분기 예측 기법
참고 자료¶
- Computer Organization and Design, Chapter 4 (Patterson & Hennessy)
- Pipeline Visualization
- MIPS Pipeline Simulator