BTB(Branch Target Buffer)
브랜치 타겟 버퍼 BTB란 간단하다. 과거에 103번지에서 100번지로 분기(jmp)가 일어나서 이동했다면 이번에 103번지를 다시 만났다면 100번지를 예상번지로 예측하는 방식이다.
- 이를 위해서 현재 PC값과 Next PC값이 저장되어있는 해쉬 테이블이 필요한데 이를 Branch Target Buffer라고 부른다.
i = 1;
100 : do{
101 : state1();
102 : i++;
103 : }while(i <= 10);
- 위의 코드처럼 처음 103번지를 만났을 때에는 Branch 명령어라는 것을 Fetch, Decode instruction에서 알 수 있다. 하지만 어디로 이동해야 할지는 i <= 10 조건을 계산하는 Execution 단계가 되어서야 확실히 알 수가 있다.
- 처음에 103번지를 만나고 나서 Branch 명령어라는 것이 밝혀지면 곧바로 BTB에 가서 현재 PC 값에 대응되는 값이 있는지 확인한다.
- BTB가 현재 비어있었다고 한다면 PC는 예측에 실패하고 단순히 Instruction의 길이만큼 더하여 PC 예측를 시도한다.
- i = 1이었으므로 i <= 10을 만족한다는 것을 Execution단계에서 확인한 후에 BTB 테이블에 현재 PC : 103 NextPC: 100이라고 저장한다.
- 그 후 i 가 10이 될때까지 우리 BTB는 Execution단계에 이르기 전에 분기를 예측해서 Decode 단계에 NextPc를 예측해 사이클을 절약할 수 있다.
- i = 10이 되었지만 여전히 BTB에는 PC : 103에서는 NextPC 100이라고 나와있기 때문에 PC는 100으로 설정되지만 Execution단계에서 틀렸다는 것을 검증해낸다.
- 분기 예측이 틀렸다면 BTB 테이블에서 103 -> 100이라는 항목을 지운다.
정리
- 우리는 총 10번의 분기를 만나 그중 8번의 분기 예측에 성공했다.
- 그렇지만 2번의 분기 예측에 실패했는데, 이 실패 예측을 줄일 수 있다.
- 방법은 실패를 두번에 걸쳐서 하는 방법이다.
- 예측에 실패했다고 바로 버리지 않고 연속적으로 한 번의 추가적인 실패가 발생했을 경우에만 BTB에서 제거한다.
- 이를 2비트 상태를 적용한다고도 한다.
Branch History Table
- BHT는 BTB와 비슷하다. 다만 BHT는 history를 기록한다는 점에서 다르다.
- Decode 단계에서 Branch라는 것이 밝혀지면 BTH에 가서 Next pc를 예측한 것이 일치하는지 확인하고 아니라면 Fetch로 redirect시킨다.
- 오로지 Branch History Table은 Decode단계에서만 사용할 수 있는데 왜냐하면 Decode되야만이 Branch 명령어인지 확인할 수 있기 때문이다.
- BHT를 사용하더라도 Fetch단계에서 next pc를 예측하는 것은 꼭 필요하다.
- 또한 BHT는 Execute 단계에서만 업데이트 될 수 있다.
댓글
댓글 쓰기