
파이프라이닝(Pipelining): 공장 조립 라인의 마법
빨래를 할 때 세탁-건조-개기를 순서대로 하나요? 아니면 겹쳐서 하나요? CPU 성능 뻥튀기의 비밀.

빨래를 할 때 세탁-건조-개기를 순서대로 하나요? 아니면 겹쳐서 하나요? CPU 성능 뻥튀기의 비밀.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

매번 3-Way Handshake 하느라 지쳤나요? 한 번 맺은 인연(TCP 연결)을 소중히 유지하는 법. HTTP 최적화의 기본.

나는 Fetch-Decode-Execute 사이클을 배우면서 한 가지 이상한 점을 발견했다. Execute 단계에서 ALU가 연산할 때, Fetch 회로는 그냥 놀고 있다는 것이다. 세탁기가 돌아가는 동안 건조기가 비어 있는 꼴이랄까.
이게 왜 문제일까? CPU 안에는 각자 역할이 다른 하드웨어가 있다. Fetch를 담당하는 버스 인터페이스, Decode를 담당하는 제어 유닛, Execute를 담당하는 ALU, 메모리에 쓰는 Memory Access 회로, 그리고 결과를 레지스터에 Write Back하는 부분. 이 중 하나만 일하고 나머지는 쉰다면 비효율적이다. 나는 이 사실을 받아들이면서, 왜 CPU 설계자들이 파이프라이닝을 만들어냈는지 이해했다.
나는 이 개념을 빨래방에 비유해서 이해했다. 세탁-건조-개기가 각각 1시간씩 걸린다고 하자. 빨래 바구니 3개를 처리하려면 얼마나 걸릴까?
내가 처음 생각한 방식 (순차 처리):세 장비가 동시에 각기 다른 바구니를 처리하니까 전체 시간이 줄어든다. 이게 바로 처리량(Throughput) 증가다. 개별 빨래 바구니는 여전히 3시간 걸리지만(Latency), 시간당 처리하는 바구니 수는 거의 3배가 된다.
나는 이 비유를 통해 파이프라이닝의 본질을 깨달았다. 병렬 처리가 아니라 중첩 처리라는 점이 와닿았다.
RISC 아키텍처를 공부하면서 나는 CPU 파이프라인이 보통 5단계로 나뉜다는 사실을 정리해본다.
IF (Instruction Fetch) : 메모리에서 명령어 가져오기
ID (Instruction Decode) : 명령어 해석, 레지스터 읽기
EX (Execute) : ALU 연산 수행
MEM (Memory Access) : 메모리 읽기/쓰기 (필요시)
WB (Write Back) : 결과를 레지스터에 저장
타이밍 다이어그램으로 보면 이렇다:
시간 → 1 2 3 4 5 6 7 8 9
명령1 IF ID EX MEM WB
명령2 IF ID EX MEM WB
명령3 IF ID EX MEM WB
명령4 IF ID EX MEM WB
명령5 IF ID EX MEM WB
보라. 5사이클 후부터는 매 사이클마다 명령어가 하나씩 완료된다. 이게 바로 파이프라이닝의 마법이다. 나는 이 다이어그램을 보고 "아, 결국 이거였구나" 싶었다.
그런데 현실은 그렇게 아름답지 않다. 나는 파이프라인 해저드(Hazard)라는 개념을 접하면서 왜 CPU 설계가 어려운지 이해했다.
ADD R1, R2, R3 # R1 = R2 + R3
SUB R4, R1, R5 # R4 = R1 - R5 (문제: R1이 아직 준비 안 됨)
두 번째 명령어가 첫 번째 명령어의 결과(R1)를 쓰려고 하는데, 첫 번째 명령어가 아직 WB 단계에 도달 안 했다. 이걸 RAW (Read After Write) 해저드라고 부른다.
해결책:이게 내가 가장 흥미롭게 느낀 부분이다. 분기 명령어(Branch, Jump) 때문에 생긴다.
if (data[i] >= 128)
sum += data[i];
CPU는 if 결과를 알기 전에 다음 명령어를 미리 가져온다. 그런데 분기가 발생하면? 지금까지 가져온 명령어들을 전부 버리고(Flush) 새로 가져와야 한다. 이게 파이프라인 버블(Pipeline Bubble)이다.
같은 하드웨어를 두 명령어가 동시에 쓰려고 할 때. 예를 들어, 명령어를 Fetch하려는데 Data Memory Access도 동시에 일어나면? 이게 바로 하버드 아키텍처(명령어 메모리와 데이터 메모리 분리)가 나온 이유다. 나는 이 해저드를 통해 왜 L1 캐시가 I-Cache와 D-Cache로 나뉘는지 이해했다.
나는 분기 예측(Branch Prediction)이라는 개념이 제일 신기했다. CPU가 과거 패턴을 학습해서 미래를 예측한다니.
정적 예측 (Static Prediction): "Backward branch는 taken, Forward branch는 not taken"이라고 가정. 루프는 보통 여러 번 도니까 backward는 taken 확률이 높다는 경험칙이다.
동적 예측 (Dynamic Prediction): Branch History Table(BHT)에 지난 분기 결과를 기록해둔다. 2-bit predictor가 대표적인데, "taken-taken" 상태에서 한 번 not taken이 나와도 바로 예측을 바꾸지 않는다. 나는 이게 노이즈에 강한 상태 머신 같다고 받아들였다.
현대 CPU의 분기 예측 정확도는 90-98%다. 놀랍다.
Stack Overflow에 유명한 질문이 있다: "왜 정렬된 배열을 처리하는 게 더 빠를까?"
// 랜덤 데이터 vs 정렬된 데이터
for (int i = 0; i < arraySize; i++) {
if (data[i] >= 128)
sum += data[i];
}
정렬 안 된 데이터는 if 분기가 예측 불가능하다. CPU가 "다음에 taken일까 not taken일까?" 헷갈려서 예측이 계속 틀린다. 파이프라인이 계속 깨진다.
정렬된 데이터는 처음엔 쭉 not taken, 어느 지점부터 쭉 taken이다. CPU가 패턴을 빠르게 학습하고 예측 성공률이 높아진다. 파이프라인이 안정적으로 돌아간다.
나는 이 실험을 통해 "알고리즘적 최적화만 중요한 게 아니라, 하드웨어 특성도 알아야 한다"는 교훈을 얻었다. 결국 이거였다.
파이프라인 하나로는 부족하다고 느낀 엔지니어들이 슈퍼스칼라(Superscalar)를 만들었다. 여러 개의 파이프라인을 병렬로 돌린다. 현대 CPU는 보통 4-6개의 실행 유닛을 동시에 굴린다.
그리고 Out-of-Order (OoO) Execution: 명령어 순서를 지키되, 데이터 의존성만 없으면 먼저 실행 가능한 걸 먼저 처리한다. 예를 들어:
LOAD R1, [addr1] # 메모리 읽기 (느림)
ADD R2, R3, R4 # R1과 무관함
MUL R5, R1, R6 # R1 필요 (대기)
OoO CPU는 LOAD가 끝나길 기다리는 동안 ADD를 먼저 실행한다. 나는 이게 멀티태스킹의 하드웨어 버전이라고 이해했다.
내가 놀란 점: 현대 CPU의 파이프라인은 14~20단계 이상이다. Pentium 4는 무려 31단계였다.
왜? 파이프라인을 더 잘게 쪼개면 각 단계가 짧아져서 클럭 속도를 높일 수 있다. 하지만 trade-off가 있다. 단계가 길수록 분기 예측 실패 시 버려야 할 명령어가 많아진다. Pentium 4가 분기 예측에 민감했던 이유다.
요즘 CPU는 10-19단계 정도로 균형을 맞춘다. 나는 "더 길다고 무조건 좋은 게 아니구나"라고 정리해본다.
파이프라이닝과는 다르지만, SIMD (Single Instruction Multiple Data)도 비슷한 맥락이다. 하나의 명령어로 여러 데이터를 동시에 처리한다.
// 일반 코드
for (int i = 0; i < 4; i++)
result[i] = a[i] + b[i];
// SIMD (SSE/AVX)
__m128i va = _mm_load_si128((__m128i*)a);
__m128i vb = _mm_load_si128((__m128i*)b);
__m128i vr = _mm_add_epi32(va, vb); // 4개 동시 덧셈
이미지 처리, 행렬 연산, 암호화에서 엄청난 성능 향상을 준다. 나는 이게 파이프라이닝의 수평 확장이라면, SIMD는 수직 확장 같다고 받아들였다.
나는 "그래서 코드를 어떻게 짜야 하나?"라는 질문에 이렇게 답한다:
결국 이거였다: CPU를 이해하면 코드가 왜 빠르고 느린지 보인다.
나는 파이프라이닝을 통해 하나의 철학을 배웠다. "자원을 최대한 활용하라. 놀리지 마라." 이건 CPU뿐 아니라 시스템 설계 전반에 적용된다.
웹 서버도 마찬가지다. I/O 대기 중인 스레드가 CPU를 놀리지 않게 비동기 처리를 쓴다. 데이터베이스도 쿼리 파이프라이닝을 한다. 파이프라이닝은 단순한 하드웨어 트릭이 아니라, 효율의 보편적 원리였다.
나는 이제 코드를 볼 때 "이 반복문은 파이프라인 친화적일까?"라고 자연스럽게 생각한다. CPU 내부를 들여다본 덕분이다. 이게 바로 내가 CS 기초를 공부하는 이유다.