Re: Branch prediction (was: eliminating array bounds checking overhead)

David Gregg <dave@complang.tuwien.ac.at>
12 May 2000 22:32:47 -0400

          From comp.compilers

Related articles
Re: Re: eliminating array bounds checking overhead patrykz@ilion.eu.org (Patryk Zadarnowski) (2000-05-01)
Branch prediction (was: eliminating array bounds checking overhead) patrykz@ilion.eu.org (Patryk Zadarnowski) (2000-05-04)
Re: Branch prediction (was: eliminating array bounds checking overhead anton@mips.complang.tuwien.ac.at (2000-05-08)
Re: Branch prediction (was: eliminating array bounds checking overhead dave@complang.tuwien.ac.at (David Gregg) (2000-05-12)
| List of all articles for this month |

From: David Gregg <dave@complang.tuwien.ac.at>
Newsgroups: comp.compilers
Date: 12 May 2000 22:32:47 -0400
Organization: Vienna University of Technology, Austria
References: 00-05-006 00-05-018
Keywords: architecture, performance

> [I was under the impression that guessing that backward branches are
> taken and forward branches aren't does surprisingly well. -John]


According to a paper by Gus Uht a few years back, predction schemes
have accuracies very roughly as follows:


Predict all branches not taken: 40 - 60%
Predict backwards taken, forward not: 65%
Predict most frequent direction in profiling run: 75%
One bit dynamic predictor 77 - 79%
Two bit dynamic predictor 78 - 89%
Two level dynamic predictor 94%


The figure for profiling and the two bit dynamic predictor look a
bit on the low side to me. But the numbers give a rough idea of the
relative strength of the major different predictors.


David.


The reference for the paper is: A. K. Uht, V. Sindagi and S. Somanathan.
"Branch Effect Reduction Techniques". COMPUTER, IEEE, 30(5):71-81, May,
1997.


Post a followup to this message

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