Learn about the technologies behind the Internet with The TCP/IP Guide!
NOTE: Using robot software to mass-download the site degrades the server and is prohibited. See here for more.
Find The PC Guide helpful? Please consider a donation to The PC Guide Tip Jar. Visa/MC/Paypal accepted.
View over 750 of my fine art photos any time for free at DesktopScenes.com!

[ The PC Guide | Systems and Components Reference Guide | The Processor | Processor Architecture and Operation | Internal Processor Interfaces and Operation | Performance Enhancing Architectural Features ]

Speculative Execution and Branch Prediction

As discussed in the section on the execution process for x86 translating processors, some CPUs have the ability to execute multiple instructions at once. In some cases, not all of the results of the execution will be used, because changes in the program flow may mean that the instruction should never have been encountered in the first place. In particular, this occurs in the vicinity of branches, where a condition is tested and the program path is altered depending on the results.

Branches are very common in x86 code and represent a real problem for pipelining, because they mean that you can't always rely that instructions will go in a linear sequence. Pipelining means starting the next instruction before the first one has completed. When we come to a conditional test instruction (an "if.. then" instruction), we don't know until the condition test has been executed which instruction is next, so what are we supposed to put into the pipeline next?

A less sophisticated processor will stall the pipeline until the results are known, hurting performance. More advanced processors will speculatively execute the next instruction anyway, with the hope that it will be able to use the results if the branch goes the way it thinks it will. Still more advanced processors combine this with branch prediction, where the processor can actually predict with fairly good accuracy which way the branch will go based on past history.

Take the following code as an example:

  • IF A = B THEN
    • C = C + 1
  • ELSE
    • C = C - 1
  • END IF

The "IF...THEN" instruction is a branch. Until it has been completely executed, we don't know if the next instruction will be the addition or the subtraction. A processor that speculatively executes may start both the addition and subtraction going at the same time, and then simply discard whichever one it turns out not to need. Or, it may make use of branch prediction to start only one of them, the one it feels is more likely to be the result of the "if" statement.

Branch prediction improves the handling of branches by making use of a special small cache called the branch target buffer or BTB. Whenever the processor executes a branch, it stores information about it in this area. When the processor next encounters the same branch, it is able to make an informed "guess" about which way the branch is likely to result. This helps keep the pipeline flowing and improves performance. (It's pretty cool too. :^) ) The larger the BTB is, the more branches it can maintain information for.

Next: Out-of-Order Execution


Home  -  Search  -  Topics  -  Up

The PC Guide (http://www.PCGuide.com)
Site Version: 2.2.0 - Version Date: April 17, 2001
Copyright 1997-2004 Charles M. Kozierok. All Rights Reserved.

Not responsible for any loss resulting from the use of this site.
Please read the Site Guide before using this material.
Custom Search