Reducing the Ill Effects of Branches

- A Tutorial on Instruction Level Parallelism Enhancements -

- To appear in: IEEE COMPUTER -

Augustus K. Uht, University of Rhode Island
Vijay Sindagi, Texas Instruments
Sajee Somanathan, ADE Corporation

April 26, 1996


In order to significantly improve processor performance, the parallelism among machine instructions must be exploited. Conditional branches are the major restrictors of this parallelism, especially since they are widespread in general-purpose programs. Until recently, the best Instruction Level Parallelism (ILP) methods known realized only about a factor of 2 to 3 speedup over purely sequential computers. The uncertainties of which way branches will execute are the culprits, and are called branch effects. After an introduction to instruction level parallelism, current Branch Effect Reduction Techniques (BERT's) are described and compared, both qualitatively and quantitatively. Lastly, a new BERT developed by the authors, called Disjoint Eager Execution (DEE), is described and evaluated. Simulation results indicating potential order-of-magnitude speedups for one type of DEE are presented.

This work is due to be published by the IEEE. Copyright may be transferred without notice, after which this version will be superseded. Parts of this paper have previously appeared.