분기 정보의 추측적 사용과 효율적 복구 기법
Branch Prediction with Speculative History and Its Effective Recovery Method
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
분기 명령어에 대한 예측 정확도는 시스템의 전체 성능 향상에 중대한 영향을 미친다. 분기 정보의 추측적 사용은 미완료 분기에 대한 히스토리 정보를 추측적으로 사용하여 분기 예측을 수행한다. 이러한 방식은 분기 명령어의 가장 최근 기록을 일관되게 사용할 수 있도록 도와주기 때문에 분기 예측의 정확도 향상에 크게 기여한다. 하지만 미완료 분기 히스토리는 올바르지 못한 정보일 수 있으며, 이런 경우 적절한 복구 기법이 필요하다. 이를 위해 본 논문에서는 분기 정보의 추측적 사용에 대한 성능 향상의 정도를 살피고, 분기 정보의 추측적 사용에 대한 필요성을 제시한다. 아울러, 분기 정보의 추측적 사용으로 인해 요구되는 적절한 복구 기법을 제안한다. 제안된 기법은 전역 분기 히스토리를 사용하는 분기 예측기와 지역 분기 히스토리를 사용하는 분기 예측기에 각각 적용 될 수 있는 방식들이다. 모의실험을 통해 본 논문에서 제안된 방식의 성능을 분석한 결과, 본 논문에서 제안된 기법이 최대 5.64%의 성능향상을 제공하였다. 아울러 프로그램 수행의 정확성을 해치지 않으면서 기존의 연구와 비교하여 90% 이상의 하드웨어 요구량의 감소를 가져왔다.
Abstract
Branch prediction accuracy is critical for system performance in modern microprocessor architectures. The use of speculative update branch history provides substantial accuracy improvement in branch prediction. However, speculative update branch history is the information about uncommitted branch instruction and thus it may hurts program correctness, in case of miss-speculative execution. Therefore, speculative update branch history requires suitable recovery mechanisms to provide program correctness as well as performance improvement. In this paper, we propose recovery logics for speculative update branch history. The proposed solutions are recovery logics for both global history and local history. In simulation results, our solution provides performance improvement up to 5.64%. In addition, it guarantees the program correctness and almost 90% of additional hardware overhead is reduced, compared to previous works.
참고문헌 (22)
- R. Tomasulo, "An efficient algorithm for exploiting multiple arithmetic units", IBM J. Research and Development, 11(1), pp.25~33 (1967)
- A. R. Talcott, "The impact of unresolved branches on branch prediction scheme performance", in Proceedings of the 21st ISCA, pp.12~21 (1994)
- E. Hao, "The effect of speculatively updating branch history on branch prediction accuracy, revisited", in Proceedings of the 27th Annual International Symposium onMicroarchitecture, pp.228~232 (1994)
- E. Sprangle, "Increasing processor performance by implementing deeper pipelines", In Proc. 29th Int’l Symp. on Computer Architecture, pp.25~34 (2002)
- Yeh, T. Y., "Two-level adaptive branch prediction", In Proceedings of the 24th ACM, 1991, 51~61
- T.-Y. Yeh, "Alternative implementations of two-level adaptive branch prediction", In Proc. of the 19th ISCA, pp.124~134 (1992)
- E. Hao, "The effect of speculatively updating branch history on branch prediction accuracy, revisited", in Proceedings of the 27th MICRO, pp.228~232 (1994)
- A. R. Talcott, "The impact of unresolved branches on branch prediction scheme performance", in Proceedings of the 21st Annual International Symposium on Computer Architecture, pp.12~21 (1994)
- K. Skadron, "Speculative updates of local and global branch history: A quantitative analysis", JILP, 2 (2000)
- A. Seznec, "Design tradeoffs for the ev8 branch predictor", In Proc. of the 29th ISCA, pp.295~306 (2002)
- M. Evers, "An analysis of correlation and predictability: What makes two-level branch predictors work", In Proceedings of the 25th Annual Intl. Symposium on Computer Architecture, pp.52~61 (1998)
- S. Sechrest, "Correlation and Aliasing in Dynamic Branch Predictors", in Proceedings of the 23rd ISCA, pp.22~32 (1996)
- A. R. Talcott, "The Influence of Branch Prediction Table Interference on Branch Prediction Scheme Performance", International Conference on Parallel Architectures and Compilation Techniques (1995)
- Chih-Chieh Lee, "The Bi-Mode Branch Predictor", International Symposium on Microarchitecture (1997)
- Eric Sprangle, "The Agree Predictor: A Mechanism for Reducing Negative Branch History Interference", Intl. Symposium on Computer Architecture (1997)
- McFarling, S., "Combining branch predictors", Tech. Rep. TN-36m Digital Western Research Lab (1993)
- S. Kim, "Analyzing the working set characteristics of branch execution", in Proceedings of the 31st Annual ACM, 1998, 49~58
- R. E. Kessler, "The Alpha 21264 Microprocessor", IEEE Micro, 19(2), pp.24~36 (1999)
- E. J. McLellan, "The Alpha 21264 Microprocessor Architecture", In Proceedings of the International Conference on Computer Design, pp.90~95 (1998)
- S. Jourdan, "Recovery requirements of branch prediction storage structures in the presence of mispredicted-path execution", International Journal of Parallel Programming, 25, pp.363~383 (1997)
- D. Burger, "Evaluating future micro-processors: the SimpleScalar tool set", Tech. Report TR-1308 Univ. of Wisconsin-Madison Computer Sciences (1997)
- "SPEC CPU2000 Benchmarks"[URL]