RISC-V CPU #4: 파이프라인 심화, 해저드와 분기 예측

시리즈 로드맵

겹쳐 흐르면 충돌한다

3편에서 파이프라인이 다섯 명령어를 겹쳐 실행해 처리량을 높인다고 했다. 그리고 명령어들이 서로 얽히면 문제가 생긴다는 것도 예고했다. 이 얽힘을 해저드(hazard) 라 한다.

해저드는 파이프라인이 매 클럭 명령어를 하나씩 매끄럽게 완료하지 못하게 만드는 모든 상황이다. 세 종류로 나뉜다.

구조적 해저드: 설계로 대부분 회피

구조적 해저드는 같은 자원을 두 명령어가 동시에 쓰려 할 때 생긴다. RISC-V 고전 파이프라인은 이를 설계 단계에서 대부분 없앤다.

• 명령어 메모리와 데이터 메모리 분리: IF 단계는 명령어 메모리를, MEM 단계는 데이터 메모리를 쓴다. 둘이 분리돼 있어 같은 클럭에 IF와 MEM이 겹쳐도 메모리 포트가 충돌하지 않는다.
• 레지스터 파일의 반 클럭 분리: WB의 쓰기는 클럭 전반부에, ID의 읽기는 후반부에 일어나게 설계한다. 같은 클럭에 한 명령어가 쓰고 다른 명령어가 읽어도 충돌하지 않는다.

이런 설계 덕분에 기본 5단계 파이프라인에서는 구조적 해저드가 거의 발생하지 않는다. 남는 진짜 문제는 데이터 해저드와 제어 해저드다.

데이터 해저드: 아직 없는 값을 원한다

가장 흔한 데이터 해저드는 RAW(Read After Write) 다. 앞 명령어가 쓸 값을, 뒤 명령어가 읽으려 한다.

add x5, x6, x7    ← x5를 계산
sub x8, x5, x9    ← x5를 사용

3편에서 보았듯, sub가 x5를 읽는 시점(ID, 3번째 클럭)에 add는 아직 x5를 레지스터에 쓰지 못했다(WB, 5번째 클럭). 순진하게 두면 sub는 낡은 x5를 읽는다.

포워딩: 결과를 앞당겨 전달

해결의 핵심은 관찰 하나다. add의 결과는 사실 EX가 끝나는 순간(3번째 클럭 끝) 이미 존재한다. 레지스터에 쓰이기까지(WB, 5번째 클럭) 기다릴 필요가 없다. 그 값은 파이프라인 레지스터에 들어 있다.

포워딩(forwarding, 바이패싱) 은 이 값을 레지스터 파일을 거치지 않고 필요한 곳으로 곧바로 전달한다.

위 그림 ①이 이 경우다. add의 EX 출력(C3)을 EX/MEM 파이프라인 레지스터에서 뽑아, sub의 EX 입력(C4)으로 곧바로 보낸다. 포워딩 하드웨어는 “뒤 명령어의 소스 레지스터 번호가 앞 명령어의 목적지 레지스터 번호와 같은가”를 파이프라인 레지스터끼리 비교해 감지한다. 같으면 레지스터 파일 대신 포워딩 경로의 값을 ALU 입력으로 선택한다. 스톨 없이 해결된다.

Load-Use 해저드: 포워딩으로도 부족한 경우

포워딩이 항상 통하지는 않는다. 앞 명령어가 로드일 때가 문제다.

lw  x5, 0(x6)     ← 메모리에서 x5를 읽음
sub x8, x5, x9    ← x5를 사용

lw의 값은 메모리를 읽는 MEM 단계가 끝나야(C4 끝) 나온다. 그런데 sub는 EX(C4)에서 그 값을 원한다. 값이 나오는 시점과 필요한 시점이 같은 클럭이라, 포워딩으로도 시간을 맞출 수 없다.

위 그림 ②가 이 경우다. sub의 EX를 한 클럭 미룬다. 이 지연을 스톨(stall) 또는 버블(bubble) 이라 한다. 미뤄진 뒤(C5)에는 lw의 값(C4 끝에 준비됨)을 포워딩할 수 있다. 이렇게 로드 직후 그 값을 바로 쓰는 상황을 load-use 해저드라 하며, 포워딩을 쓰더라도 버블 하나는 피할 수 없다.

컴파일러는 이 버블을 줄일 수 있다. 로드와 그 값을 쓰는 명령어 사이에, 서로 무관한 다른 명령어를 끼워 넣으면 버블 자리를 유용한 일로 채운다. 명령어 순서를 바꾸는 이 최적화를 명령어 스케줄링이라 한다.

제어 해저드: 어디로 갈지 아직 모른다

분기 명령어는 다른 종류의 문제를 만든다. 다음에 실행할 명령어가 분기 결과에 달려 있는데, 그 결과는 나중에야 정해진다.

beq x6, x7, LABEL   ← x6 == x7 이면 LABEL로, 아니면 다음 명령어로
(다음 명령어)         ← 어느 쪽을 가져와야 하나?

분기의 성립 여부는 두 레지스터를 비교해야 알 수 있고, 이 비교는 EX에서 이뤄진다. 그런데 파이프라인은 매 클럭 명령어를 가져온다. 분기가 EX(3번째 클럭)에 도달할 즈음, 그 뒤 명령어들은 이미 IF와 ID에 들어와 있다. 만약 분기가 예상과 다른 방향으로 성립했다면, 잘못 가져온 그 명령어들을 버려야 한다. 이 버림을 플러시(flush) 라 한다.

