Report Number: CSL-TR-90-411
Institution: Stanford University, Computer Systems Laboratory
Title: Branch strategies: modeling and optimization
Author: Dubey, Pradeep K.
Author: Flynn, Michael J.
Date: February 1990
Abstract: Instruction dependency introduced by conditional branch
instructions, which is resolved only at run-time, can have
severe performance impact on pipelined machines. A variety of
strategies are in wide use to minimize this impact.
Additional instruction traffic generated by these branch
strategies can also have an adverse effect on the system
performance. Therefore, in addition to the likely reduction a
branch prediction strategy offers in average branch delay,
resulting excess i-traffic can be an important parameter in
evaluating its overall effectiveness. The objective of this
paper is twofold: to develop a model for different approaches
to the branch problem and to help select an optimal strategy
after taking into account the additional i-traffic generated
by the i-buffering.
The model presented provides a flexible tool for comparing
different branch strategies in terms of the reduction it
offers in average branch delay and also in terms of the
associated cost of wasted instruction fetches. This
additional criterion turns out to be a valuable consideration
in choosing between two almost equally performing strategies.
More importantly, it provides a better insight into the
expected overall system performance. Simple
compiler-support-based low implementation-cost strategies can
be very effective under certain conditions. An active branch
prediction scheme based on loop buffer can be as competitive
as a branch-target-buffer based strategy.