컴퓨터공학 300 주제 시리즈의 090번째 글이다. 전체 지도는 여기.

한 줄 요약

파이프라이닝은 명령어 실행을 여러 단계로 나누고, 각 단계가 서로 다른 명령어를 동시에 처리하게 해서 처리량을 높이는 기법이다. 명령어 하나의 지연 시간은 줄지 않고 오히려 조금 늘지만, 단위 시간에 끝나는 명령어 수가 단계 수에 가깝게 늘어난다.

왜 필요한가

빨래를 생각해 보자. 세탁 30분, 건조 30분, 개기 30분. 네 바구니를 한 바구니씩 끝까지 하면 6시간이다. 첫 바구니가 건조기에 들어갈 때 둘째 바구니를 세탁기에 넣으면 3시간이면 된다. 한 바구니가 끝나는 데는 여전히 1시간 30분이 걸리지만, 그 뒤로는 30분마다 한 바구니씩 나온다.

CPU 도 같다. 앞 글의 단일 사이클 데이터패스(#089)는 명령어 하나가 끝날 때까지 다른 부품이 놀았다. 파이프라인은 그 노는 부품을 다음 명령어에게 빌려준다. 지난 수십 년간 CPU 성능 향상의 큰 축이 이 기법과 그 확장(슈퍼스칼라, 비순차 실행)이었다.

이 개념은 소프트웨어에도 그대로 나온다. 셸 파이프, 스트림 처리, CI 파이프라인, HTTP 요청 파이프라이닝 모두 “단계를 나눠 겹친다” 는 같은 아이디어다.

핵심 개념

고전적 5단계 파이프라인

단계 이름 하는 일
IF Instruction Fetch PC 로 명령어 메모리에서 명령어를 읽고 PC+4
ID Instruction Decode 해독, 레지스터 파일 읽기, 즉시값 생성
EX Execute ALU 연산, 주소 계산, 분기 비교
MEM Memory 데이터 메모리 읽기·쓰기
WB Write Back 결과를 레지스터 파일에 씀

단계 사이에는 파이프라인 레지스터가 들어간다. 앞 단계의 결과와 그 명령어에 필요한 제어 신호를 붙잡아 다음 사이클에 다음 단계로 넘긴다. 이 레지스터 덕분에 다섯 단계가 각자 다른 명령어를 들고 있을 수 있다.

타이밍 그림

사이클    1   2   3   4   5   6   7   8
I1       IF  ID  EX MEM  WB
I2           IF  ID  EX MEM  WB
I3               IF  ID  EX MEM  WB
I4                   IF  ID  EX MEM  WB

5사이클째에는 다섯 단계가 모두 바쁘다. 이 상태가 유지되면 매 사이클마다 명령어 하나가 끝난다.

지연 시간과 처리량

  • 지연 시간(latency): 명령어 하나가 들어가서 나오기까지의 시간. 파이프라인에서는 단계 수 × 클록 주기다.
  • 처리량(throughput): 단위 시간당 완료되는 명령어 수. 이상적인 파이프라인에서는 사이클당 1개다.

k 단계 파이프라인으로 n 개 명령어를 실행하면 걸리는 사이클은 다음과 같다.

파이프라인 없음:  n × k  (단계 시간 단위로 셈)
파이프라인:       k + (n − 1)
속도 향상:        n·k / (k + n − 1)  →  n 이 크면 k 에 수렴

이상과 현실

이론상 k 단계면 k 배 빨라진다. 실제로는 그렇지 않다.

  1. 단계 불균형: 클록 주기는 가장 느린 단계에 맞춰진다. 다섯 단계가 똑같이 200ps 가 아니라 하나가 300ps 면 전부 300ps 를 기다린다.
  2. 파이프라인 레지스터 오버헤드: 단계 사이 레지스터의 설정 시간과 지연이 사이클마다 붙는다.
  3. 채우기와 비우기: 시작할 때 k−1 사이클은 파이프라인이 덜 찼다.
  4. 해저드: 앞 명령어의 결과가 필요하거나(데이터), 분기 방향을 아직 모르거나(제어), 같은 부품을 동시에 쓰려 할 때(구조) 파이프라인이 멈추거나 비워진다. 다음 글(#091)의 주제다.

더 깊게, 더 넓게

  • 깊은 파이프라인: 단계를 더 잘게 쪼개면 단계당 시간이 줄어 클록을 올릴 수 있다. 대신 분기 예측이 틀렸을 때 버려지는 작업이 많아지고 레지스터 오버헤드 비중이 커진다. 무작정 깊게 만드는 것이 답이 아니라는 것은 업계가 이미 겪어 본 교훈이다.
  • 슈퍼스칼라: 파이프라인을 여러 줄 두어 사이클당 여러 명령어를 내보낸다.
  • 비순차 실행: 앞 명령어가 메모리를 기다리는 동안 의존성이 없는 뒤 명령어를 먼저 실행한다. 결과는 원래 순서대로 확정(retire)해서 프로그램 입장에서는 순서대로 실행된 것처럼 보이게 한다.

이 모두가 명령어 수준 병렬성(ILP)을 뽑아내는 기술이다.

직접 해 보기

타이밍 그림과 속도 향상 공식을 계산한다. python3 로 실행해 확인했다.

STAGES = ["IF", "ID", "EX", "MEM", "WB"]

def diagram(n, k=len(STAGES)):
    total = k + n - 1
    print("      " + " ".join(f"{c+1:>3}" for c in range(total)))
    for i in range(n):
        row = ["   "] * total
        for s in range(k):
            row[i + s] = f"{STAGES[s]:>3}"
        print(f"I{i+1:<4} " + " ".join(row))

diagram(4)

def speedup(n, k, stage_ps, latch_ps=0):
    single = n * (k * stage_ps)                  # 비파이프라인: 명령어당 k 단계 전부
    piped = (k + n - 1) * (stage_ps + latch_ps)  # 파이프라인: 채우는 시간 + 1/사이클
    return single / piped

for n in (1, 5, 100, 1_000_000):
    print(n, round(speedup(n, 5, 200), 3), round(speedup(n, 5, 200, latch_ps=20), 3))

출력:

        1   2   3   4   5   6   7   8
I1     IF  ID  EX MEM  WB
I2         IF  ID  EX MEM  WB
I3             IF  ID  EX MEM  WB
I4                 IF  ID  EX MEM  WB
1 1.0 0.909
5 2.778 2.525
100 4.808 4.371
1000000 5.0 4.545

단계당 200ps, 파이프라인 레지스터 오버헤드 20ps 를 가정한 계산이다(가정값이지 특정 CPU 의 실측값이 아니다). 명령어가 하나뿐이면 파이프라인은 이득이 없고, 오버헤드 때문에 오히려 느리다(0.909). 명령어가 많아지면 5배에 가까워지지만 오버헤드가 있으면 5배에 닿지 못한다(4.545). 지연 시간과 처리량이 다른 지표라는 점이 숫자로 드러난다.

현업에서는

  • 지연 시간 vs 처리량: 서비스 성능도 같은 두 축으로 본다. 배치 처리를 늘리면 처리량은 오르지만 개별 요청의 지연은 늘 수 있다. “빨라졌다” 고 말할 때 어느 쪽인지 명시해야 한다.
  • 가장 느린 단계가 전체를 정한다: CI/CD 파이프라인, 데이터 파이프라인, 메시지 큐 소비자 체인 모두 병목 단계의 처리량이 전체 처리량이다. 다른 단계를 아무리 빠르게 해도 소용없다. 쿠버네티스에서 특정 단계 디플로이먼트만 레플리카를 늘리는 것이 이 병목을 넓히는 일이다.
  • 의존성 줄이기: CPU 파이프라인이 의존 없는 명령어를 겹쳐 실행하듯, 소프트웨어도 서로 독립인 I/O 요청을 동시에 보내면(비동기, 배치) 왕복 지연을 겹칠 수 있다.

확인 문제

  1. 5단계 파이프라인에서 명령어 10개를 실행하는 데 이상적으로 몇 사이클이 걸리는가.
  2. 파이프라이닝은 명령어 하나의 지연 시간을 줄이는가.
  3. 단계 시간이 각각 100, 150, 300, 200, 100ps 인 파이프라인의 클록 주기는 최소 얼마인가(레지스터 오버헤드 무시).
  4. 파이프라인을 무작정 깊게 만들면 생기는 문제 두 가지는.

풀이

  1. 5 + 10 − 1 = 14 사이클.
  2. 줄이지 않는다. 오히려 파이프라인 레지스터 오버헤드와 단계 불균형 때문에 조금 늘 수 있다. 늘어나는 것은 처리량이다.
  3. 가장 느린 단계인 300ps.
  4. 분기 예측 실패 시 버리는 작업이 늘어나고, 파이프라인 레지스터 오버헤드가 단계 시간에서 차지하는 비중이 커진다.

더 읽을거리 (References)