Branch prediction paper available

A new technical report on heuristics for program-based static branch
prediction is available via anonymous ftp from ftp.cs.wisc.edu in
directory "tech-reports/reports/93" as file "tr1137.ps.Z" The file is
compressed postscript.




Thomas Ball Computer Sciences Dept.
tom@cs.wisc.edu University of Wisconsin-Madison


------------------------------------------------------------------------------
Title: "Branch Prediction for Free"


Thomas Ball and James R. Larus
tom@cs.wisc.edu, larus@cs.wisc.edu
University of Wisconsin-Madison, Comp. Sci. Dept. TR #1137


Abstract:


Many compilers rely on branch prediction to improve program
performance by identifying frequently executed regions and by aiding
in scheduling instructions. *Profile-based* predictors require a
time-consuming and inconvenient compile-profile-compile cycle in
order to make predictions. We present a *program-based* branch
predictor that performs well for a large and diverse set of programs
written in C and Fortran. In addition to using natural loop analysis
to predict branches that control the iteration of loops, we focus on
heuristics for predicting non-loop branches, which dominate the
dynamic branch count of many programs. The heuristics are simple and
require little program analysis, yet they are effective in terms of
coverage and miss rate. Although program-based prediction does not
equal the accuracy of profile-based prediction, we believe it reaches
a sufficiently high level to be useful. Additional type and semantic
information available to a compiler would enhance our heuristics.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.