Branch predication

From Wikipedia, the free encyclopedia

Not to be confused with Branch prediction.

Branch predication is a strategy in computer architecture design for mitigating the costs usually associated with conditional branches, particularly branches to short sections of code. It does this by allowing each instruction to conditionally either perform an operation or do nothing.

[edit] Overview

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 a good solution until designers began improving performance by instruction pipelining, which is slowed down by branches. 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 normally relies on branching has a more elegant solution. Consider the following pseudocode:

if condition
    do this
else
    do that

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

  branch if condition to label 1
  do that
  branch to label 2
label 1:
  do this
label 2:
  ...

With branch predication, all possible branch paths are executed, the correct path is kept and all others are thrown away. 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.

Typically, in order to claim a system has branch predication, most or all of the instructions must have this ability to execute conditionally based on a predicate.

[edit] Advantages and disadvantages

The main purpose of predication is to avoid jumps over very small sections of program code, increasing the effectiveness of pipelined execution and avoiding problems with the cache. It also has a number of more subtle benefits:

  • Functions that are traditionally computed using simple arithmetic and bitwise operations may be quicker to compute using predicated instructions.
  • Predicated instructions with different predicates can be mixed with each other and with unconditional code, allowing better instruction scheduling and so even better performance.
  • Elimination of unnecessary branch instructions can make the execution of necessary branches, such as those that make up loops, faster by lessening the load on branch prediction mechanisms.

Unfortunately, predication has one strong drawback: encoding space. In typical implementations, every instruction reserves a bitfield for the predicate specifying whether that instruction should have an effect. When available memory is limited, as on embedded devices, this space cost can be prohibitive. However, some architectures such as Thumb-2 are able to avoid this issue.

[edit] Examples

In Intel's IA-64 architecture, almost 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 predicated with the value true. The use of predication is essential in the IA-64 implementation of software pipelining because it avoids the need for writing separated code for prologs and epilogs.

On the ARM architecture, almost all instructions can be conditionally executed. Thirteen different predicates are available, each depending on the four flags Carry, Overflow, Zero, and Negative in some way. The ARM's 16-bit Thumb instruction set has no branch predication, in order to save encoding space, but its successor Thumb-2 overcomes this problem using a special instruction which has no effect other than to supply predicates for the next four instructions.

For a concrete example of code exploiting branch predication, see the ARM assembly example in binary GCD algorithm.