컴퓨터 구조 04 - 파이프라인과 병렬 처리
명령어 파이프라이닝, 해저드 처리, 분기 예측, 슈퍼스칼라와 비순차 실행
왜 파이프라이닝인가
이전 포스트까지 CPU가 명령어를 인출-해석-실행하는 과정을 살펴보았다. 그런데 이 방식대로라면 하나의 명령어가 완전히 끝나야 다음 명령어를 시작할 수 있다. 각 단계가 1 클럭 사이클이 걸린다면, 3단계 사이클에서 하나의 명령어에 3 사이클이 필요하다. 매 사이클마다 ALU, 메모리 접근 유닛, 디코더 중 하나만 일하고 나머지 둘은 놀게 되는 셈이다.
이 비효율을 해결하는 아이디어가 파이프라이닝이다. 세탁을 예로 들면 이해가 쉽다. 세탁기에 빨래를 넣고, 다 되면 건조기에 넣고, 다 되면 개는 과정을 순차적으로 처리하면 세 벌의 빨래에 9단위 시간이 필요하다. 그러나 첫 번째 빨래가 건조기로 넘어가는 순간 두 번째 빨래를 세탁기에 넣으면, 세 벌을 5단위 시간에 처리할 수 있다. 각 장비가 쉬지 않고 일하기 때문이다.
CPU 파이프라이닝도 같은 원리이다. 첫 번째 명령어가 해석 단계로 넘어가는 순간, 인출 유닛은 이미 두 번째 명령어를 가져오고 있다. 각 단계가 독립적으로 동작하여 매 클럭 사이클마다 하나의 명령어가 완료되는 이상적인 처리량을 달성할 수 있다.
5단계 파이프라인
교과서적인 RISC 파이프라인은 다섯 단계로 구성된다.
5단계 파이프라인
단계 사이클1 사이클2 사이클3 사이클4 사이클5 사이클6 사이클7
──────────────────────────────────────────────────────────
IF I1 I2 I3 I4 I5
ID I1 I2 I3 I4 I5
EX I1 I2 I3 I4 I5
MEM I1 I2 I3 I4
WB I1 I2 I3
IF = Instruction Fetch (명령어 인출)
ID = Instruction Decode (명령어 해석 / 레지스터 읽기)
EX = Execute (ALU 연산)
MEM = Memory Access (메모리 접근)
WB = Write Back (결과 레지스터에 기록)파이프라인이 가득 차면(fully pipelined), 매 사이클마다 하나의 명령어가 완료된다. 5단계 파이프라인이라고 해서 하나의 명령어가 1 사이클에 끝나는 것은 아니다. 각 명령어는 여전히 5 사이클이 필요하지만, 동시에 5개의 명령어가 각각 다른 단계에서 처리되고 있으므로 처리량(throughput)은 사이클당 1개가 된다.
파이프라인 단계 수를 늘리면 각 단계에서 처리하는 작업이 줄어들어 단계별 지연 시간이 짧아지고, 따라서 클럭 속도를 더 높일 수 있다. Pentium 4의 NetBurst 아키텍처가 31단계 파이프라인을 사용한 것도 이 때문이다. 그러나 단계가 너무 많아지면, 뒤에서 설명할 해저드로 인한 손실이 커진다는 트레이드오프가 존재한다.
해저드
파이프라인은 모든 명령어가 독립적일 때 이상적으로 동작한다. 하지만 현실의 프로그램에서 명령어 사이에는 다양한 의존성이 존재하며, 이를 해저드(hazard)라고 부른다. 해저드가 발생하면 파이프라인을 멈추거나(stall) 특별한 처리가 필요하다.
데이터 해저드는 이전 명령어의 결과를 다음 명령어가 필요로 할 때 발생한다.
데이터 해저드 예시
add r1, r2, r3 IF ID EX MEM WB
sub r4, r1, r5 IF ID EX MEM WB
↑
r1의 값이 아직 WB를 거치지 않았으므로
sub의 ID 단계에서 올바른 r1 값을 읽을 수 없다이 문제를 해결하는 핵심 기법이 포워딩(forwarding) 또는 바이패싱(bypassing)이다. WB 단계까지 기다리지 않고, EX 단계에서 산출된 결과를 다음 명령어의 EX 입력으로 직접 전달한다. 하드웨어에 별도의 데이터 경로를 추가하여, 파이프라인을 멈추지 않고도 데이터 의존성을 해결할 수 있다.
포워딩으로 해결
add r1, r2, r3 IF ID EX MEM WB
sub r4, r1, r5 IF ID EX MEM WB
↑────┘
EX의 결과를 직접 전달 (포워딩)다만 로드 명령어 다음에 그 결과를 바로 사용하는 경우에는 포워딩으로도 해결이 안 된다. 로드의 결과는 MEM 단계 이후에야 확정되므로, 최소 1 사이클의 지연(load-use hazard)이 불가피하다. 컴파일러는 이 지연을 피하기 위해 로드와 사용 사이에 독립적인 명령어를 삽입하는 명령어 스케줄링을 수행한다.
구조적 해저드는 두 명령어가 동시에 같은 하드웨어 자원을 필요로 할 때 발생한다. 예를 들어 명령어 인출과 데이터 메모리 접근이 동시에 발생하는데 메모리 포트가 하나뿐이라면, 하나가 기다려야 한다. 이를 해결하기 위해 현대 프로세서는 명령어 캐시와 데이터 캐시를 분리하고, 레지스터 파일에 독립적인 읽기/쓰기 포트를 두는 등 하드웨어를 복제한다.
제어 해저드는 분기 명령어로 인해 다음에 실행할 명령어가 불확실해질 때 발생한다. 조건 분기의 결과는 EX 단계에서야 결정되는데, 그동안 파이프라인은 이미 후속 명령어들을 인출하고 있다. 분기가 일어나면 이미 인출한 명령어들을 모두 버려야(flush) 하므로, 파이프라인 단계 수만큼의 사이클이 낭비된다. 이것이 파이프라인이 깊어질수록 분기 비용이 증가하는 이유이다.
분기 예측
제어 해저드의 비용이 크기 때문에, 현대 프로세서는 분기 예측(branch prediction)을 사용하여 분기 결과를 미리 추측하고, 추측한 경로의 명령어를 투기적으로(speculatively) 실행한다. 예측이 맞으면 파이프라인이 끊기지 않고, 예측이 틀리면 투기적으로 실행한 명령어를 폐기하고 올바른 경로부터 다시 시작한다.
가장 단순한 정적 분기 예측은 항상 특정 방향을 예측한다. 예를 들어 "역방향 분기는 taken, 순방향 분기는 not taken"이라는 규칙은 루프 분기에서 꽤 효과적이다. 루프의 끝에서 처음으로 돌아가는 분기는 대부분 taken이기 때문이다.
동적 분기 예측은 과거의 분기 이력을 기반으로 예측한다. 가장 기본적인 구조는 분기 이력 테이블(Branch History Table, BHT)이다.
2비트 포화 카운터 (각 분기 명령어에 대해)
taken
┌──────────────┐
│ ↓
┌────┐ taken ┌────┐
│ ST │←────────│ WT │ S = Strongly, W = Weakly
│ 11 │ │ 10 │ T = Taken, N = Not Taken
└────┘ └────┘
│ ↑
│ not taken │ not taken
↓ │
┌────┐ ┌────┐
│ WN │────────→│ SN │
│ 01 │ not │ 00 │
└────┘ taken └────┘
↑ │
└──────────────┘
taken
예측: 상위 비트가 1이면 taken, 0이면 not taken2비트 카운터를 사용하는 이유는 1비트 카운터의 한계 때문이다. 루프에서 1비트 카운터를 사용하면, 루프 종료 시 한 번의 not taken으로 상태가 뒤집혀서 다음 루프 진입 시 첫 번째 반복을 잘못 예측한다. 2비트 카운터는 한 번의 이탈로는 상태가 완전히 바뀌지 않으므로, 이 문제를 완화한다.
더 정교한 예측기로는 상관 예측기(correlating predictor)가 있다. 이는 현재 분기뿐 아니라 최근 다른 분기들의 결과도 고려하여 예측한다. 예를 들어 if (x > 0) 다음에 if (x > 5)가 오는 경우, 첫 번째 분기가 not taken이면 두 번째도 not taken일 가능성이 높다. 이런 상관관계를 포착하여 예측 정확도를 높이는 것이다.
분기 목적지 버퍼(Branch Target Buffer, BTB)는 분기 예측과 함께 사용되는 구조로, 분기 명령어의 목적지 주소를 캐싱한다. 분기가 taken으로 예측되면, BTB에서 목적지 주소를 즉시 가져와 다음 인출을 시작할 수 있다. BTB가 없다면 분기 목적지를 계산하는 데 추가 사이클이 필요할 것이다.
현대 프로세서의 분기 예측 정확도는 95% 이상에 달한다. 그러나 나머지 5%의 오예측이 성능에 미치는 영향은 파이프라인이 깊을수록 커진다. 20단계 파이프라인에서 오예측 한 번은 20 사이클의 손실을 의미하기 때문이다. 이것이 프로그래머가 분기 패턴을 예측 가능하게 작성해야 하는 이유이며, 정렬된 데이터에 대한 조건문이 정렬되지 않은 데이터보다 빠른 이유이기도 하다.
슈퍼스칼라 실행
파이프라이닝은 매 사이클마다 하나의 명령어를 완료하는 것을 목표로 한다. 과연 사이클당 하나가 한계인가? 그렇지 않다. 여러 개의 파이프라인을 병렬로 배치하면, 매 사이클마다 여러 명령어를 동시에 인출, 해석, 실행할 수 있다. 이것이 슈퍼스칼라(superscalar) 실행이다.
2-way 슈퍼스칼라 파이프라인
사이클 1 2 3 4 5
──────────────────────────────────
파이프0 IF_I1 ID_I1 EX_I1 MEM_I1 WB_I1
파이프1 IF_I2 ID_I2 EX_I2 MEM_I2 WB_I2
파이프0 IF_I3 ID_I3 EX_I3 MEM_I3
파이프1 IF_I4 ID_I4 EX_I4 MEM_I4
→ 매 사이클마다 2개의 명령어를 동시에 처리현대의 고성능 프로세서는 대부분 4-way에서 8-way 슈퍼스칼라 설계를 채택하고 있다. 그러나 사이클당 처리하는 명령어 수를 늘리려면 독립적인 명령어를 충분히 찾아야 하며, 이를 위한 하드웨어 복잡도가 급격히 증가한다. 의존성 검사, 자원 할당, 결과 커밋 등의 로직이 모두 확장되어야 하기 때문이다.
비순차 실행
순차 실행(in-order execution)에서는 앞선 명령어가 해저드로 멈추면 뒤따르는 모든 명령어도 함께 멈춘다. 뒤에 있는 명령어가 앞의 명령어와 전혀 무관하더라도 실행할 수 없는 것이다.
비순차 실행(out-of-order execution, OoO)은 이 제약을 깨뜨린다. 데이터 의존성이 없는 명령어라면 프로그램 순서와 관계없이 먼저 실행할 수 있도록 한다.
프로그램 순서:
I1: load r1, [r2] ← 캐시 미스, 수백 사이클 대기
I2: add r3, r1, r4 ← r1에 의존, I1 대기 필수
I3: mul r5, r6, r7 ← I1, I2와 무관
I4: sub r8, r5, r9 ← r5에 의존, I3 대기 필수
비순차 실행:
I1을 발행 → 캐시 미스 대기
I3을 먼저 실행 (I1과 무관)
I4를 I3 다음에 실행 (I3 결과 사용 가능)
I1 완료 후 I2 실행비순차 실행의 핵심 구조는 토마슬로(Tomasulo) 알고리즘에서 유래한 예약 스테이션(reservation station)과 재정렬 버퍼(reorder buffer, ROB)이다. 예약 스테이션은 피연산자가 준비될 때까지 명령어를 대기시키고, 준비되는 즉시 실행 유닛에 보낸다. ROB는 명령어의 결과를 프로그램 순서대로 커밋하여, 비순차 실행에도 불구하고 프로그램의 의미(semantics)를 보존한다.
비순차 실행이 왜 중요한가? 캐시 미스가 발생하면 메모리 접근에 수백 사이클이 걸릴 수 있다. 순차 실행에서는 이 시간 동안 CPU가 완전히 멈추지만, 비순차 실행에서는 그 사이에 독립적인 명령어를 계속 처리할 수 있다. 현대 고성능 프로세서가 비순차 실행 없이는 성립하기 어려운 이유가 바로 이것이다.
명령어 수준 병렬성
파이프라이닝, 슈퍼스칼라, 비순차 실행은 모두 명령어 수준 병렬성(Instruction-Level Parallelism, ILP)을 활용하기 위한 기법이다. ILP란 프로그램에서 동시에 실행 가능한 명령어가 얼마나 존재하는지를 나타내는 척도이다.
이론적으로는 ILP가 무한히 높은 프로그램도 존재할 수 있지만, 현실에서는 데이터 의존성, 제어 의존성, 자원 제한 등으로 인해 활용 가능한 ILP가 제한된다. 일반적인 정수 프로그램에서 하드웨어가 추출할 수 있는 ILP는 사이클당 2~3개 명령어 수준이다.
ILP의 한계를 인식한 것이 프로세서 설계가 멀티코어 방향으로 전환된 핵심적인 이유이다. 단일 코어에서 더 많은 ILP를 추출하려면 하드웨어 복잡도가 지수적으로 증가하는 반면, 동일한 트랜지스터 예산으로 여러 코어를 배치하면 스레드 수준의 병렬성을 활용할 수 있기 때문이다. 물론 멀티코어의 성능을 끌어내려면 소프트웨어가 병렬화되어야 한다는 새로운 과제가 등장하지만, 이는 이후의 포스트에서 다룰 것이다.
다음 글에서는 권한 수준과 보호 링을 다룬다.