Kim Seon Deok
[Quantitative approach] ch3.3 Reducing Branch Costs With Advanced Branch Predictions 본문
[Quantitative approach] ch3.3 Reducing Branch Costs With Advanced Branch Predictions
seondeok 2023. 12. 15. 11:22
Outline
Ch3.3 Reducing Branch Costs With Advanced Branch Predictions
1.Correlating Branch Predictors
- Global Branch Correlation
- Gshare predictor
- Local Branch Correlation
2. Tournamanet predictor
3. Hybrid predictor
4. TAgged GEometic— predictors
Ch3.4 Overcoming Data Hazards With Dynamic Scheduling
branch hazard로 인한 stall은 pipeline의 성능을 저하시키기 때문에 branch hazard의 수를 줄이는 Loop unrolling 기법의 방식을 사용했다.
pipeline이 더 깊어지고 clock per instruction 이 증가함에 따라 branch predict의 정확성에 대한 중요성이 커졌다.
이번에는 branch predict를 통해 성능 저하를 막는 여러 가지 방식을 알아볼 것이다.
Correlating Branch Predictors
correlating predictors = two-level predictors
다른 branch의 동작을 사용해서 prediction을 수행하는 branch predictor이다.
- Global Branch Correlation
최근에 execution path에서 실행된 branch instruction의 결과는 이후의 다른 branch의 instruction 결과에 correlate된다.
if(cond1)
....
if(cond1 AND cond2)두 if 문의 조건은 서로 dependent하다. 그렇기 때문에 correlation으로 인해 첫 번째 branch가 not taken이라면, 두 번째 branch 또한 not taken이다.
branch Y : if (cond1)
branch Z : if (cond2)
branch X : if (cond1 AND cond2)branch Y와 branch Z가 taken이라면, branch X도 taken이다.
branch Y와 branch Z가 not taken이라면, branch X도 not taken이다.
Global History Register (GHR)
모든 branch의 global T/NT history를 기록하는 register
Pattern History Table (PHT)
최근 GHR 값에 대한 결과를 기록하는 table로 2 bit counter table이다.
Global branch correlation을 capture하려면 현재까지 진행된 branch instruction의 global T/NT history를 register에 유지하면서 이를 이용하여 GHR 값에 대한 최근 branch 결과를 기록한 PHT에 액세스해야 한다.
-> 동일한 global branch history가 마지막으로 발생했을 때의 branch instruction 결과를 기반으로 predict를 수행한다.
Gshare predictor
Gshare에서 index는 branch address와 가장 최근의 branch 결과(GHR)를 XOR(hashing)하여 PHT에 접근한다.
이렇게 함으로써 predictor에 사용되는 더 많은 context information을 추가할 수 있고 2 bit counter array의 utilization을 올릴 수 있다. 하지만 XOR연산으로 인해 accuracy가 올라가지만 access latency가 증가한다는 단점이 있다.
* One-Level branch predictor
one-level branch predictor은 이전의 instance로부터 target address를 BTB에 저장하고 PC값을 통해 access한다.
Branch Target Buffer(BTB)는 target address를 저장하고 있는 cache이다.
1. branch instruction 수행
2. target address를 BTB에 write
3. 다음에 branch instruction 수행 시 BTB에서 hit이라면 hit signal을 and gate의 입력으로 보내고 target address를 mux의 입력으로 보냄
- taken이라면 PC + target address
- not taken이라면 PC + 4
- taken이지만 BTB miss라면 PC + 4
* Two-Level branch predictor
one-level branch predictor에서 Global branch history가 Direction predictor에 access하도록 하여 predict accuracy를 높인다. 이 때 global branch history를 유지하기 위해 GHR을 이용한다.
* Two-Level Global history branch predictor
two-level branch predictor에서와 다르게 현재 branch instruction의 history와 이전 branch instruction의 history를 결합하고 XOR 연산을 추가하여 predict를 수행한다.
- Local Branch Correlation
특정 branch의 outcome은 이전의 동일한 branch의 결과에 correlate된다.
local history에 대한 motivation은 loop branch를 높은 정확도로 예측하고자 하는 경우에서 출발한다.
- loop branch를 완벽하게 predict하려면 loop의 마지막 iteration을 식별해야 한다.
- 각 local history에 대한 PHT entry를 별도로 갖고 있으면 각 loop의 iteration을 구별할 수 있다.
- loop의 길이가 짧은 경우에 동작한다.
Local branch correlation을 capture하려면 각 branch에 대해 history register를 유지하고 해당 register의 값에 따른 history를 기록하는 table을 사용해야 한다.
-> Local History / Branch Predictor = 특정 branch의 prediction은 해당 branch의 local history가 마지막으로 나타났을 때의 결과를 기반으로 한다.
Local branch correlation은 각 branch에 대한 개별 history를 유지하기 때문에 predict가 더 정교하다.
그리고 해당 branch의 특정 history pattern에 따라 predict를 수행하기 때문에 branch 간 independency가 보장된다.
local history table
각 entry는 가장 최근의 branch outcome으로 구성된다.
saturating counter
local prediction을 제공한다.
first level : local history register 집합 -> branch instruction의 PC 값을 기반으로 history register를 select
second level : 각 history entry에 대한 saturating counter table -> 동일한 branch의 최신 history를 이용해 그 branch가 어떤 방향으로 진행되었는지를 확인
* Two-Level Local History Branch Predictor
Hybrid Branch Predictors
각 branch에 대해 다른 predictor가 더 효과적인 경우가 있기 때문에 다양한 type의 predictor를 섞어서 가장 높은 성능을 출력하도록 하는 방식이다.
프로그램 시작 시 predictor를 train하고, train하는 데 걸리는 시간을 warmup time이라 한다.
predictor가 많은 정보를 사용하게 되면 prdictor를 train하기 위해 시간이 오래 걸리게 된다. hybrid branch predictor를 사용하면 warmup time을 줄일 수 있다. 하지만 여러 type의 predictor를 평가해 보고 select하는 과정에서 추가적으로 latency가 발생하며 어떤 predictor를 사용할 지에 대한 selector가 추가적으로 필요하다.
Tournament Predictors
tournament predictor는 global predictor와 local predictor를 사용하고 각 branch에 대해 더 높은 성능을 내는 predictor 하나를 select하는방식이다.
이 때 global predictor는 가장 최근의 branch history를 사용해 predictor를 indexing한다.
local predictor는 branch address를 index로 사용한다.
Tagged Hybrid Predictors = TAGE = TAgged GEometic predictors
tagged hybrid predictor는 다른 길이를 가진 history로 인덱싱된 global predictor들로 구성된다.
PPM(Prediction by Partial Matching)은 branch prediction 알고리즘과 비슷하게 history를 바탕으로 하드웨어 동작을 예측하는 통계적 압축 알고리즘이다.
PPM predictor class를 TAGE라 하고 서로 다른 길이의 history로 indexing 된 여러 global predictor를 사용해서 accuracy를 높인다.
위의 5개의 prediction table로 이루어진 TAGE에서 p(i)는 가장 최근의 i개의 branch history의 hash를 사용하여 access된다.
h[0:L(1)]은 shift register로, 이 곳에 gshare와 동일한 방식으로 histiory가 store 된다.
-> 서로 다른 history length를 사용해서 각 predictor를 indexing한다.
1. p(0)은 history를 사용하지 않고 PC값만을 사용하기 때문에 항상 match된다. p(1)~p(4)에서 어느 것도 match되지 않는다면 p(0)를 기본 predictor로 사용한다.
2. p(1)~p(4)의 prediction은 tag가 branch address와 global branch history의 hash와 일치할 때 사용된다.
2-1. p(1) : 가장 짧은 길이의 history로 branch prediction 수행
2-2. p(2) : p(1)보다 긴 길이의 history로 branch prediction 수행
2-3. p(3) : p(2)보다 긴 길이의 history로 branch prediction 수행
2-4. p(4) : p(3)보다 긴 길이의 history로 branch prediction 수행
- pred filed : branch가 어떻게 예측되었는지를 나타냄
- tag field : 특정 길이의 history에 대한 hash로 구성됨
- use field : 해당 entry의 prediction이 최근에 이루어졌는 지 여부를 나타냄 -> 주기적으로 모든 entry에서 재설정되어서 오래된 prediction이 지워질 수 있게 함
tagged hybrid predictor의 서로 다른 table들은 각각 다른 history length를 사용하기 때문에 다양한 상황에 적용할 수 있다.
length가 짧은 history는 빠르게 변하는 branch에 대한 prediction에 도움이 되고 history length가 더 길어질 수록 장기적인 pattern에 기반한 prediction에 유용하다.
tagged hybrid predictor 는 gshare 방식에 비해 구현하기가 더 복잡하고 multiple tage를 확인하고 prediction result를 선택해야 하기 때문에 약간 더 느리다.
하지만 pipeline이 점점 깊어지고 branch misprediction에 대해 penalty가 점점 커짐에 따라, 높은 accuracy를 얻는 것은 바로 위에서 언급한 단점보다 더 중요하다. 따라서 최근 high-end processor는 tagged hybrid predictor 방식을 사용하고 있다.