Pipeline & Hazard Resolution

1. Overview

파이프라인과 해저드 해결(Pipeline & Hazard Resolution, PHR)은 한 번에 하나씩 처리하던 단일 사이클 CPU의 한계를 줄이기 위해, 명령어 실행 단계를 컨베이어 벨트처럼 나누어 클럭마다 여러 명령어를 겹쳐 처리하는 기계적 병렬성의 기초입니다.

학습자는 명령어 실행 단계를 Fetch, Decode, Execute, Memory, Write-back의 5단계로 나누어 동시에 여러 명령어를 겹쳐 돌리는 **파이프라인(Pipeline)**의 시간차 구조를 분석합니다. 이어 컨베이어 벨트 위에서 명령어가 서로 충돌하고 데이터가 꼬이는 **구조적, 데이터, 제어 해저드(Hazards)**를 살펴보고, 멈춤(Stall), 전방 전달(Forwarding), 분기 예측(Branch Prediction)이라는 하드웨어 우회 기법으로 IPC(Instruction Per Clock)를 높이는 방법을 익힙니다.

2. Scope & Boundaries

In-Scope

• 파이프라인 역학 (Pipeline Physics): 5단 파이프라인(IF, ID, EX, MEM, WB), 파이프라인 레지스터(Pipeline Registers), 처리량(Throughput)과 지연(Latency).
• 구조적 해저드 (Structural Hazard): 하드웨어 자원 충돌(예: 메모리 포트 부족)과 캐시 분리(I-Cache, D-Cache).
• 데이터 해저드 (Data Hazard): RAW(Read After Write) 의존성 파괴, 포워딩/바이패싱(Forwarding/Bypassing), 파이프라인 스톨(Pipeline Stall/Bubble), NOP 삽입.
• 제어 해저드 (Control Hazard): 조건 분기(Branch)에 의한 파이프라인 붕괴(Flush), 분기 지연 슬롯(Branch Delay Slot).

Out-of-Scope

• 비순차 실행 (Out-of-Order Execution): 명령어 순서를 동적으로 재배치하는 토마술로(Tomasulo) 알고리즘 $\rightarrow$ 02-03-03. Out-of-Order Execution 영역.
• 소프트웨어 스레드 스케줄링: 운영체제가 여러 프로세스를 시분할로 돌리는 컨텍스트 스위칭 $\rightarrow$ 03-02-01. Thread & Context Switching 영역.

Boundaries

• PHR vs. Single-Cycle Datapath (02-01-03): 단일 사이클(02-01-03)은 하나의 명령어가 시작부터 끝까지 1클럭 안에 하드웨어 전체를 사용하는 구조입니다. PHR은 같은 하드웨어를 여러 단계로 나누고 단계 사이에 파이프라인 레지스터를 두어, 여러 명령어가 서로 다른 단계를 동시에 사용하게 만드는 처리량 최적화 기술입니다.

3. Counterexample

• 클럭 분할 환상 (Perfect Speedup Fallacy): "명령어를 5단계로 나누면 클럭 속도도 무조건 5배 빨라진다"는 오해입니다. 파이프라인의 전체 클럭 주기는 5단계 중 **가장 느린 단계(보통 메모리 접근)**에 맞춰져야 하므로 완벽한 5배가 될 수 없으며, 중간에 파이프라인 레지스터가 추가되면서 셋업/홀드 타임 오버헤드가 발생해 개별 명령어의 레이턴시(Latency)는 오히려 단일 사이클보다 길어질 수 있습니다.
• 데이터 의존성 무시 (RAW Hazard Ignore): 어셈블리어에서 add x1, x2, x3 바로 다음 줄에 sub x4, x1, x5를 두고, 아래 명령어가 곧바로 위 명령어의 결과를 읽는다고 가정하는 오해입니다. 파이프라인에서는 아래 명령어의 Decode 단계가 위 명령어의 Write-back 단계보다 먼저 올 수 있으므로, 하드웨어 포워딩(Forwarding) 회로가 없으면 아래 명령어는 아직 갱신되지 않은 오래된(Stale) x1 값을 읽게 됩니다.

4. Prerequisites

• 단일 사이클 데이터 경로 (Basic): IF, ID, EX, MEM, WB가 무엇을 하는 부품인지 단일 사이클에서 미리 배워야, 그 부품들 사이에 파이프라인 레지스터를 배치하는 이유를 이해할 수 있습니다. (02-01-03 ADP)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 파이프라인 단계 분할 역학 (Pipeline Anatomy)

