[컴퓨터 구조] Branch prediction

Branch Prediction은 Fetch 단계에서 세 가지를 예측하는 기술이다. 이는 명령어의 branch 여부, branch의 taken/not taken 여부, 그리고 branch의 target address이다.

Branch Target Buffer(BTB)는 이전에 taken된 branch의 target address를 저장하는 저장소다. BTB는 현재 명령어가 branch인지 판단하는 데도 사용된다.

 

Branch Prediction은 정적 예측과 동적 예측으로 나뉜다. 정적 예측에는 always not taken, always taken, BTFN, profile based, program analysis based 방식이 있다. 동적 예측에는 Last time prediction, Two-bit counter based prediction, Two-level prediction 방식이 있다.

 

 

 

Last time prediction

Last time prediction은 동적 예측 방식 중 하나다. 이 방식은 특정 위치의 branch에 대해 마지막으로 실행된 결과를 기반으로 다음 예측을 수행한다.

예측이 틀릴 경우, 다음 예측을 반대로 바꾸는 특징이 있다. 이는 branch의 패턴이 반복될 때 효과적으로 작동한다.

그러나 taken과 not taken이 번갈아 나타나는 패턴에서는 효율이 떨어진다. 이는 매번 예측이 틀려 지속적으로 예측을 바꾸게 되기 때문이다.

따라서 Last time prediction은 단순하지만 특정 패턴에 대해 제한적인 성능을 보이는 예측 방식이다.

 

 

 

 

Two bit counter based prediction

 

Two-bit counter based prediction은 동적 예측 방식의 하나다. 이 방법은 2비트 카운터를 사용하여 예측의 안정성을 높인다.

이 방식의 핵심은 예측이 두 번 연속으로 틀렸을 때만 다음 예측을 바꾼다는 점이다. 이는 일시적인 패턴 변화에 덜 민감하게 반응하도록 한다.

Two-bit counter는 네 가지 상태를 가지며, 각 상태는 strongly taken, weakly taken, weakly not taken, strongly not taken을 나타낸다. 예측이 맞으면 같은 방향의 강한 상태로, 틀리면 반대 방향의 약한 상태로 이동한다.

이 방법은 Last time prediction보다 안정적이며, 불규칙한 패턴에서도 더 나은 성능을 보인다.

 

 

 

Two level prediction

Two-level prediction은 더 복잡하고 정교한 동적 예측 방식이다. 이 방법은 두 가지 주요 개념을 바탕으로 한다.

첫째, Global branch correlation은 한 branch의 결과가 주변 branch들의 결과에 영향을 받는다는 개념이다.

 

 

둘째, Local branch correlation은 개별 branch의 결과가 반복되는 경향이 있다는 개념이다.

이 방식의 구현은 두 가지 주요 구성 요소를 사용한다:

1. Global History Register(GHR)는 최근 branch들의 taken/not taken 정보를 저장하는 레지스터다.
2. Pattern History Table(PHT)는 각 패턴에 대한 예측 정보를 저장하는 테이블이다.

 

예측 과정에서 GHR의 정보를 이용해 PHT에 접근하고, PHT에 저장된 2비트 예측 값(00, 01, 10, 11)으로 예측을 수행한다. 예측이 실제 결과와 다를 경우 PHT를 업데이트한다.

이 방식은 복잡한 branch 패턴을 더 정확히 예측할 수 있어 고성능 프로세서에서 널리 사용된다.

 

 

 

 

PHT issue

 

PHT(Pattern History Table) 사용 시 발생할 수 있는 간섭 문제와 그 해결 방안은 다음과 같다.

서로 다른 branch가 동일한 GHR(Global History Register) 값을 가질 경우, PHT의 같은 부분에 영향을 주는 간섭이 발생할 수 있다. 이는 예측 정확도를 떨어뜨리는 원인이 된다.

 

이 문제를 해결하기 위한 방법으로는 세 가지가 있다:

