Encyclopedia > Branch predication

  Article Content

Branch predication

Branch predication, not to be confused with branch prediction, is a strategy in computer architecture design for mitigating the costs usually associated with conditional branches. Because computer programs respond to a user, there is no way around the fact that portions of a program need to be executed conditionally. As the majority of processors simply execute the next instruction encountered, the traditional solution is to insert branch instructions that allow a program to conditionally branch to a different section of code. This was not necessarily a problem until designers began improving performance by instruction pipelining. For a more thorough description of the problems which arose and a popular solution, see branch prediction.

Luckily, one of the more common patterns of code that usually relies on branching has a more elegant solution. Consider the following pseudocode:

 if condition
     do this
     do that

In a system that uses conditional branching, this might translate to machine instructions looking something like this:

 branch(condition) to label 1
 do that
 branch(always) to label 2
 label 1:
 do this
 label 2:
 more code here

With branch predication, these branches can be eliminated. The basic idea is that each instruction is associated with a predicate (the word here used similarly to its usage in predicate logic) and that the instruction will only be executed if the predicate is true. The machine code for the above example using branch predication might look something like this:

 (condition) do this
 (not condition) do that

Note that besides eliminating branches, less code is needed in total, provided the architecture provides predicated instructions. While this does not guarantee faster execution in general, it will if the do this and do that blocks of code are short enough.

This allows programmers or compilers to avoid "jumps" in simple program code, increasing the effectiveness of pipelined execution and avoiding problems with cacheing.

The IA-64 architecture by Intel includes branch predication in its design in a particularly elegant fashion. Every instruction in the IA-64 instruction set is predicated. The predicates themselves are stored in special purpose registers. One of the predicate registers is always true so that unpredicated instructions are simply instructions predicted with the value true. In conjunction with more traditional methods for handling branching, the IA-64 architecture has seen excellent performance in its real implementations so far, the Itanium and Itanium 2[?] processors.

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Quadratic formula

... left side is now a perfect square; it is the square of (x + b/(2a)). The right side can be written as a single fraction; the common denominator is 4a2. W ...

This page was created in 35 ms