Author: Robert Hyatt
Date: 09:55:45 06/06/01
Go up one level in this thread
On June 06, 2001 at 09:33:10, Vincent Diepeveen wrote: >On June 05, 2001 at 23:03:18, Robert Hyatt wrote: > >> >>Do you realize that the BTB stores the _target_ address and not the address of >>the branch instruction itself? This significantly reduces the number of entries >>it needs. A loop with 10 if statements with break as the executable needs only >>one BTB entry, not 10, even though there are 10 conditional branches in the >>loop (all to the same label). > >Noop i didn't know this. So it stores a variables adress and then >uses a FEW bits only to predict its value? > >Why doesn't it then also use its value to predict the branch? It does. It remembers, via the 4 states (Strongly Taken, Weakly Taken, Weakly Not Taken, Strongly Not Taken) what happened the last few times this branch target address was referenced by a conditional branch. This _is_ used to predict the next branch that references this same address. If the current BTB state is either of the two "taken" cases, the branch is predicted to be taken. If not, it is predicted to be not taken. If the branch target address is not in the BTB, then the direction of the branch is used to predict the branch (backward = predict taken, forward = predict not-taken). The BTB contains the target address because that is part of the instruction and is readily available in the pipeline. The instruction address is not passed along the pipeline as it is not useful information. >So that only if the value gets modified of this variable short >before it gets executed, then a way better prediction would >be done! > >Or am i completely posting nonsense here? > >Fact is that there is a 50% chance here that things go wrong >because side here is a local variable. If there is a 50% probability that a branch is taken, then there is a 50% probability that the branch will be predicted correctly 1/2 of the time, and a 50% probability that the branch will be predicted wrong all of the time. If you take a branch the first two times, then alternate, you will predict right 1/2 the time as you will predict "taken" every time. If you don't take it the first two times, then alternate, you will predict not taken every time and still hit 50%. but if you flip back and forth from the start, you will (say) take it the first time (and go into the WT state) which makes you predict taken next time (wrong) and when you find out it is wrong, you move to WNT which will make the next predicton wrong as well. Over and over... > >It first gets compared whether it's white then whether it's black. > >it says: > >if( side == white ) > >a bit later: > >if( side == black ) > >Isn't that challenging BTB again? > >Anyway, for 100% sure 1 misprediction occurs even if the >rest gets guessed well. We both know it's crappy way of coding >things. The programmer of it doesn't seem to realize it though >and even challenges us to show him faster code. > >How about you cut'n pasting some from crafty? > >Best regards, >Vincent
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.