(펌) CPU 기초 교양 강좌 - 파이프라이닝(2)

3. 파이프라인의 문제와 해결

그런데, 파이프라인을 길이를 늘리고 클럭 스피드를 무작정 올리기만 하면 만사가 다 OK일까...
아무리 좋은 약이라도 부작용은 있는 법이죠. 파이프라인에서도 문제가 없는 건 아닙니다.

아래 명령을 CPU가 파이프라인을 통해서 수행한다고 해봅시다.

① MOV R1, 10 ; R1 = 10
② MOV R2, 20 ; R2 = 20
③ ADD R1, R2 ; R1 = R1 + R2
④ MOV R3, 30 ; R3 = 30

이것을 4단 파이프라인으로 처리한다고 하면 아래처럼 되겠죠.

일단 첫번째 명령(①)의 실행이 끝나면 R1에 10 이 기억된 상태가 됩니다.
일단 여기까지는 문제가 없습니다. 계속해서 다음 진행을 보겠습니다.

문제는 여기입니다. 이 시점에서 [기록] 단계에서는 R2에 20 을 쓰려하고 있는데, [실행] 단계에서는 R1 + R2의 연산을 하려고 합니다. 본래 이들 명령의 의도대로라면 먼저 R2에 20이 기록된 다음에 R1 + R2의 계산을 수행해야 하지만, 아직 R2의 값이 확정도 안되었는데 R1 + R2의 연산이 수행되려하고 있는 것이죠.

이처럼, 앞의 계산결과에 영향을 받는 명령이 있을 경우에, 무작정 파이프라이닝을 하게 되면 충돌이 일어납니다. 그러면 이런 충돌을 방지하기위한 뭔가 대책이 있어야겠죠?

(1) 지연 로드

가장 단순한 방법은 계산결과가 확정되기까지 다음 명령의 실행을 보류하는 것입니다. 그러기 위해서 CPU에서는 충돌위험이 있는 명령어 사이에 NOP(아무것도 안함) 명령을 삽입하게 됩니다.

① MOV R1, 10 ; R1 = 10
② MOV R2, 20 ; R2 = 20
③ NOP ; 아무짓도 안함
④ ADD R1, R2 ; R1 = R1 + R2
⑤ MOV R3, 30 ; R3 = 30

중간에 삽입된 NOP 명령은 말그대로 아무일도 안하고 클럭만 소모하기 때문에, 다음 명령의 수행을 지연시켜주는 역할을 하게 됩니다.

그럼 이 상태로 파이프라인을 돌려보면...

역시 첫번째 명령까지는 아무이상 없습니다.

NOP 명령 덕분에 ADD R1, R2에서 R2에 대한 참조가 한박자 늦어집니다. 따라서 충돌을 회피할 수 있습니다.

이렇게 하면 문제는 해결이 되긴 하지만, 이런 식으로 NOP 명령의 삽입이 많아지게 되면 애써 파이프라인을 만들어 놓은 의미가 퇴색됩니다. 파이프라인을 제대로 활용을 하지 못한다는 의미가 되니까요.

(2) 명령 다시짜기

그래서 좀더 지능적인 방법을 동원해 보기로 합니다.
뭐 이것도 간단합니다. 문제가 되는 명령을 별 문제없는 명령과 실행순서를 바꾸는 겁니다.

① MOV R1, 10 ; R1 = 10
② MOV R2, 20 ; R2 = 20
④ MOV R3, 30 ; R3 = 30
③ ADD R1, R2 ; R1 = R1 + R2

여기서는 ③번과 ④번의 실행순서를 바꿔보기로 합니다.

③번은 반드시 ②번 작업이 끝난 다음에 수행되어야만 하지만, ③번과 ④번의 작업에는 아무런 연관성이 없기 때문에 순서가 바뀌어도 상관이 없습니다.

그럼 이 상태로 파이프라인을 가동해 봅니다.

NOP 명령을 삽입할 때와 마찬가지로 ADD R1, R2가 R2의 값을 참조하는 시점이 한박자 늦어지게 됩니다. 그렇지만, 중간에 쓸모없는 NOP 명령이 끼어든게 아니라, 앞 뒤의 연산에 영향을 주지않는 명령을 삽입했기 때문에, 파이프라인의 효율성은 그대로 유지할 수가 있습니다.


그런데 아직 파이프라인의 문제가 다 해결된 것은 아닙니다.
이제 파이프라인에서 가장 골치아픈 문제가 기다리고 있습니다.
이것도 예제와 함께 알아보기로 하죠.

MOV R1, 0 ; R1 = 0
MOV R2, 10 ; R2 = 10

LOOP:
   JMP R2 = 0, EXIT ; R2가 0 이면 EXIT로 점프
   ADD R1, R2 ; R1 = R1 + R2
   DEC R2 ; R2 = R2 - 1
   JMP LOOP ; LOOP로 점프
EXIT:

END ; 종료

이것은 1 ~ 10까지의 합을 구해서 R2에 저장하는 간단한 프로그램입니다.
(어째 코드가 미묘하게 어셈블리 같으면서 어셈블리 같지가 않을 텐데, 그거야 제가 마음대로 만든 거니까 사소한건 신경쓰지 마시길...)

