<aside> 💡 선 요약

다음 PC를 어떻게 예측할까?

• non-control-flow(80%) → PC+4
• control-flow(20%)
  • 30% not taken으로 예측 → 0.88
  • 70% taken으로 예측(BTB) → 0.89
  • 직전 결과로 예측 (BHT) → 0.94
  • 2-bit 카운터 사용 → 0.96
  • 글로벌, 로컬 history 기반 추측 → 0.97
  • JALR인 경우는 return address stack 사용

</aside>

Simplest (0.88)

PC=PC+4 (not taken)로 예측

non control flow는 80%이며, PC=PC+4로 연산한다.

• branch에서는 70%확률로 점프(taken)하고 30프로 확률로 PC=PC+4가 된다(not taken)
  • not taken 으로 예측 → 30%의 확률로 맞음
  • taken인 경우 → 틀림! (확률은 70%)

control flow가 20퍼니까

0.2*0.7=14% 확률로 틀리며, 패널티는 파이프라인 플러시로 생기는 버블 한칸이다!

→ IPC = 1/(1+0.20.71) = 0.88

Branch Target Buffer [Oracle] (0.89)

taken이 70%니까 taken으로 예측하고 싶다!

Branch 이후의 위치를 버퍼에 저장해 놓는다! Branch인 경우 Taken으로 예측

BTB는 기본적으로 엄청 큰 해시 테이블이다. 계산해서 넣는게 아니라 계산해 놓은걸 참조만

IF 단계에서

• ALU/L/S면 PC+4를 저장해 놓고
• Branch/JAL이면 PC+offset을 저장해 놓고
• JALR이면 그냥 보내 준다.

→ IPC = 1/(1+0.20.32) = 0.89

그러나 모든 PC에 대해 BTB를 만들어 놓기에는 너무 클 것이다! (PC는 32비트) 따라서 해시 테이블로 구현이 되어 있고, key는 PC의 N자리이다. 즉 2^N 크기를 가짐

해시 테이블의 문제는 바로 collision이다! 만약 collision이 발생한다면 엉뚱한 곳으로 PC를 보낼 것! → 안됨

위와 같은 경우가 collision이다. 그렇다면 어떻게 구분할까? 나머지 자리를 tag로 활용하면 된다!

그러면 어떤 tag를 저장할까? 전부? 너무 많음 → branch와 jump inst에 대한 tag만 저장해 놓으면 된다! (80%절약)