Dynamic Branch Prediction Overview

Branch prediction은 크게 static과 dynamic으로 나눌 수 있다.

static branch prediction의 경우 compile time에 compiler가 해주고,

dynamic branch prediction의 경우 runtime에 Hardware가 해준다.

 

그 중 하드웨어에 의한 dynamic branch prediction에 대해 알아보자.

 

BHT (Branch History Table)을 사용하는데,브랜치가 이전에 take했는지, 안했는지 과거를 기록하여 예측하는 방식이다.

 

taken(T) / not taken(NT) 여부를 몇 비트로 기록할지,모든 브랜치의 과거 기록을 통합하여 기록할지 또는 개별 브랜치의 과거 기록을 기록할지 등에 따라몇가지 종류의 predictor가 있다.

 

prediction에 실패하는 경우도 2가지로 나뉜다.첫번째는 예측이 실패하는 경우이다. (wrong prediction)T로 예측하고 진행했는데 뒤늦게 나온 결과가 NT라 하는 예가 해당된다.두번째는 hashing conflict로 인해 다른 브랜치의 예측을 참조하게 된 경우이다. (wrong branch)모든 브랜치의 과거를 기록하려면 BHT가 너무 커지기 때문에, addr의 LSB 일부를 사용하는 등의방법을 취하는데, 이럴 경우 hashing conflict를 피할 수 없기 때문에 발생한다.

 

BTB (Branch Target Buffers)란 작은 cache like 메모리로,정확한 branch 주소(cache의 tag 역할)와 target 주소(cache의 data 역할)를 저장하는 버퍼이다.앞서 hashing conflict를 감수할 만큼, BHT의 크기를 줄이는 데에 신경을 쓰는데왜 BTB에 와서는 정확한 이름표인 tag를 필요로 할까?

BHT는 단순히 브랜치를 할지, 말지에 대해서 예측하고 실패하면 stall cycle이 생기는 "아쉬운" 수준의 결과를 낳는데에 반해,

BTB는 target 주소를 알려주기 때문에 잘못된 주소를 fetch하게 될 경우, page fault 등의 심각한 문제를 일으킬 수 있기 때문이다.

 

---

대학원에 진학해서 고급 컴퓨터 구조 수업을 듣게 되어,

학부때 배운 내용을 복습해보았다.

석사 2년 화이팅 >_< :)