대강의 내용을 순서도로 표현해 봤으니, 이해가 안간다면 이쪽을 참고하셔도 좋겠습니다.

하여간, 여기서 주목할 것은 프로그램 내에 조건분기 명령이 포함되어 있다는 점입니다. 이 조건분기라는 것이 파이프라이닝에서는 참 다루기가 까다로운 녀석입니다.

그럼 이게 얼마나 쥐약인지(...) 이 프로그램을 파이프라인에 집어넣고 돌려보겠습니다.

뭐가 문제일까요?

조건분기에서 R2가 0일때 분기하도록 했습니다. 그런데, 지금 시점에서 조건분기 명령은 아직 실행도 안된상태입니다. 그러면 다음에 가져올 명령을 어떻게 알아내느냐 하는 문제입니다.

조건분기를 실행해서 R2 = 0 이 되면 다음에 실행해야할 명령은 'END'이고, 조건이 안맞을 경우는 'ADD R1, R2'를 실행해야 합니다. 그런데 파이프라인에서는 미리 명령을 읽어와야 하기 때문에 조건분기가 미처 다 해석도 되기전에 다음에 실행해야할 명령을 결정해야하는 모순에 빠지게 됩니다.

CPU에서 분기명령 처리

프로그램 상에서 어느 특정 위치로 분기하는 경우, CPU가 하는 일은 단지 다음에 가져올 명령이 있는 주소를 PC(Program Counter) 레지스터에 기록만 하면 됩니다.

달리 말하자면, 명령을 읽어오는(Fetch) 단계에서 어떤 명령을 가져올 것인가에 대한 결정에 영향을 주는 것이 분기명령이라고 할 수 있습니다.

예를들어 A, B, C, 라는 명령들이 있다고 할 때...

B가 D가 있는 위치로 분기하는 명령이라고 하면, CPU는 B 명령을 실행하면서 다음에 Fetch 시킬 명령을 D로 확정하면 됩니다.

만일 B가 조건 분기였다면, 조건이 참일 때는 D 명령을, 조건이 거짓이 되면 C 명령을 Fetch해야합니다.

그러면 파이프라이닝을 하는 과정에서 조건 분기를 만나면 어떻게 해야할까...
이번에도 조건이 확정될때까지 NOP 명령을 삽입해서 기다려도 되겠지만, 이번 경우는 NOP 명령의 삽입이 좀 많아집니다.

그래서 엔지니어들이 고민에 고민을 거듭한 끝에 내린 결론은...

"그냥 찍자..."

이것이 바로 분기 예측의 시작입니다.

(3) 분기 예측

이건 말 그대로 어느 쪽으로 분기할 것인가를 그냥 찍는 겁니다.
어느쪽으로 찍어도 일단 확률은 50% 입니다.

만일 잘못 찍었다면?
그땐 할 수 없습니다. 이미 가져온 명령을 취소하고 다시 가져올 수 밖에요...

즉, 분기예측이 성공하면 좋겠지만, 만일 예측이 빗나가면 오히려 성능이 떨어지게 됩니다. 따라서 기본 50%에서 가능한 100% 쪽으로 확률을 끌어올리는 것이 분기예측의 기술이라 하겠습니다.

그럼 어떻게 하면 확률을 끌어올려서 쪽집게 도사가 될 수 있을까요?

프로그램에서는 어느 과정을 반복해서 수행하는 루프 형태가 종종 쓰입니다. 이런 식의 루프에서는 분기 하는 경우보다 분기하지 않는 경우가 더 많습니다.

위에서 예로든 프로그램을 보아도, R2 = 0 일때 분기하도록 했지만, 실제 분기가 일어나는 경우는 단 한번이고 분기하지 않는 경우가 10번입니다. 따라서 이때는 분기하지 않는 쪽으로 찍는게 훨씬 이득이죠.

이런 식으로 분기에 대한 정도를 알 수 있으면, 찍는데 큰 도움이 됩니다. 그래서 똑똑한 CPU는 프로그램을 실행시키면서 실시간으로 이런 분기에 대한 빈도를 조사합니다. 그리고 이렇게 얻은 정보는 분기 캐시라는 것에 기록합니다.

그럼 CPU가 분기 캐시를 어떻게 활용하는지 보겠습니다.

분기 캐시의 동작 방식

우선 읽어들인 분기 명령이 분기 캐시에 존재하는지 확인합니다.

1. 분기하는 명령이 캐시에 들어있지 않은 경우
   (1) 명령어를 분기 캐시에 기록한다.
   (2) 우선은 분기하지 않는 경우를 가정해서 명령을 가져온다.
   (3) 그런데 분기하는 경우였다면: 분기캐시에서 빈도값을 +1 한다.

2. 분기하는 명령이 분기 캐시에 존재하는 경우
   (1) 캐시에 저장된 분기 빈도값을 조사한다.
   (2) 빈도값이 기준치 이상이면 분기하는 경우로 판단
      → 그런데 분기를 안했다면(비적중): 빈도값 -1
      → 분기를 하는게 맞았으면(적중): 빈도값 +1
   (3) 빈도값이 기준치 미달이면 분기하지 않는 경우로 판단
      → 예측 적중: 빈도값 -1
      → 예측 실패: 빈도값 +1

다음 시간에는 슈퍼 스칼라 구조에 대해 알아보기로 합니다.