Branch Prediction 정리

Data Dependence

Name Dependence

• Anti-dependence : WAR Hazard
  

• output-dependence WAW hazard
  

True Dependence

• RAW hazard
  

Static Branch Prediction

1. Taken 한다고 예측하기
2. Untaken 한다고 예측하기
3. Trace-based 예측

Dynamic Branch Prediction

BHT

Branch History Table
바로 직전에 branch 일어났는지를 추적

2비트 branch predictor

Correlated Branch Prediction

Motivation : 다른 branch의 결과에 내 branch가 영향을 받는다면?

다른 branch의 행동을 근거로 삼는 것
(M, N) Correlated Branch Prediction : M개의 branch 결과를 N비트 branch predictor 사용

Global History Branch Predictor

correlated랑 접근 방식은 동일
BHR의 비트 수 == Correlated 에서의 M
PHT = correlated에서의 entry

Local History Branch Predictor

motivation : 내 행동에 일정 패턴이 있을 때 맞추고 싶어

PC의 LSB를 BHT에도 가져와서 Indexing
여기의 BHT에는 해당 LSB 가진 branch들의 history만 적힐 것임!

Branch Target Buffers

IF stage

BTB에 해당 PC의 Entry가 있는지 찾기

ID stage

PC의 branch가 taken 됐는지 검증할 수 있음

EX stage

update & 원래 IF 해오기 (2 cycle)