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
Abstract
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.