Re: Branch prediction

bonzini@gnu.org
20 May 2000 13:20:51 -0400

          From comp.compilers

Related articles
Re: Branch prediction bonzini@gnu.org (2000-05-20)
Re: Branch prediction djimenez@cs.utexas.edu (2000-05-21)
Re: Branch prediction anton@mips.complang.tuwien.ac.at (2000-05-21)
Re: Branch prediction freitag@alancoxonachip.com (Andi Kleen) (2000-05-21)
Re: Branch prediction sci0627@ccrd200.cdc.polimi.it (2000-05-28)
Re: Branch prediction anton@mips.complang.tuwien.ac.at (2000-05-31)
Re: Branch prediction qed@pobox.com (2000-06-03)
[1 later articles]
| List of all articles for this month |

From: bonzini@gnu.org
Newsgroups: comp.compilers
Date: 20 May 2000 13:20:51 -0400
Organization: Mailgate.ORG Server - http://www.Mailgate.ORG
Keywords: architecture, optimize
Mail-From: sci0627@ccrd200.cdc.polimi.it at ccrd200.cdc.polimi.it [131.175.6.2]

>There are two sides to the branch prediction story: static
>(compile-time) prediction and dynamic prediction done by the
>prefetcher.


The x86 does not allow AFAIK static prediction. The PPC does.


>that). Of course, this means that your predictor should be really
>smart: these CPUs expect prediction accuracy well into the 90% range.


The scheme used by P6s and on (maybe Pentium MMX too? I don't
remember) is exceptionally smart. It works by bucketing jumps into 16
bins, according to a taken/not-taken bit pattern. E.g. bin 13 (1101)
means Taken, Taken, Not-Taken, Taken; it is actually able to guess all
pattern with periods up to six, a few longer patterns (up to 16), and
even to learn irregularities.


There's a description of it in Agner Fog's Pentium and Pentium Pro
optimization paper (www.agner.org/assem/)


There's a fundamental problem with every branch prediction system I
ran over. They do not work with indirect jump. Most processors
remember where the last jump landed, which might be decent for a lexer
but absolutely impractical for a bytecode interpreter; the solution
might be to tell the processor "hey, trust me, the jump is going to
land there" with a special instruction.


Paolo Bonzini


Post a followup to this message

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