Branch prediction paper available

tom@derby.cs.wisc.edu (Tom Ball)
Mon, 15 Feb 1993 19:18:01 GMT

          From comp.compilers

Related articles
Branch prediction paper available tom@derby.cs.wisc.edu (1993-02-15)
| List of all articles for this month |

Newsgroups: comp.compilers,comp.arch
From: tom@derby.cs.wisc.edu (Tom Ball)
Keywords: architecture, report, FTP
Organization: University of Wisconsin, Madison -- Computer Sciences Dept.
Date: Mon, 15 Feb 1993 19:18:01 GMT

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.
--


Post a followup to this message

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