컴퓨터구조 12 - Branch Prediction

근데 우리는 명령어가 언제 Branch인지 알 수 있을까?

첫 클락에서는 명령어가 뭔지 모른다. IR들어갈 때 쯤 알 수 있다.

 

branch는 뭐가 문제일까?

branch 하나 생기면 pipeline stage만큼 stall해야되는데 성능 개박살남 ㅇㅇ

 

 

 

Branch 해결 방법

---

branch를 해결하는 여러 방법중에 prediction에 대해 배워볼거다

branch를 제대로 예측하기 위해서는 3가지를 알아야한다.

1. 지금 fetch한 명령어가 branch냐 아니냐
2. branch direction (condition이 만족했냐 아니냐)
3. 만약 condition을 만족했다면 어디로가느냐

 

A. 간단한 prediction은 그냥 무조건 맞다고 하는거. 사실상 PC+4로 위에서 말했듯이 성능이 박살난다.

 

 

 

B.

요 밑에 BTB라는 buffer가 과거의 기록을 저장해논다. 과거주소에서 branch했다면 갱신해서 저장한다.

BTB를 통해서 1,3번 조건을 해결할 수 있다.

 

 

 

Direction prediction

---

그렇다면 2번 조건(branch 조건문이 맞냐 아니냐)을 어떻게 예측할 수 있을까? Direction prediction에는 여러 방법이 있다.

저번에 언급했던게 Compile 단계에서 할 수 있는 방법이고 이번에는 Runtime에서 적용할 수 있는 방법을 배워보자.

요즘엔 Two-level이나 Hybrid 방법을 쓴다.

 

 

Last time prediction

---

1bit 짜리 predition으로 마지막 결과를 따라한다.

근데 만약 1010101010 branch가 있다면 이런 방식은 적중률 0%임

 

Two-Bit Counter Based Prediction

---

2bit 짜리로 만들면 확률 더 올릴 수 있다.

85~90% 확률까지 나와서 많은 프로그램에서 사용하는 방식

근데 1프로도 중요하니까 더 나은 predition을 알아보자.

 

 

Two-Level Global Branch Prediction

---

branch들의 특성을 알아보니

요런게 있다 뭔 뜻이냐? 하나의 branch 결과가 다른 branch 결과와 연관성이 있다는 뜻이다.

 

이런 애들보면 앞의 branch의 taken에 따라 뒤 branch의 taken도 정해진다.

단순히 local하게 그 명령어만 볼게 아니라 앞 뒤 branch를 보고 예측해보자.

이러한 특성을 이용해 Global History Register (GHR)을 만든다.

밑에거는 아까랑 동일한데 위에서 Global branch history를 보고 predict

GHR에는 최근  branch들의 결과가 계속 갱신된다.

이 GHR의 pattern을 보고 해당하는 값을 PHP에서 찾아서 예측함. 

PHP에서는 2bit-counters로 계속 돌아간다. 따라서 GHR보고 PHP에서 찾은 2bit중에 상위 1bit으로 taken not taken 결정

요 두개의 level 활용해서 예측하는 방법임.