1. GHR의 비트 수 증가: GHR의 비트 수를 늘려 PHT의 크기를 확장하는 방법이다. 하지만 비트 하나 증가할 때마다 PHT 크기가 두 배로 커지므로, 하드웨어 제약으로 인해 무한히 늘릴 수 없다는 한계가 있다.
2. Branch filtering: 이 방법은 인덱스에 규칙성이 있는 branch만 PHT를 사용하도록 제한한다. 나머지 branch들은 last time prediction이나 two-bit prediction과 같은 더 단순한 예측 방식을 사용하게 한다. 이를 통해 PHT 사용을 최적화하고 간섭을 줄일 수 있다.
3. Hashing/index-randomization: Gshare나 Gskew와 같은 기법을 사용하여 PHT 접근 시 인덱스를 무작위화하는 방법이다. 이는 서로 다른 branch가 PHT의 동일한 위치를 참조할 확률을 줄여 간섭을 감소시킨다.

이러한 방법들은 각각의 장단점이 있으며, 실제 구현 시에는 하드웨어 자원, 예측 정확도, 복잡성 등을 고려하여 적절한 방법을 선택하거나 조합하여 사용한다.

 

 

 

 

Gshare

GHR만을 사용할 경우 실질적으로 PHT에서 사용되는 부분은 많지 않다. 많이 나오는 패턴이 어느정도 정해져 있기 때문에 PHT에서도 쓰는 부분을 지속적으로 사용하는 것이다. 때문에 Gshare predictor에서는 GHR과 branch의 pc값을 같이 써주면서 PHT에서 여러 부분이 사용될 수 있도록 분배해준다.

 

Gshare에서는 GHR값과 PC값을 XOR연산하여 나온 값을 PHT와 비교하여 예측한다. (branch A, B가 GHR값이 같을 때 pc를 통해 각 각 서로 다른 branch임을 알 수 있게 하여 PHT의 서로 다른 부분을 사용할 수 있게 하는 것이다.)

 

 

 

 

Gskew

 

Gskew는 Gshare을 조금 더 발전시킨 형태로 Gshare에서 XOR연산만을 했던 것과 달리 여러가지 연산에 대해 그에 해당하는 PHT에 접근하여 각 PHT마다 taken인지 not taken인지 예측하고 최종적으로 taken이 많이 나왔으면 taken으로, not taken이 많이 나왔으면 not taken으로 결정하는 방식이다.

-> 더 잘 예측될 순 있겠으나 더 복잡하고 하드웨어가 더 많이 필요하다.

 

 

 

 

Local Branch Prediction

 

위의 for문을 살펴보면 taken, not taken 여부가 1110을 갖는다. 이때 이 for문이 loop 안에 들어가 있다면 last time prediction이나 two-bit prediction을 사용할 때 지속적으로 예측이 틀리는 지점이 생긴다(항상 0을 1로 예측함)

그렇다면 이 for문 만을 위한 PHT가 있다면 매번 올바르게 예측할 수 있지 않을까?

이렇듯 branch마다 PHT를 따로 둬서 관리한다면 더 정확한 예측이 가능해진다.

 

 

 

 

Hybrid Branch Predictor

Hybrid Branch Predictor는 다양한 예측 방식을 조합하여 사용하는 고급 branch prediction 기법이다.

이 방식의 기본 개념은 각 branch마다 가장 적합한 예측 방법이 다를 수 있다는 점에 기반한다. 예를 들어, 어떤 branch는 local branch prediction이 효과적이지만, 다른 branch는 last time prediction만으로도 충분할 수 있다.

Hybrid Branch Predictor의 장점은 다음과 같다:

1. 예측 정확도가 향상된다.
2. Warm-up time(초기 패턴 수집 시간)이 줄어든다.

반면, 단점도 존재한다:

1. 어떤 예측 방식을 사용할지 결정하는 'meta-predictor' 또는 'selector'가 필요하다.
2. 여러 예측기를 동시에 운용하므로 예측 시간이 더 오래 걸릴 수 있다.

이 방식은 각 branch의 특성에 맞는 최적의 예측 방법을 적용함으로써, 전체적인 예측 성능을 높이는 것이 목표다. 하지만 복잡성과 하드웨어 요구 사항이 증가하는 trade-off가 있다.