분기가 EX에서 확정될 때까지 뒤 명령어를 무작정 가져오면:
  분기 성립 → 이미 IF/ID에 가져온 fall-through 명령어들은 잘못됨 → 플러시

플러시된 클럭은 낭비다. 이 낭비를 줄이는 방법이 분기 예측(branch prediction) 이다.

정적 예측

가장 단순한 예측은 항상 한 방향을 가정하는 것이다.

• 항상 not-taken: 분기가 성립하지 않는다고 보고 다음 명령어(fall-through)를 계속 가져온다. 성립하면 플러시.
• BTFN(Backward Taken, Forward Not-taken): 뒤로 가는 분기는 taken, 앞으로 가는 분기는 not-taken으로 예측한다. 반복문의 끝 분기는 뒤로 가며 대개 성립하므로 이 규칙이 잘 맞는다.

정적 예측은 하드웨어가 단순하지만 프로그램의 실제 동작을 반영하지 못한다.

동적 예측: 2비트 포화 카운터

동적 예측은 분기의 과거 이력을 기록해 다음을 예측한다. 가장 널리 쓰이는 형태가 2비트 포화 카운터다.

각 분기(PC로 색인)마다 네 상태 중 하나를 가진다. Strongly Taken, Weakly Taken, Weakly Not-taken, Strongly Not-taken이다. 분기가 실제로 taken이면 상태가 taken 쪽으로 한 칸, not-taken이면 반대쪽으로 한 칸 이동한다. 예측은 현재 상태가 taken 쪽이면 taken, 아니면 not-taken이다.

2비트를 쓰는 이유는 이력 유지(hysteresis) 다. 1비트 예측기는 한 번만 빗나가도 예측이 뒤집힌다. 반복문은 마지막 회차에서 딱 한 번 not-taken이 되는데, 1비트 예측기는 이 한 번 때문에 다음 반복문 진입 시 예측을 틀린다. 2비트는 강한 상태에서 한 번 빗나가도 약한 상태로만 이동해 예측 방향을 유지한다. 예외적인 한 번에 흔들리지 않는다.

예측에는 방향뿐 아니라 목적지 주소도 필요하다. BTB(Branch Target Buffer) 가 분기 PC에 대해 과거의 목적지 주소를 저장해, IF 단계에서 예측 즉시 다음 PC를 정하게 한다.

RISC-V의 선택: 지연 슬롯 없음

여기서 ISA 설계 이야기를 하나 짚는다. 과거 MIPS는 분기 지연 슬롯(delay slot) 을 두었다. 분기 바로 뒤 명령어를 분기 성립과 무관하게 항상 실행하도록 ISA에 못박아, 플러시 한 칸을 소프트웨어로 메우게 한 것이다.

RISC-V는 지연 슬롯을 두지 않았다. 지연 슬롯은 단순한 5단계 파이프라인에는 맞지만, 더 깊고 넓은 현대 파이프라인에서는 오히려 방해가 된다. 1편에서 본 대로 ISA는 특정 마이크로아키텍처를 강제하지 않아야 한다. RISC-V는 지연 슬롯 대신 분기 예측이라는 마이크로아키텍처 기법에 맡겼다. 파이프라인 구조가 바뀌어도 ISA는 그대로다.

비용으로 보기

해저드는 파이프라인의 이상적 처리량을 갉아먹는다. 이상적으로는 명령어당 1클럭(CPI = 1)이지만, 스톨과 오예측이 CPI를 늘린다.

분기 오예측의 비용을 간단히 추산하면 이렇다. 분기가 전체 명령어의 20%, 예측 정확도 90%, 오예측당 페널티 2클럭이라 하자.

분기로 인한 추가 CPI ≈ 0.20 × (1 - 0.90) × 2 = 0.04

즉 CPI가 1에서 약 1.04로 오른다. 예측 정확도가 낮아지거나 파이프라인이 깊어져 페널티가 커지면 이 값은 빠르게 커진다. 파이프라인을 깊게 만들수록 클럭은 높아지지만 오예측 페널티도 커지는 상충 관계가 있다. 이 균형이 파이프라인 깊이를 정하는 핵심 요인이다.

요약

파이프라인이 겹쳐 흐르는 대가로 해저드가 생긴다. 구조적 해저드는 설계로 대부분 없애고, 데이터 해저드는 포워딩으로(로드-사용은 버블 하나를 더해) 해결한다. 제어 해저드는 분기 예측으로 낭비를 줄이며, 2비트 포화 카운터가 예외적 한 번에 흔들리지 않는 예측을 제공한다. RISC-V는 지연 슬롯을 ISA에 넣지 않고 이 문제들을 마이크로아키텍처에 맡겼다. 다음 편에서는 지금까지의 단순 5단계를 넘어, 슈퍼스칼라와 비순차 실행 같은 심화 기법과 다른 CPU 아키텍처를 조망하며 시리즈를 마무리한다.

다음 글: RISC-V CPU #5 - 요약, 심화 아키텍처, 다른 CPU 아키텍처 (예정)