Branch predictor has become an indispensable part for deeply pipelined processors to achieve high in-struction per cycle (IPC) rates in more aggressive clock frequency. Performance of branch prediction algorithm is mainly dependent on the branch prediction hit ratio. Many prediction algorithms with higher and higher prediction hit ratio have been proposed for many decades. However it does not always guarantee the expected overall performance of program control-flow in processor. Complicated predicting process and extra memory requirements accompanied by higher hit-ratio makes it unattractive when implementing it on silicon.
Consequently, most branch predictor realized in silicon nowadays is based on dynamic two-level branch prediction technique, and this methodology is considered as a very specific solution to this branch prediction problem.
Conventional dynamic two-level branch predictions are based on utilizing values existing in the processor. PC and branch history are major ingredients in conditional branch prediction since they are highly correlated to the program flow.
In this thesis, we propose a new branch prediction method that utilizing program status value. NZCV, which is directly related to the result of conditional branch, can be another good ingredient in prediction process. However NZCV has not been mentioned even once in any dynamic branch prediction algorithms. Proposed algorithm is based on the two-level branch prediction that utilizing 2-bit counter table with globally used history shift register. By using different indexing scheme utilizing NZCV, it raises prediction hit-ratio higher than gshare. All through the simulation results, we show that the branch prediction hit ratio can be im-proved than gshare in most of the cases, with negligible hardware degradation. Simulation results are based on the Simple-scalar Alpha-DEC version 3.0e and simulated benchmark is SPEC 95 and 2000.
본 논문에서는 마이크로프로세서의 IPC(Instruction per cycle)를 높이기 위한 조건 분기예측의 새로운 알고리즘을 제시 하였다. 분기예측 알고리즘은 주로 예측성공의 확률을 높이는데 그 연구 방향이 집중 되어 왔다. 하지만 더 높은 확률로 예측 하기 위한 연산의 복잡도가 점점 높아지고, 테이블의 크기도 커질 수 밖에 없기 때문에 결과적으로는 전체 성능에 큰 효과를 불러오기는 쉽지 않았다.
기존의 분기예측 알고리즘은 프로그램 카운터와 조건 분기의 결과값을 기록 해 놓았다가 예측에 사용하는 방식을 취해 왔다. 그 두 개의 값을 이용한 수많은 조건 분기 예측 알고리즘이 십 수년간 제시 되어 왔지만, 하드웨어적인 복잡도 및 온-칩 메모리 사이즈를 고려 하였을 때 가장 적합한 알고리즘은 2-레벨 적응 예측이 가능한 예측기 이고 프로세서 업계에서도 이를 기본으로 한 예측기가 주로 사용 되어 오고 있다. 이러한 방식으로 고착화 된 예측기의 성능을 뛰어 넘기 위해서는 근본적인 변화가 필요함을 생각하여 새로운 값을 예측에 사용하기로 하였다.
본 논문에서는 프로세서에서 생성 가능한 플래그 값(N,Z,C,V)을 추가적으로 도입하여 분기예측에 사용하는 알고리즘을 제시 하였다. NZCV는 Negative, Zero, Carry 그리고 Over-flow의 약자로 현재 대부분의 마이크로 프로세서에서 더 빠른 조건 수행을 위해 사용되고 있는 플래그 값이다. 제안된 방식은 분기조건을 판별하는데 있어 NZCV플래그가 이상적인 환경에서 예측의 정확도를 크게 향상 시킬 수 있음을 실험적으로 보였다. 파이프라인이 적용된 프로세서의 경우에는 지연된 플래그 만을 이용할 수 있어서 예측의 정확도가 이상적인 경우보다 낮아 지지만, 기존 방식 보다 향상된 결과를 얻을 수 있었다.
