Entry Calder:1997:ESB from toplas.bib

Last update: Tue May 1 02:05:46 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Calder:1997:ESB,
  author =       "Brad Calder and Dirk Grunwald and Michael Jones and
                 Donald Lindsay and James Martin and Michael Mozer and
                 Benjamin Zorn",
  title =        "Evidence-Based Static Branch Prediction Using Machine
                 Learning",
  journal =      j-TOPLAS,
  volume =       "19",
  number =       "1",
  pages =        "188--222",
  month =        jan,
  year =         "1997",
  CODEN =        "ATPSDT",
  ISSN =         "0164-0925 (print), 1558-4593 (electronic)",
  ISSN-L =       "0164-0925",
  bibdate =      "Wed Mar 12 08:06:48 MST 1997",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/toplas.bib",
  URL =          "http://www.acm.org/pubs/citations/journals/toplas/1997-19-1/p188-calder/",
  abstract =     "Correctly predicting the direction that branches will
                 take is increasingly important in today's wide-issue
                 computer architectures. The name {\em program-based\/}
                 branch prediction is given to static branch prediction
                 techniques that base their prediction on a program's
                 structure. In this article, we investigate a new
                 approach to program-based branch prediction that uses a
                 body of existing programs to predict the branch
                 behavior in a new program. We call this approach to
                 program-based branch prediction {\em evidence-based
                 static prediction}, or ESP. The main idea of ESP is
                 that the behavior of a corpus of programs can be used
                 to infer the behavior of new programs. In this article,
                 we use neural networks and decision trees to map static
                 features associated with each branch to a prediction
                 that the branch will be taken. ESP shows significant
                 advantages over other prediction mechanisms.
                 Specifically, it is a program-based technique; it is
                 effective across a range of programming languages and
                 programming styles; and it does not rely on the use of
                 expert-defined heuristics. In this article, we describe
                 the application of ESP to the problem of static branch
                 prediction and compare our results to existing
                 program-based branch predictors. We also investigate
                 the applicability of ESP across computer architectures,
                 programming languages, compilers, and run-time systems.
                 We provide results showing how sensitive ESP is to the
                 number and type of static features and programs
                 included in the ESP training sets, and we compare the
                 efficacy of static branch prediction for subroutine
                 libraries. Averaging over a body of 43 C and Fortran
                 programs, ESP branch prediction results in a miss rate
                 of 20\%, as compared with the 25\% miss rate obtained
                 using the best existing program-based heuristics.",
  acknowledgement = ack-nhfb,
  fjournal =     "ACM Transactions on Programming Languages and
                 Systems",
  keywords =     "algorithms; languages; measurement; performance",
  subject =      "{\bf I.2.6}: Computing Methodologies, ARTIFICIAL
                 INTELLIGENCE, Learning, Parameter learning. {\bf C.4}:
                 Computer Systems Organization, PERFORMANCE OF SYSTEMS,
                 Measurement techniques. {\bf D.3.4}: Software,
                 PROGRAMMING LANGUAGES, Processors, Compilers. {\bf
                 D.3.4}: Software, PROGRAMMING LANGUAGES, Processors,
                 Optimization. {\bf I.2.6}: Computing Methodologies,
                 ARTIFICIAL INTELLIGENCE, Learning, Connectionism and
                 neural nets.",
}

Related entries