Title page for ETD etd-04142010-005228


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

mispredicted.

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.

The

classification technique presented in this study measures that

45% of

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.

Files
  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

Browse All Available ETDs by ( Author | Department )

If you have questions or technical problems, please Contact LSU-ETD Support.