Author: Robert Hyatt
Date: 11:10:18 06/05/01
Go up one level in this thread
On June 05, 2001 at 11:57:12, Gian-Carlo Pascutto wrote: >On June 05, 2001 at 11:49:20, Daniel Clausen wrote: > >>Second, there are processors which use more than 1 bit for branch prediction. >>(I think the Sparc-architecture is one of them, but I'm not sure) So >>recognizing simple patterns like 101010 or thelike would not be a problem for >>such architectures either. > >The branch predictors on x86 also can do this and much more. > >They can recognize quite large patterns. I once stumbled upon >a site that had a great explanation of how it works, but I >dont remember the link (maybe it was at Dr Dobbs) > >-- >GCP Most use two bits in the BTB predictions. But if the branches alternate yes, no, yes, no, they will _never_ be correctly predicted. The classic approach is a finite state machine with four states, SNT, WNT, WT and ST. (Strongly Not Taken, Weakly Not Taken, Weakly Taken and Strongly Taken). To get into SNT the branch has to be not taken at least two consecutive times... for ST, it has to be taken for at least two consecutive times (three if it starts in SNT). When a branch is taken, it moves to the right one state (in the list above) until it can move no further, where it then sticks. If it is not taken, it moves to the left one state unless it is already in SNT. Clever, predicts every loop iteration branch but the last, and gets all the other ;if/then/else branches right if they are consistent. But not ones that alternate...
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.