|Re: Branch prediction email@example.com (2000-05-20)|
|Re: Branch prediction firstname.lastname@example.org (2000-05-21)|
|Re: Branch prediction email@example.com (2000-05-21)|
|Re: Branch prediction firstname.lastname@example.org (Andi Kleen) (2000-05-21)|
|Re: Branch prediction email@example.com (2000-05-28)|
|Re: Branch prediction firstname.lastname@example.org (2000-05-31)|
|Re: Branch prediction email@example.com (2000-06-03)|
|[1 later articles]|
|Date:||20 May 2000 13:20:51 -0400|
|Organization:||Mailgate.ORG Server - http://www.Mailgate.ORG|
|Mail-From:||firstname.lastname@example.org at ccrd200.cdc.polimi.it [22.214.171.124]|
>There are two sides to the branch prediction story: static
>(compile-time) prediction and dynamic prediction done by the
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.
Return to the
Search the comp.compilers archives again.