분기 예측
덤프버전 :
1. 개요[편집]
Branch Prediction
파이프라인이 등장하면서 CPU는 수행이 채 끝나지도 않은 명령어의 결과를 사용해야 하는 일이 종종 있게 되었다. 특히 분기 명령어(branch instruction)의 경우 그 조건을 평가하는 데 필요한 값이 아직 계산되고 있다면, 어떤 명령어를 다음에 수행해야 할지 명령어를 가져오는(fetch) 단계에서 아직 판단할 수 없으므로 필요한 값이 다 계산될 때까지 기다리는(stall) 수밖에 없었는데, 이는 CPU의 성능을 크게 떨어뜨리는 요인이 되었다. 특히 이는 파이프라인이 깊어지면서 더 심해지는 문제였다. 그래서 필요한 값을 기다리지 않고 어떻게 분기할지 예측하여 파이프라인이 끊기지 않고 계속 수행되도록 하는 기법들이 여럿 등장하게 되었다. 이에 따라 CPU는 명령어를 가져오는 단계에서 분기 명령어의 조건을 아직 평가할 수 없다면 어떻게 분기할지 예측하여 그대로 다음 명령어를 수행하고, 나중에 조건을 평가할 수 있을 때 앞서의 예측이 틀렸다면 예측하여 수행된 명령어들을 취소하고 올바른 분기의 명령어를 다시 수행하게 된다. 다만 주의할 점은 이런 식의 추측 실행(speculative execution)을 할 경우에 명령어들은 취소되었지만 명령어가 참조한 메모리가 캐시에 올라오는 등 부작용(side effect)은 여전히 남아 있을 수 있는데, 프로세서 설계 시 이를 간과했다가 터진 것이 CPU 게이트.
높은 정확성의 분기 예측이 가능한 것은 프로그램 안에 있는 각 분기 명령어가 대부분 분기되거나(taken) 분기되지 않거나(not taken)의 둘 중 한 쪽 경우를 훨씬 많이 이용하는 경향성이 있기 때문이다. 예컨대 분기 명령어 하나로만 구성된 간단한 do-while 루프를 생각해 보자. 보통 루프를 계속 수행하는 경우가 루프를 벗어나는 경우보다 훨씬 많으므로, 돌아가는 분기를 타는(taken) 쪽으로 예측하면 정확성이 높을 것이다.
2. 종류[편집]
2.1. 정적 분기 예측[편집]
Static Branch Prediction
가장 간단한 방식으로, 실행시간 정보에 의존하지 않고 분기 예측을 수행한다. 이 중에서 유명한 것으로 BTFNT(Backward taken, Forward not taken)가 있는데, 이는 말 그대로 분기의 방향이 순방향이면 분기를 타지 않고, 역방향이면 분기를 타는 방식이다. 이는 루프의 수행 방식에서 착상한 것으로, 루프에서는 계속 수행하는 경우가 더 많은데 이는 역방향 분기의 경우이므로 분기를 타는 경우로 예측하고, break 문과 같이 루프를 벗어나서 다음 흐름을 실행하는 분기는 루프가 계속 수행되는 도중에는 잘 일어나지 않는데 이는 순방향 분기의 경우이므로 분기를 타지 않는 경우로 예측하는 것이다.
2.2. 동적 분기 예측[편집]
Dynamic Branch Prediction
실행시간 정보를 활용하여 분기 예측을 수행한다. 보통 정적 분기 예측보다 정확도가 더 높다.
2.2.1. 분기 예측 버퍼[편집]
Branch Prediction Buffer
각 분기 명령어마다 지난번에 그 분기가 실행되었는지의 여부를 저장해서 지난번에 분기되었다면 이번에도 분기하는 것으로, 아니라면 이번에도 아닌 것으로 예측해 보자. 그러면 각 분기 명령어는 분기하는 경우와 아닌 경우 둘 중 하나를 훨씬 많이 이용하므로, 대부분의 경우에는 지난번에 수행된 결과와 이번에 수행될 결과가 같을 것이다. 이렇게 각 분기당 1-bit의 버퍼만 사용하여 예측을 할 수있다. 물론 CPU 내부에 들어갈 수 있는 메모리는 한정적이므로 실제로는 모든 분기 명령어에 대해 bit를 할당하기보다는 직접사상 캐시(direct mapped cache)처럼 분기 명령어 주소의 낮은 쪽 bit들을 버퍼 칸 번호로 이용하여 다대일 사상이 되도록 할 것이다. 이런 방식에는 문제점이 하나 있는데, 만약 분기 예측이 한 번 틀렸다면 그것은 그 분기의 경향성과 다르지만 어쨌든 이번에 수행된 결과가 버퍼에 저장되므로 다음에도 또 틀릴 가능성이 높다는 것이다. 이런 문제를 해결하기 위해 버퍼당 2bit를 사용하여 두 번 연속으로 틀렸을 때만 예측을 바꾸도록 하면 더 좋은 성능을 낼 수 있다.[1] 한 분기 당 3bit 이상을 사용하는 것은 성능을 아주 조금만 증가시킬 뿐이다.
2.2.2. 연관 분기 예측[편집]
Correlating Branch Prediction[2]
바로 앞에서 설명한 간단한 분기 예측 버퍼는 각각의 분기 명령어의 수행 결과를 예측할 때 그 명령어 하나의 이전 수행 결과만 사용한다. 어떤 분기 명령어의 실행은 분명 다른 분기 명령어의 수행에 의존하므로, 다른 분기 명령어(특히 최근에 수행된 것들)의 수행 결과까지 사용한다면 더 높은 예측의 정확성을 얻을 수 있을 것이다. 예를 들어, if-then-else 구조의 경우에 if가 분기하면 else는 분기하지 않는다. 이처럼 특정 분기 명령어의 분기 여부는 주위에 있는 다른 분기 명령어의 분기 여부와 서로 상관관계를 갖는 경우가 있다. 이렇게 주위 상황도 함께 고려해 분기를 예측하자는 것이 연관 분기 예측이라고 할 수 있다.
이제 최근에 수행된 분기 명령어의 결과 m 개를 기록해 두고, 각각의 결과를 조합한 2m개의 경우마다 위의 n-bit 예측 버퍼 하나씩을 사용한 것을 (m, n) 예측기라고 하자. 만약 버퍼 칸 수가 E개라면 (m, n) 예측기에 필요한 버퍼의 총 크기는 버퍼 자체의 크기인 n bit * 2m * E + 최근 수행된 결과를 기록할 m bit가 된다.
다소 까다로워 보이기는 하지만, 결국 과거 히스토리에 기대어 분기를 예측한다는 것이 핵심이다. 즉, 특정 분기 명령어를 마주칠 때마다 그 주변의 분기 명령어의 관계를 함께 고려할 때, 최근 m번의 분기는 비슷한 양상을 보일 것이고 그에 따라 m비트 크기의 레지스터에 기록되는 비트열의 모습은 그 양상을 반영할 것이다. 따라서 그 m비트를 가지고 분기를 예측하는 데에 사용할 n비트 버퍼[3]를 결정한 뒤에 분기를 할 것인지 말 것인지를 예측하는 것이다. 보통 m비트 레지스터에 기록된 값을 인덱스로 사용해서 2m개의 n비트 버퍼들을 유지하고 있는 테이블로부터 실제 사용될 n비트 버퍼를 결정하게 된다.
연관 분기 예측 자체도 세부적인 방식에 따라 크게 두 종류로 나뉘는데[4], 위에서 설명된 방식은 최근 m번 수행된 분기 결과를 기록하는 m비트 크기의 Global History Register와, 그 2m비트 조합의 각각에 대해 n번의 분기 패턴을 기록하는 n비트 크기의 Global Pattern History를 사용하는 방식이다. 이 방식은 모든 분기 명령어들이 같은 History Register를 사용(Global History Register)하기 때문에 Global Branch Prediction이라고도 한다. 다른 방식은 Local Branch Prediction인데, 이때는 각 분기 명령어들이 서로 다른 History Register를 사용(Local History Register)한다. 그래서 특정 분기 명령어마다 최근 m번의 분기 결과를 별도로 기록할 수 있다. 서로 다른 분기 명령어마다 각기 다른 History Register를 사용해야 하는데, 이때는 보통 프로그램 카운터에 저장된 값, 즉 해당 분기 명령어의 주소가 이루는 비트열의 상/하위 몇개의 비트를 가지고 결정하거나 한다.
3. 성능[편집]
대체로 분기 예측이 적용된 프로세서는 그렇지 않은 프로세서들에 비해서 강세를 보인다. 모든 부분에 성능 향상을 기대할 수 없지만 반복문 등의 작업에서는 확실히 빨라진다. 간혹 분기 예측이 실패할 가능성도 있는데 과거의 프로세서들은 기술 수준이 낮아서 자주 실패했지만 최근에 출시되는 프로세서들은 분기 예측에 실패할 확률이 매우 낮으므로 오래된 최적화 테크닉이 더 느려질 정도이다. 예를 들어 사전 순으로 정렬된 문자열을 이진 탐색하여 찾는 경우, 비교한 문자의 값에 따라 3가지의 다른 동작을 해야하는데 분기 예측이 실패했다면 파이프라인 전체를 비우고 다시 채워야하므로 상당히 느려진다. 그래서 비트 연산과 점프 테이블을 조합하여 항상 일정한 사이클을 소모하도록 최적화할 수 있지만 분기 예측이 실패하지 않으면 단 2사이클 만으로 처리가 가능하기 때문에 최신 프로세서에서는 이러한 구식의 최적화 테크닉을 사용하지 않는것이 좋다.
4. 관련 문서[편집]
이 문서의 내용 중 전체 또는 일부는 2023-12-01 06:57:04에 나무위키 분기 예측 문서에서 가져왔습니다.[1] 벤치마크에 따라 결과는 달라지지만 대체로 90% 이상의 분기 예측률을 보인다. 물론 이것만으로 충분하지 않아서 밑에 설명된 것처럼 더 복잡해지기도 한다.[2] Two-Level Adaptive Training Branch Prediction 이라고도 불린다.[3] 이때 n비트 버퍼는 통상적으로 2비트 Saturating Counter이다.[4] 심지어 이 두 종류의 예측기를 함께 사용하기도 한다. 즉, 예측의 결과를 기록하는 버퍼를 따로 두어서 더욱 예측을 잘하고 있는 예측기를 실제로 사용할 예측기로 토너먼트의 승자처럼 고르는 것이다. 분기를 예측하는 예측기를 예측한다