Branch Prediction

비록 우리 과제에서는 disable 하기는 했지만, 이런기능도 있다는 것이 흥미롭다.
하지만, enable 했을경우 LCD에서 buffer under run 현상이 발견되어서 임베디드 과제에는 적용이 힘들지도 모르겠다.(혹은 ARM 계열에서만 발생하는 문제일 수 있다.)

원문 : http://minjang.egloos.com/503419

---

(2008년 6월 21일에 수정)

대부분의 고성능 CPU들은 거의 모두 Out-of-Order Execution이라고 불리는 비순차 실행을 지원하고 있다. Out-of-Order(OOO)의 목적은 하나의 스레드 내에서 최대의 병렬성을 찾는 것이다. 당연한 이야기겠지만 프로그램 코드는 프로그래머가 의도한 대로 위에서 아래로 순차적으로 실행된다. 중간에 if, for, 함수 호출이 있으면 다른 곳으로 점프하기도 하지만 본질적으로 순차적으로 수행되어야한다.

1: a = b + c;
2: d = a + b;
3: z = x * y;

위와 같은 경우 2번 명령은 1번이 끝나지 않으면 미리 실행될 수 없다. 그런데 덩달아 아무 상관없는 3번도 기다려야한다. 만약, 1, 2번에 있는 명령들이 지독하게 느린 것들이라면 아무 죄없는 무관한 뒤따르는 명령어들도 모두 기다려야만 하고 이는 성능 저하로 이어진다.

여기서 만약, 명령어를 처리할 수 있는 차선이 하나 더 존재해서 (이러한 구조를 Superscalar라고 한다) 1, 2에 의존적이지 않는 3번 명령을 동시에 처리할 수 있으면 어떻게 될까? 병렬성을 찾아 동시에 명령을 실행하기 때문에 당연히 성능이 높아질 것이다. 이렇게 미리 수 많은 명령어를 미리 가져와 서로 독립적인 것들을 가능한 먼저 처리해주는 것이 비순차 실행의 특징이다. 대신 밖에서 보는 프로그래머는 이러한 내용을 모르도록 감춰야 한다.

이렇게 앞에 있는 명령어들을 미리 가져올 때 여러 문제가 있지만 가장 골치아픈 문제가 if 문과 같은 분기문이다.

1: a = e + f;
2: if (a == 0)
3:     b = 0;
4: else
5:     b = 1;

위와 같은 코드를 생각해보자. 수퍼스케일러 CPU는 동시에 명령 흐름들을 처리할 수 있으므로, 독립적으로 동시에 실행 가능한 명령어들을 찾는다. 그래서 1~5번 명령어를 미리 읽어와서 서로 독립적으로 실행될 수 있는 녀석들을 찾기 시작한다. 그런데 2번에 if문이 있어서 3번을 읽어야할지 5번을 읽어야할지 아직 알 수가 없다. 물론 a 값이 계산될 때 까지 기다리면 되지만 요즘 CPU들은 이것 마저도 못 기다린다.

그래서 일단 찍는다. 정말로 찍는다. "주어진 분기문이 참이냐 거짓이냐" 라는 Yes/No 질문에 예측을 한다. 이것을 branch prediction, 분기예측이라 부른다. 예를 들어, 분기예측기가 a == 0일 확률이 높다고 예측하였다고 하자. 그러면 CPU는 그것을 믿고 3번 명령어를 가지고 와서 처리한다. 그리고 좀 있다가 2번 명령이 완전히 완료가 되어 a가 0이라고 판명이 나면 다행인 거고 아니면 다시 되돌린다. Undo를 하는 것이다. 그리고 다시 수행을 해서 3번 대신 5번이 수행되도록 한다. 이런 짓거리를 speculative execution이라고 한다. 사전적으로 번역하면 '투기적 실행', 좀 풀어 해석하면 예측 실행 정도가 되겠다.

이렇게 예측 실행이 맞으면 상당한 성능을 끌어올릴 수 있다. 반면에 틀리면 손실이 당연히 있다. 그러나 평균적으로 득이 훨씬 크기 때문에 비순차 실행 머신에서는 모두 이것을 하고 있다. 그러나 펜티엄4의 넷버스트 아키텍쳐는 이럴 때 손실이 상당히 크다. 왜냐면 파이프라인이 엄청 깊다보니 분기 예측이 틀릴 때 파이프라인을 몽땅 비우고 시키고 다시 채우는데 수십여 사이클이 소모된다.

어떻게 하면 잘 찍을지... 지난 십여년 이상 엄청난 연구가 이루어졌다. 그래서 대부분의 소프트웨어에서 저런 경우 분기문의 예측율은 보통 90%를 훌쩍 넘는 경우가 많다. 물론 if 문이 정말 rand()와 같은 어려운 경우라면 남는 장사가 아니겠지만 대표적으로 for 루프에 있는 분기문 정도는 아주 높은 확률로 예측이 가능하다. 이것은 컴퓨터 프로그램은 대부분 locality (지역성)이 있기 때문에, 그 전에 분기문의 결과가 어떠했는가로부터 학습한 뒤 미래를 예측하면 상당한 적중률을 보인다. 캐쉬와 같다고 보면 된다.

분기문은 if 뿐만이 아니라 for, while과 같은 루프문, 함수 호출, 간접 호출 (함수 포인터를 이용한 호출, virtual 함수 호출)도 모두 포함한다는 것을 알아두자. 그리고 함수 포인터를 이용한 간접 호출은 이외에도 "어느 곳으로 가는가"와 같은 문제를 하나 더 풀어야만 한다. 그래서 더욱 어려운 문제가 된다.


한줄 요약:
(조금 과장해서) 프로그램 짤 때 if문을 최대한 줄이자.