편견이 깨지는 어셈블리 프로그래밍 - 최적화 강좌 1 - 3  
 
 





브랜치 유닛
파 이프 라인의 등장으로 우리는 CPU의 클럭 속도를 더 높일 수 있게 되었다. 하지만 파이프 라인에도 약점은 존재한다. 바로 파이프 라인을 채우는 데 걸리는 시간이다(파이프 라인 참고) 파이프 라인은 파이프가 채워져 있을 때만 제 속도를 낼 수 있는 시스템인데 이 파이프가 비워지는 경우가 있다. 그 중 한 가지 경우가 하나의 CPU가 리셋됐을 때로(이 경우는 어쩔 수 없다) 다른 하나는 프로그램 명령 흐름 제어가 바뀌었을 때이다.
즉 JMP 명령 등 브랜치(branch) 명령이 발생했을 때다. 그래서 JMP 명령(C 언어의 경우 for, if, while, select 등의 명령어)을 포함하는 브랜치가 잦은 프로그램일수록 파이프 공정을 비우고 다시 채우는 현상이 빈번하게 발생하므로 파이프를 다시 채워야 하는 시간으로 인하여 수행 속도의 감소 현상이 일어나게 된다. 하지만 이러한 브랜치 명령에 의한 수행속도 감소를 없애기 위해 브랜치 명령을 쓰지 않는다는 것은 불가능한 일이다.
그러므로 최대한으로 브랜치에 의한 수행 속도 감소를 없애기 위해 등장한 것이 브랜치 예측 유닛이다. 브랜치 예측 유닛은 브랜치 타겟 버퍼(BTB)에 실행되었던 예측되는 브랜치 대상 영역의 코드들을 가지고 있다가 브랜치가 실제 발생되었을 때 브랜치 타겟 버퍼들 중에서 해당 브랜치 주소와 일치하는 것이 있으면 명령 큐를 바로 브랜치 타겟 버퍼의 내용으로 교환함으로써 브랜치로 인한 파이프 채움 대기 시간을 최대한으로 줄이는 방식과 명령으로부터 예측되는 브랜치 대상 주소로부터 명령들을 가져올 준비를 하고 있는 방식에 의하여 브랜치에 대한 수행속도 피해를 줄이고 있다.
그럼 펜티엄 Ⅲ의 브랜치 예측 방식에 대해 알아보자. 펜티엄 Ⅲ에는 512개의 브랜치 타겟 버퍼가 존재한다. 펜티엄 Ⅲ의 브랜치 예측 방식에는 동적 브랜치에 대한 예측과 정적 브랜치에 대한 예측 이렇게 2가지 방식이 있는데 이 두 가지는 어떻게 다른 지 알아보자. 동적 브랜치란 간접 주소에 의한 브랜치(예: jmp[bx])에 대해 예측을 해주는 것을 말하고 브랜치 예측 방식은 패턴 매칭 방식과 최후 4개의 브랜치했던 주소를 기억하는 방식으로 구성되어 있다. 특히 루프의 경우 4개의 브랜치 예측 주소에 당첨될 확률이 높다. 또한 펜티엄 Ⅱ, Ⅲ부터 채택된 ret 명령에 의한 예측 시스템도 있다. 원래 브랜치 명령은 jmp/call 명령들을 디코딩(분석)하면서 나온 주소를 보관하는 방식인데 ret 명령의 경우 돌아갈 주소가 스택에 있기 때문에 주소를 얻기가 힘들었다.
하지만 인텔에서는 스택의 주소까지 긁어오는 과감한 브랜치 예측을 포함시키게 된 것이다. 정적인 브랜치(예: jmp Lvl1) 분기 예측방식은 해당 주소를 가져와서 예측을 할 수 있는 방법을 말한다. 브랜치를 100% 정확히 예측할 수 없다. 그럼 브랜치에 한 피해는 어떤 경우에 발생하는지 알아보자 .

◆ 어쩔 수 없는 브랜치의 피해
브 랜치의 대상이 브랜치 타겟 버퍼 내에 없어 브랜치 명령으로부터 가져온 브랜치 예측 주소를 사용할 때를 말한다. 브랜치 타겟 버퍼가 대부분 실행되었던 코드들을 캐시하기 때문에 프로그램의 앞부분이 아닌 실행된 적이 없었던 뒷부분으로 브랜치가 발생할 경우 브랜치 예측 주소로 최대한 빠르게 명령을 가져오는 대상을 바꿔 그 피해를 최소화하는 수밖에 없다. 이럴 경우 보통 대략 5클럭 정도의 손해를 보게 된다.

◆ 운 좋은 브랜치의 경우
브랜치 대상이 브랜치 타겟 버퍼에 존재할 경우이다. 이는 이미 캐시된 코드 데이터가 파이프 라인으로 주입되기 때문에 파이프의 흐름에 피해를 최소화시킬 수 있게 된다. 이럴 경우 보통 한 클럭 정도만이 손해를 보게 된다.

◆ 최악의 경우
이 는 주로 동적 브랜치에 주로 발생하는데 브랜치 대상이 브랜치 타겟 버퍼에 존재하지 않고 명령으로부터 예측했던 브랜치 예측주소와도 맞지 않을 경우이다. 이럴 경우 어쩔 수 없이 파이프 라인을 초기화하고 명령을 가져오는 대상을 브랜치 주소로 바꿔야 하므로 많은 시간을 손해보게 된다. 보통은 10에서 15클럭을 손해보며 최악의 경우 26클럭까지 손해보게 된다.

브랜치 명령으로 인해 손해보는 경우가 커 보이지 않을지도 모른다. 386 시절에는 명령어 하나당 3에서 11클럭 사이였기 때문이다. 하지만 펜티엄이후 명령의 디코딩/실행 시퀄()의 비약적 발전으로 인해 U/V 파이프에 최적화된 명령은 한 클럭에 2개의 명령을 동시에 수행할 수 있어 5클럭이라 해도 무시할 수 없는 크기가 된다. 그렇다면 최적화를 위한 브랜치와 관련해 몇 가지 내용을 정리할 수 있다.

① 최대한 브랜치 발생을 자제하고(while , if , for 등 자제)
② 브랜치를 쓸 경우 간접 주소 지정에 의한 브랜치를 최대한 피할 것(동적인 브랜치)
③ 브랜치와 브랜치 사이는 되도록이면 띄우고, 자주 순환되는 루프들의 경우 short의 점프 거리를 벗어나지 않을 것(+127,-128 바이트 이내)


출처: http://www.imaso.co.kr/?doc=bbs/gnuboard.php&bo_table=article&wr_id=72


+ Recent posts