One of the main obstacles in designing of today`s wide-issue, deeply-pipelined superscalar processors is the conditional branch instruction. This is because the outcome of a conditional branch instruction is resolved in the late stage of a pipeline, which results in wasted processor cycles due to pipeline stalls. Various approaches have been proposed to solve the branch problem, including dynamic branch prediction that is probably the most popular one, because it gives good performance and can be implemented without any modification of existing binary programs. Dynamic branch prediction predicts the outcome of a conditional branch instruction using branch history information collected at run-time and allows instructions from predicted path to be executed speculatively while the conditional branch instruction is being resolved. If a misprediction occurs, the speculatively executed instructions are thrown away and instruction fetch restarts from the correct path.
Modern superscalar processors tend to have wider issue width and deeper pipeline depth to exploit more and more of the instruction level parallelism (ILP). In these superscalar processors, the performance degradation due to a misprediction becomes more severe, since the amount of speculative work that must be thrown away in the event of a misprediction increases significantly as the issue width and the pipeline depth increase. Therefore, wide-issue, deeply-pipelined modern superscalar processors require very accurate branch prediction to fully exploit their potential performance.
Two-level branch predictors, introduced by Yeh & Patt in 1991, are generally considered to be good solutions to achieve the desired high prediction accuracy. Actually, novel variations of two-level branch predictors have been adopted by various commercial microprocessors, such as Intel Pentium-Pro and DEC Alpha 21264. Two-level branch predictors can be classified broadly as either global history-based branch predictors or self history-based branch predictors depending on the sort of branch history information they use.
Global history-based branch predictors can take advantage of branch correlation information, but they suffer from a severe destructive aliasing problem. Many researchers have focused on alleviating the aliasing problem and, as a result, many brilliant variations of global history-based branch predictors have been proposed. However, there has been little research on self history-based branch predictors. It is important to develop improved self history-based branch predictors, as they tend to be implemented in commercial microprocessors, such as the Intel Pentium-Pro and its successors.
Branch correlation is known to be very useful information to make accurate branch prediction. Until now, branch correlation has been exploited only through the global history, but there has been no way to exploit it using the self history. In this thesis, we introduce a correlation detector, called the BHT cache, which makes self history-based branch predictors exploit branch correlation. Trace-driven simulations were carried out using the IBS-Ultrix benchmarks to evaluate the performance of the self history-based branch predictors incorporating the BHT cache. Our simulation results show that the self history-based branch predictors incorporating the BHT cache can take advantage of branch correlation information resulting in improved prediction accuracy at a very small extra hardware cost.
조건부 분기 명령어의 분기 여부는 파이프라인의 늦은 단계에서 결정되기 때문에 프로세서의 사이클을 낭비하는 파이프라인 지연이 발생하게 되고, 이는 프로세서의 성능 저하의 큰 원인이 된다. 특히 더욱 깊은 파이프라인과 여러 개의 명령어를 동시에 수행하는 슈퍼스칼라 프로세서에서는 분기 명령어로 인한 성능 저하가 더욱 심각해진다.
이러한 분기 명령어로 인한 성능 저하 문제를 해결하기 위해서 여러 가지 방법들이 제안되었는데, 그 중에서 동적 분기 예측 방식이 가장 좋은 성능을 보이고 또한 기존 프로그램들의 수정 없이 사용할 수 있기 때문에 가장 많이 사용되고 있다. 동적 분기 예측 방식은 프로그램 실행 시의 분기 역사 정보를 이용해서 분기 명령어의 분기 여부를 예측하는 방식이다. 이러한 분기 예측 방식은 분기 여부가 결정되기 전에 예측된 분기 방향의 명령어들을 미리 수행할 수 있게 함으로써 파이프라인 지연을 줄일 수 있다. 그러나, 만약 분기 예측이 틀렸을 경우에는 그 동안 미리 수행했던 모든 명령어들을 버리고 정확한 분기 방향의 명령어들을 다시 수행해야 한다. 그러므로, 분기 예측의 정확도는 프로세서의 성능에 직접적인 영향을 미치게 된다. 특별히, 최근의 슈퍼스칼라 프로세서에서는 분기 예측이 틀렸을 경우 버리고 다시 수행해야 하는 명령어의 수가 상당히 많기 때문에 더욱 정확한 분기 예측이 필요하다.
1991 년에 Yeh와 Patt이 처음으로 제안한 이단계 분기 예측기는 이러한 높은 분기 예측 정확도를 얻기 위한 좋은 대안으로 많이 사용되고 있다. 실제로 Intel Pentium-Pro 와 DEC Alpha 21264 등의 상용 마이크로프로세서들에서 이단계 분기 예측기들이 채용되어서 사용되고 있다. 이단계 분기 예측기는 사용하는 분기 역사의 종류에 따라 크게 전역역사 기반 분기 예측기와 자신역사 기반 분기 예측기로 분류할 수 있다.
전역역사 기반 분기 예측기는 분기 명령어 상호관계 정보를 이용할 수 있어서 좋은 성능을 보이지만 여러 개의 분기 명령어들이 하나의 예측자를 동시에 사용하는 충돌 문제 때문에 심각한 성능 저하가 발생한다. 이러한 전역역사 기반 분기 예측기에서의 충돌 문제를 해결하기 위해서 많은 연구들이 진행되어 왔고, 그 결과 여러 가지 우수한 전역역사 기반 분기 예측기들이 제안되었다. 그러나, 지금까지 자신역사 기반 분기 예측기에 대한 연구는 거의 없었다. 하지만 Intel Pentium-Pro와 같은 상용 마이크로프로세서에서도 자신역사 기반 분기 예측기를 채용했듯이, 좀 더 좋은 성능을 보이는 자신역사 기반 분기 예측기에 대한 연구도 매우 중요하다.
전역역사 기반 분기 예측기에서 이용하고 있는 분기 명령어 상호관계 정보는 정확한 분기 예측에 매우 유용한 정보이다. 지금까지는 이러한 분기 명령어 상호관계 정보를 전역역사를 통해서만 이용할 수 있었고, 자신역사를 통해서는 이용할 수 없었다. 본 논문에서는 자신역사 기반 분기 예측기에서도 분기 명령어 상호관계를 이용할 수 있게 해 주는 분기 명령어 상호관계 검출기인 BHT cache를 제안한다. BHT cache를 채용한 자신역사 기반 분기 예측기의 성능을 분석하기 위해서 IBS-Ultrix 벤치마크를 이용해서 시뮬레이션을 수행하였다. 시뮬레이션 결과, 매우 작은 추가 하드웨어 비용으로 BHT cache를 채용한 자신역사 기반 분기 예측기가 분기 명령어 상호관계를 이용해서 더 좋은 예측 정확도를 보임을 확인하였다.
