More Web Proxy on the site http://driver.im/

Article

Loop Termination Prediction

Authors:

Timothy Sherwood,

Brad CalderAuthors Info & Claims

ISHPC '00: Proceedings of the Third International Symposium on High Performance Computing

Pages 73 - 87

Published: 16 October 2000 Publication History

Abstract

Deeply pipelined high performance processors require highly accurate branch prediction to drive their instruction fetch. However there remains a class of events which are not easily predictable by standard two level predictors. One such event is loop termination. In deeply nested loops, loop terminations can account for a significant amount of the mispredictions. We propose two techniques for dealing with loop terminations. A simple hardware extension to existing prediction architectures called Loop Termination Prediction is presented, which captures the long regular repeating patterns of loops. In addition, a software technique called Branch Splitting is examined, which breaks loops with iteration counts above the detection of current predictors into smaller loops that may be effectively captured. Our results show that for many programs adding a small loop termination buffer can reduce the missprediction rate by up to a difference of 2%.

References

[1]

A. Eden and T. Mudge. The YAGS branch prediction scheme. In 31st International Symposium on Microarchitecture, pages 69-77, December 1998.

[2]

A. Farcy, O. Temam, R. Espasa, and T. Juan. Dataflow analysis of branch mispredictions and its application to early resolution of branch outcomes. In 31st International Symposium on Microarchitecture, December 1998.

[3]

Gonzalez and Gonzalez. Control-flow speculation thorough value prediction for superscalar processors. In International Conference on Parallel Architectures and Compilation Techniques, October 1999.

[4]

T. Heil, Z. Smith, and J. E. Smith. Improving branch predictors by correlating on data values. In 32nd International Symposium on Microarchitecture, November 1999.

[5]

IBM. The PowerPC Architecture: A Specification for a New Family of RISC Processors. Morgan Kaufmann Publishers, 1994.

[6]

Intel. IA-64 Application Developer's Architecture Guide. Intel Corporation, Order Number 245188-001, 1999.

[7]

R. E. Kessler, E. J. McLellan, and D. A. Webb. The alpha 21264 microprocessor architecture. In International Conference on Computer Design, October 1998.

[8]

S. McFarling. Combining branch predictors. Technical Report TN-36, Digital Equipment Corporation, Western Research Lab, June 1993.

[9]

C. H. Perleberg and A. J. Smith. Branch target buffer design and optimization. IEEE Transactions on Computers, 42(4):396-412, 1993.

[10]

K. Skadron, P. Ahuja, M. Martonosi, and D. Clark. Improving prediction for procedure returns with return-address-stack repair mechanisms. In Proceedings of the 31st Annual International Symposium on Microarchitecture, pages 259-271, December 1998.

[11]

J. E. Smith. A study of branch prediction strategies. In 8th Annual International Symposium of Computer Architecture, pages 135-148. ACM, 1981.

[12]

A. Srivastava and A. Eustace. ATOM: A system for building customized program analysis tools. In Proceedings of the Conference on Programming Language Design and Implementation, pages 196-205. ACM, 1994.

[13]

J. Tubella and A. Gonzalez. Control speculation in multithreaded processors through dynamic loop detection. In 4th International Symposium on High Performance Computer Architecture, February 1998.

[14]

T. Yeh. Two-level adpative branch prediction and instruction fetch mechanisms for high performance superscalar processors. Ph.D. Dissertation, University of Michigan, 1993.

[15]

T. Yeh and Y. Patt. A comprehensive instruction fetch mechanism for a processor supporting speculative execution. In Proceedings of the 25th Annual International Symposium on Microarchitecture, pages 129-139, December 1992.

[16]

T.-Y. Yeh and Y. Patt. Two-level adaptive branch prediction. In 18th Annual International Symposium on Computer Architecture, pages 51-61, May 1991.

Cited By

Seznec AMiguel JAlbericio JPrvulovic M(2015)The inner most loop iteration counterProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830831(347-357)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830831
García ASantana OFernández EMedina PValero M(2008)LPAProceedings of the 3rd international conference on High performance embedded architectures and compilers10.5555/1786054.1786080(273-287)Online publication date: 27-Jan-2008
https://dl.acm.org/doi/10.5555/1786054.1786080
Moseley TConnors DGrunwald DPeri RBanerjee UMoreira JDubois MStenström P(2007)Identifying potential parallelism via loop-centric profilingProceedings of the 4th international conference on Computing frontiers10.1145/1242531.1242554(143-152)Online publication date: 7-May-2007
https://dl.acm.org/doi/10.1145/1242531.1242554
Show More Cited By

Recommendations

Outer-loop vectorization: revisited for short SIMD architectures
PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques

Vectorization has been an important method of using data-level parallelism to accelerate scientific workloads on vector machines such as Cray for the past three decades. In the last decade it has also proven useful for accelerating multi-media and ...
Loop striping: maximize parallelism for nested loops
EUC'06: Proceedings of the 2006 international conference on Embedded and Ubiquitous Computing

The majority of scientific and Digital Signal Processing (DSP) applications are recursive or iterative. Transformation techniques are generally applied to increase parallelism for these nested loops. Most of the existing loop transformation techniques ...
Termination of Nested Loop
ISCSCT '08: Proceedings of the 2008 International Symposium on Computer Science and Computational Technology - Volume 02

The verification of termination is a difficult problem. While most of the recent work on automated termination proofs focuses on the construction of linear ranking functions for unnested loops, we present an algorithm based on region graphs [1] to prove ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ISHPC '00: Proceedings of the Third International Symposium on High Performance Computing

October 2000

589 pages

ISBN:3540411283

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 16 October 2000

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 23 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Seznec AMiguel JAlbericio JPrvulovic M(2015)The inner most loop iteration counterProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830831(347-357)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830831
García ASantana OFernández EMedina PValero M(2008)LPAProceedings of the 3rd international conference on High performance embedded architectures and compilers10.5555/1786054.1786080(273-287)Online publication date: 27-Jan-2008
https://dl.acm.org/doi/10.5555/1786054.1786080
Moseley TConnors DGrunwald DPeri RBanerjee UMoreira JDubois MStenström P(2007)Identifying potential parallelism via loop-centric profilingProceedings of the 4th international conference on Computing frontiers10.1145/1242531.1242554(143-152)Online publication date: 7-May-2007
https://dl.acm.org/doi/10.1145/1242531.1242554
Santana ORamirez AValero M(2007)Enlarging Instruction StreamsIEEE Transactions on Computers10.1109/TC.2007.7074256:10(1342-1357)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1109/TC.2007.70742
Pajuelo AGonzalez AValero M(2005)Control-Flow Independence Reuse via Dynamic VectorizationProceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers - Volume 0110.1109/IPDPS.2005.154Online publication date: 4-Apr-2005
https://dl.acm.org/doi/10.1109/IPDPS.2005.154
Sherwood TCalder B(2001)Automated design of finite state machine predictors for customized processorsACM SIGARCH Computer Architecture News10.1145/384285.37925429:2(86-97)Online publication date: 1-May-2001
https://dl.acm.org/doi/10.1145/384285.379254
Sherwood TCalder BStenström P(2001)Automated design of finite state machine predictors for customized processorsProceedings of the 28th annual international symposium on Computer architecture10.1145/379240.379254(86-97)Online publication date: 1-Jun-2001
https://dl.acm.org/doi/10.1145/379240.379254

View Options

View options

Media

Figures

Other

Tables

View Table of Contents