Branch effect reduction techniques
- 1 May 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in Computer
- Vol. 30 (5) , 71-81
- https://doi.org/10.1109/2.589913
Abstract
The insatiable demand of both old and new applications demand improved capabilities. Developers must exploit parallelism for all types of programs to realize gains. Multiprocessor, multithreaded, vector, and dataflow computers achieve speedups up to the 1,000's for programs with large amounts of data parallelism or independent control flow. General-purpose code, however, has many conditional branches, irregular control flow, and much less data parallelism. These code characteristics and their detrimental consequences, in the form of branch effects, have severely limited the parallelism that can be exploited. Branch effects result from the uncertainties in the way branches execute. This article surveys techniques to reduce branch effects and describes their relative merits, including examples from commercial machines. Branch effect reduction techniques can be implemented in hardware, software, or both to free up more parallelism and speed up the execution of general-purpose code. Research is bearing fruit: Speedups of 10 or more are being demonstrated in research simulations and may be realized in hardware within a few years.Keywords
This publication has 11 references indexed in Scilit:
- Limits of Control Flow on ParallelismPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- A study of branch prediction strategiesPublished by Association for Computing Machinery (ACM) ,1998
- Disjoint eager execution: an optimal form of speculative executionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1995
- Multiscalar processorsPublished by Association for Computing Machinery (ACM) ,1995
- Improving the accuracy of static branch prediction using branch correlationPublished by Association for Computing Machinery (ACM) ,1994
- A theory of reduced and minimal procedural dependenciesIEEE Transactions on Computers, 1991
- Two-level adaptive training branch predictionPublished by Association for Computing Machinery (ACM) ,1991
- The Cydra 5 departmental supercomputer: design philosophies, decisions, and trade-offsComputer, 1989
- A VLIW architecture for a trace scheduling compilerIEEE Transactions on Computers, 1988
- The Inhibition of Potential Parallelism by Conditional JumpsIEEE Transactions on Computers, 1972