• Why to Learn: 1,000피코초(ps)짜리 명령어를 1클럭으로 묶으면 1GHz가 한계지만, 이를 여러 단계로 나누면 더 짧은 클럭 주기로 처리량을 높일 수 있습니다. 파이프라인은 이 단계 분할의 이득과 비용을 함께 이해해야 제대로 설계할 수 있습니다.
• What to Learn:
  • Concepts: 스루풋(Throughput, 처리량), 레이턴시(Latency, 응답 시간), 인스트럭션 레벨 병렬성(ILP).
  • Skills: IF, ID, EX, MEM, WB 파이프라인 분할, 파이프라인 레지스터(IF/ID, ID/EX, EX/MEM, MEM/WB).
  • Tools: 시간축 파이프라인 다이어그램.
  • Trade-offs: 단계를 잘게 나눌수록 클럭 주기를 줄일 수 있지만, 파이프라인이 한 번 깨졌을 때(Flush) 다시 채우는 복구 페널티도 커집니다. 펜티엄4의 깊은 파이프라인은 이 균형이 얼마나 중요한지 보여주는 사례입니다.
• How to Learn:
  • 1단계: 세탁(30분), 건조(30분), 개기(30분)라는 프로세스가 있을 때, 빨래 4바구니를 한 번에 한 바구니씩 끝내는 방식과 단계별로 겹쳐 처리하는 방식을 비교해 파이프라인의 처리량 이득을 계산합니다.
  • 2단계: 각 단계 사이에 파이프라인 레지스터를 두고, 클럭마다 데이터와 제어 신호가 앞 단계에서 뒷 단계로 넘어가는 하드웨어 구조를 살펴봅니다.
• Implement: 명령어 리스트를 입력받아 파이프라인 사이클(Clock) 다이어그램 텍스트를 출력하는 스크립트 작성. Inst1: IF ID EX MEM WB, Inst2: IF ID EX MEM WB 식으로 중첩되는 사이클마다 CPU 부품의 사용 현황을 시각화.

Recommended

Core Topic 02: 데이터 해저드와 단계 충돌 (Data Hazards & RAW)

• Why to Learn: 코드가 순서대로 작성되어 있어도, 파이프라인에서는 앞 명령어의 결과가 아직 나오기 전에 뒷 명령어가 그 결과를 필요로 할 수 있습니다. 데이터 해저드는 이 시점 차이를 다루는 핵심 문제입니다.
• What to Learn:
  • Concepts: 데이터 해저드(Data Hazard), RAW(Read After Write), WAR, WAW.
  • Skills: 의존성(Dependency) 추적, 파이프라인 버블(Bubble / NOP) 삽입.
  • Tools: 의존성 그래프(Dependency Graph).
  • Trade-offs: 컴파일러가 의존성을 발견할 때마다 빈 명령어(NOP)를 넣어 파이프라인을 멈추게(Stall) 하면 안전하지만, IPC가 크게 떨어집니다.
• How to Learn:
  • 1단계: add x1, x2, x3 (x1을 WB 단계에서 5사이클째에 씀) 바로 뒤에 sub x4, x1, x5 (x1을 ID 단계에서 3사이클째에 읽음)가 올 때, 결과가 준비되기 전에 읽기가 시도되는 시점 차이를 계산합니다.
  • 2단계: 이를 해결하기 위해 하드웨어가 2사이클 동안 뒷 명령어를 멈춰(Stall) 파이프라인에 버블(Bubble)을 넣는 지연 현상을 확인합니다.
• Implement: 입력된 2개의 어셈블리 명령어 리스트에서 정규표현식으로 레지스터(Target, Source)를 파싱하고, 이전 명령어의 Target을 다음 명령어의 Source로 쓰고 있는지 검사하여 "RAW Hazard Detected! Need 2 Stalls" 경고를 뱉는 의존성 검사기 작성.

Practical

Core Topic 03: 포워딩과 하드웨어 지름길 개척 (Forwarding & Bypassing)

• Why to Learn: 데이터 해저드 때문에 파이프라인이 자주 멈추면 처리량이 떨어집니다. 포워딩은 ALU 연산이 끝난 값을 레지스터에 쓰기 전, 뒷 명령어의 ALU 입력으로 직접 보내 스톨을 줄이는 하드웨어 우회 경로입니다.
• What to Learn:
  • Concepts: 전방 전달(Forwarding / Bypassing).
  • Skills: 포워딩 유닛(Forwarding Unit) 로직 설계, EX/MEM 레지스터 탭, MEM/WB 레지스터 탭.
  • Tools: 멀티플렉서(MUX) 라우팅 회로.
  • Trade-offs: 레지스터 파일(WB)까지 기다리지 않아 스톨을 줄이는 이득 vs 포워딩 선, ALU 입력 MUX, 비교기 추가로 하드웨어 면적과 타이밍 부담이 커지는 비용.
