University of
Houston
Department of Computer
Science
In partial fulfillment of
the Requirements for the Degree of
Master of Science
Qingdong Wang
will
defend her thesis
Applying
Evolutionary Programming to A Hybrid Branch Prediction
Method with Switch-Counter
Abstract
Modern high-performance
computer architectures require extremely accurate branch prediction to overcome
the performance limitations of conditional branches. A hybrid branch prediction
with switch-counter method was recently proposed to improve branch prediction.
This method applies a rule-based program to distinguish four different
instruction classes during compilation and then uses different predicators for
each class in run time. In this thesis, we apply the Evolutionary Programming
(EP) technique to optimize the branch classification, which will result in
higher prediction accuracy. The performance of the hybrid branch prediction with
EP method is evaluated on SPEC2000, SPEC95 and MediaBench benchmarks.
The branch classification
problem can be formulated to be a nonlinear and non-convex optimization problem,
which may have multiple local optimal points. The experimental results show that
the EP algorithms can handle a large range of benchmarks and provide impressive
improvement for the prediction accuracy, the EP algorithms are robust. The
optimal solutions obtained by applying the EP algorithms on the training data
sets are validated using the testing data sets. We analyze how the EP algorithms
refine the distributions of the instructions with regular history pattern and
irregular history pattern which affect the prediction accuracy. It is observed
that the benchmarks that have larger distributions of instructions of regular
and irregular history patterns, the EP algorithms can gain more improvements for
prediction accuracy.
Date:
Time:
10:00 AM
Place: 550-PGH
Faculty,
students, and the general public are invited.
Thesis Advisor: Dr. Willis King