Type of Document Dissertation Author Michael, Christopher Joseph URN etd-04142010-005228 Title The Weakening of Branch Predictor Performance as an Inevitable Side Effect of Exploiting Control Independence Degree Doctor of Philosophy (Ph.D.) Department Electrical & Computer Engineering Advisory Committee
Advisor Name Title Koppelman, David M. Committee Chair Peng, Lu Committee Member Ramanujam, Jagannathan Committee Member Sterling, Thomas L. Committee Member Trahan, Jerry L. Committee Member Giaime, Joseph A. Dean's Representative Keywords
- Branch Prediction
- Computer Architecture
Date of Defense 2010-03-29 Availability unrestricted AbstractMany algorithms are inherently sequential
and hard to explicitly parallelize. Cores designed to aggressively
handle these problems
exhibit deeper pipelines and wider fetch widths to exploit instruction-level
parallelism via out-of-order execution. As these parameters increase, so does
the amount of instructions fetched along an incorrect path when a branch is
Many of the instructions squashed after a branch are
control independent, meaning they will be fetched regardless of whether the
candidate branch is taken
or not. There has been much research in retaining these control independent
instructions on misprediction of the candidate branch.
This research shows that there is potential for exploiting control
independence since under favorable
circumstances many benchmarks can exhibit 30%
or more speedup. Though these control independent processors are meant to lessen
the damage of misprediction, an inherent side-effect of fetching out of order,
branch weakening, keeps realized speedup from reaching its potential.
This thesis introduces, formally defines, and
identifies the types of branch weakening. Useful information is provided to
develop techniques that may reduce weakening. A classification is provided that
measures each type of weakening to help better determine potential speedup of
control independence processors.
Experimentation shows that certain applications suffer greatly from
weakening. Total branch mispredictions increase by 30% in several cases.
Analysis has revealed two broad causes of weakening: changes in branch predictor
update times and changes in the outcome history used by branch predictors.
Each of these broad causes are classified into more specific causes, one of
which is due to the loss of nearby correlation data and cannot be avoided.
classification technique presented in this study measures that
the weakening in the selected SPEC CPU 2000 benchmarks are of this type while
40% involve other changes in outcome history. The remaining 15% is caused by
changes in predictor update times.
In applying fundamental
techniques that reduce weakening, the Control Independence Aware
Branch Predictor is developed. This predictor reduces weakening for the majority
of chosen benchmarks. In doing so, a control independence
processor, snipper, to
attain significantly higher speedup for 10 out of 15 studied benchmarks.
Filename Size Approximate Download Time (Hours:Minutes:Seconds)
28.8 Modem 56K Modem ISDN (64 Kb) ISDN (128 Kb) Higher-speed Access draft.pdf 366.58 Kb 00:01:41 00:00:52 00:00:45 00:00:22 00:00:01
If you have questions or technical problems, please Contact LSU-ETD Support.