• How to Learn:
  • 1단계: add x1...의 ALU 계산이 3사이클(EX) 끝에서 완료되었을 때, 이 값을 5사이클(WB)까지 기다리지 않고 뒤따라오는 sub의 4사이클(EX) 시작점 MUX로 전달하는 경로를 추적합니다.
  • 2단계: 포워딩으로도 해결하기 어려운 lw(메모리 읽기) 직후의 데이터 의존성(Load-Use Data Hazard)에서는, 메모리 데이터가 나오는 4사이클(MEM) 끝부분 때문에 1사이클 스톨(Stall)이 필요함을 확인합니다.
• Implement: 파이프라인 시뮬레이터를 확장하여, 현재 EX 단계에 진입한 명령어의 Source 레지스터가 MEM 단계나 WB 단계에 있는 앞 명령어의 Target 레지스터와 일치할 경우, 자동으로 포워딩 선을 연결(MUX=1)하여 Stall 없이 연산을 속행하는 로직 구현.

Advanced

Core Topic 04: 제어 해저드와 파이프라인 플러시 (Control Hazards & Branching)

• Why to Learn: if문이나 for문 같은 분기(Branch)를 만났을 때, CPU가 점프할지 말지 결정(EX 단계)하기 전에 뒤따라 들어온 명령어들이 무효화(Flush)될 수 있습니다. 제어 해저드는 이 비용을 줄이기 위해 다룹니다.
• What to Learn:
  • Concepts: 제어 해저드(Control Hazard), 플러시(Flush).
  • Skills: 분기 지연 슬롯(Branch Delay Slot), 정적 분기 예측(Static Branch Prediction).
  • Tools: 제어 유닛(Control Unit) 킬 스위치(Kill Switch).
  • Trade-offs: "점프할지 말지 모를 땐 안 한다고 가정한다(Assume Not Taken)"는 정적 예측이 틀렸을 때 파이프라인을 비우는 페널티(3~4사이클 손실) vs 하드웨어 비교기를 ID(디코드) 단계로 앞당겨 판단을 일찍 내려 플러시 페널티를 1사이클로 줄이는 클럭 타이밍 타협.
• How to Learn:
  • 1단계: 분기 명령어 뒤에 3개의 명령어가 파이프라인에 들어왔는데, 분기가 "Taken"으로 결정되었을 때 이미 들어온 명령어의 제어 신호를 0(NOP)으로 바꾸는 플러시 메커니즘을 분석합니다.
  • 2단계: 컴파일러가 분기 명령어 바로 뒷칸(Delay Slot)에 반드시 실행해도 되는 명령어(예: 변수 초기화)를 배치해, 플러시 비용을 줄이는 MIPS의 방식을 살펴봅니다.
• Implement: 브랜치 명령어가 들어왔을 때 PC(Program Counter)가 어떻게 갱신되는지 모사하고, 예측이 틀렸을 때(Misprediction) 현재 파이프라인 큐에 들어있는 뒤따른 명령어 객체들의 valid_bit를 False로 날려버려 NOP화(Flush)시키는 제어 해저드 핸들러 모듈 작성.

7. Terminology

8. References

Primary

• [P1] CS2023 - AR/Pipelining and Instruction-Level Parallelism — Core requirements.
• [P2] SWEBOK v4.0 - Computing Foundations / Pipeline — Hardware standards.

Secondary

• [Computer Organization and Design] Patterson & Hennessy — Detailed pipeline datapath charts.
• [Digital Design and Computer Architecture] Harris & Harris — Integrated view of logic/hazards.

Industry

• [ARM Cortex-R Series: Real-time Processor Pipeline] — Deterministic hazard handling.
• [MIPS Instruction Set Architecture - Pipeline Implementation] — Classic study case.

9. Final Checklist

Primary

• 5단 파이프라인 구조에서 데이터 종속성(Data dependency)이 있는 두 명령어 사이에 왜 최소 2클록의 시차가 필요한지 물리적으로 설명할 수 있는가? (P1)
• '포워딩(Forwarding)' 로직을 설계할 때, ALU의 입력 선택용 멀티플렉서(MUX)를 제어하는 감지 조건을 수식으로 기술할 수 있는가? (P1)

Secondary

• 파이프라인 스테이지가 5단에서 20단으로 늘어날 때, 'Branch Penalty'가 전체 성능에 미치는 물리적 영향력의 변화를 소통 가능한가?
• 메모리 접근 명령(Load) 직후에 해당 데이터를 쓰는 명령이 올 때, 포워딩만으로는 해결할 수 없어 'Stall'이 반드시 발생하는 수리적 근거를 입증할 수 있는가?

Industry

• 임베디드 시스템 설계 시, 에너지 효율을 위해 파이프라인 단수를 줄이는 대신 클록을 낮추는 전략의 물리적 타당성을 제안할 수 있는가? (SFIA)
• 실시간 OS(RTOS) 환경에서 파이프라인 해저드로 인한 지연 시간 변동성(Jitter)을 분석하고 최악의 시나리오를 물리적으로 확정할 수 있는가?