|Re: Re: eliminating array bounds checking overhead firstname.lastname@example.org (Patryk Zadarnowski) (2000-05-01)|
|Branch prediction (was: eliminating array bounds checking overhead) email@example.com (Patryk Zadarnowski) (2000-05-04)|
|Re: Branch prediction (was: eliminating array bounds checking overhead firstname.lastname@example.org (2000-05-08)|
|Re: Branch prediction (was: eliminating array bounds checking overhead email@example.com (David Gregg) (2000-05-12)|
|From:||David Gregg <firstname.lastname@example.org>|
|Date:||12 May 2000 22:32:47 -0400|
|Organization:||Vienna University of Technology, Austria|
> [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.
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,
Return to the
Search the comp.compilers archives again.