06 ILP (2)

Control dependencies

Case/switch statement

• switch는 memory에 jump address table이 존재
• 값에 따라 jump 할 곳을 jump address table에서 읽기만 하면 되니까 branch prediction이 도움 X
  

Branch prediction

PC 값을, branch 결과를 확실히 알 때까지 기다리겠다

• control flow가 아닌 instr에 대해서도 stall을 해야 함→ stall이 너무 많아
  

항상 NextPC = PC + 4로 하겠다.

• instruction이 sequential 하게 실행될 chance를 극대화
• flow instruction을 최대한 줄임 → loop unrolling, 삼항연산자
• wrong path는 다 flush 해야 함
  

Branch Target Buffer(BTB)

• 몇몇 branch들은 target address가 항상 거의 고정돼 있더라 e.g. for문
• PC 값을 가지고 BTB를 확인했을 때 BTB에서 hit → direction predictor로 이 branch가 taken 될지 안 될지 판단 → taken이면 BTB에 저장된 target address 불러와서 다음 명령어를 fetch
  

• branch prediction 과정에서 예측해야 하는 세 가지
  • 이 instr이 branch냐? → BTB로 가능
  • 이 brach가 taken 되냐? 안 되냐?
  • taken 된다면 target address가 어디냐? → BTB로 가능

Branch Direction Prediction

Static

• 항상 taken / 항상 not taken / backward는 taken, forward는 not taken
• Profile-based
  • 코드 몇 번 실행해 보고 그 결과를 수집해서 예측
  • ISA support 반드시 필요 → branch instruction format에 hit bits (taken/not taken) 추가해야 해
• Program-based
  • 사전 지식 사용 → if a < 0은 에러 코드니까 보통 not taken으로 해둠
  • profiling은 필요하지 않지만 좋을지 안 좋을지 모르고 ISA support bit가 필요
• Programmer-based
  • 코드를 짤 때 내가 제공 → likely-taken, likely-not-taken
  • profiling은 필요 없지만 마찬가지로 ISA support가 필요

Runtime

• runtime 때 수집되는 dynamic information을 가지고 branch를 taken/not taken을 예측하겠다
• profiling이 필요 없고 동적으로 변화하는 branch behavior을 반영할 수 있음
• hardware적으로 훨씬 복잡함
• Last Time predictor
  • 마지막 branch taken 결과만 가지고 다음 taken 여부를 결정
  • branch마다 BTB에 single bit로 표시
  • 바로 직전 결과에 지나치게 의존해서 다음을 판단하다 보니, 전환이 너무 빠름
• Two bit Counter Based Prediction
• strongly taken / weaky taken / strongly !taken / weakly !taken
  • 더 정확하지만 BTB entry에 저장해야 하는 bit 수가 증가 → hardware cost

Global Branch Correlation

• 앞서 실행된 branch의 결과를 보면, 지금 branch의 결과를 알 수 있는 경우가 있음
• 모든 branch의 T/NT history를 보고 이 branch의 outcome을 결정하자
• two level history를 사용
  • GHR(Global History Register) + history at that GHR
• GHR을 인덱스로 PHT의 entry에 접근해서, 그 안에 있는 2 bit branch predictor 확인
  • PHT (Pattern History Table)
    • processor 안의 SRAM이나 캐시에 저장

• Global predictor만으로는 서로 다른 두 branch가 GHR에 저장된 pattern이 같다는 이유로, 같은 PHT entry에 접근하고 수정해서 서로의 branch 예측 결과에 영향을 줄 수 있음
• Gshare
  • GHR과 PC 값을 XOR 해서 동일한 GHR 값을 갖더라도 branch가 다르면 서로 다른 PHT entry에 접근하도록 하자