Abstract
Indirect branch prediction is a performance limiting factor for current computer systems, preventing superscalar processors from exploiting the available ILP. Indirect branches are responsible for 55.7% of mispredictions in our benchmark set, although they only stand for 15.5% of dynamic branches. Moreover, a 10.8% average IPC speedup is achievable by perfectly predicting all indirect branches.
The Multi-Stage Cascaded Predictor (MSCP) is a mechanism proposed for improving indirect branch prediction. In this paper, we show that a MSCP can replace a BTB and accurately predict the target address of both indirect and non-indirect branches. We do a detailed analysis of MSCP behavior and evaluate it in a realistic setup, showing that a 5.7% average IPC speedup is achievable.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
B. Calder and D. Grunwald. Reducing indirect function call overhead in C++ programs. 21st Symp. on Principles of Programming Languages, 1994.
B. Calder and D. Grunwald. Fast accurate instruction fetch and branch prediction. 21st Intl. Symp. on Computer Architecture, 1994.
P. Y. Chang, E. Hao and Y. Patt. Target prediction for indirect jumps. 24th Intl. Symp. on Computer Architecture, 1997.
K. Driesen and U. Hölzle. Accurate indirect branch prediction. 25th Intl. Symp. on Computer Architecture, 1998.
K. Driesen and U. Hölzle. The cascaded predictor: economical and adaptive branch target prediction. 31st Intl. Symp. on Microarchitecture, 1998.
K. Driesen and U. Hölzle. Multi-Stage Cascaded Prediction. 5th Intl. Euro-Par Conf., 1999
D. Kaeli and P. Emma. Branch history table prediction of moving target branches due to subroutine returns. 18th Intl. Symp. on Computer Architecture, 1991.
J. Lee and A. Smith. Branch prediction strategies and branch target buffer design. IEEE Computer Magazine, 17(1), 1984.
S. McFarling Combining branch predictors. Digital Equipment Corporation, WRL Technical Note TN-36, 1993.
P. Michaud, A. Seznec and R. Uhlig. Trading conflict and capacity aliasing in conditional branch predictors. 24th Intl. Symp. on Computer Architecture, 1997.
R. Nair. Dynamic path-based branch correlation. 28th Intl. Symp. on Microarchitecture, 1995.
C. Perleberg and A. Smith. Branch target buffer design and optimization. IEEE Transactions on Computers, 42(4), 1993.
O. J. Santana, A. Falcón, E. Fernández, P. Medina, A. Ramírez and M. Valero. Analysis and evaluation of the Multi-Stage Cascaded Predictor. Departamento de Arquitectura de Computadores, UPC, Technical Report DAC-UPC-2001-24, 2001.
J. Stark, M. Evers and Y. Patt. Variable length path branch prediction. 8th Intl. Conf. on Architectural Support for Programming Languages and Operating Systems, 1998.
T. Y. Yeh and Y. Patt. Two level adaptive training branch prediction. 24th Intl. Symp. on Microarchitecture, 1991.
T. Y. Yeh and Y. Patt. A comprehensive instruction fetch mechanism for a processor supporting speculative execution. 25th Intl. Symp. on Microarchitecture, 1995
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Santana, O.J., Falcón, A., Fernández, E., Medina, P., Ramírez, A., Valero, M. (2002). A Comprehensive Analysis of Indirect Branch Prediction. In: Zima, H.P., Joe, K., Sato, M., Seo, Y., Shimasaki, M. (eds) High Performance Computing. ISHPC 2002. Lecture Notes in Computer Science, vol 2327. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47847-7_13
Download citation
DOI: https://doi.org/10.1007/3-540-47847-7_13
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43674-4
Online ISBN: 978-3-540-47847-8
eBook Packages: Springer Book Archive