Branch predication


Branch predication

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.

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.

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.

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.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Conditional (programming) — Conditional statement redirects here. For the general concept in logic, see Material conditional. In computer science, conditional statements, conditional expressions and conditional constructs are features of a programming language which perform …   Wikipedia

  • Hazard (computer architecture) — Hazards are problems with the instruction pipeline in central processing unit (CPU) microarchitectures that potentially result in incorrect computation. There are typically three types of hazards: data hazards structural hazards control hazards… …   Wikipedia

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   Wikipedia

  • Predicate — or predication may refer to:*Predicate (mathematics), a relation, or the boolean valued characteristic function or indicator function of a relation *Predicate (logic), a fundamental concept in first order logic **in Bertrand Russell s theory of… …   Wikipedia

  • Binary GCD algorithm — The binary GCD algorithm is an algorithm which computes the greatest common divisor of two nonnegative integers. It gains a measure of efficiency over the ancient Euclidean algorithm by replacing divisions and multiplications with shifts, which… …   Wikipedia

  • Software pipelining — In computer science, software pipelining is a technique used to optimize loops, in a manner that parallels hardware pipelining. Software pipelining is a type of out of order execution, except that the reordering is done by a compiler (or in the… …   Wikipedia

  • David August — David I. August (born 1970) is an associate professor of computer science at Princeton University specializing in compilers and computer architecture. August is a strong advocate of alternatives to parallel programming to address the software… …   Wikipedia

  • устройство прогнозирования ветвлений потока команд — В некоторых процессорах. [http://www.morepc.ru/dict/] Тематики информационные технологии в целом EN BPUBranch Predication Unit …   Справочник технического переводчика

  • Aristotle’s logic and metaphysics — Alan Code PART 1: LOGICAL WORKS OVERVIEW OF ARISTOTLE’S LOGIC The Aristotelian logical works are referred to collectively using the Greek term ‘Organon’. This is a reflection of the idea that logic is a tool or instrument of, though not… …   History of philosophy

  • Homiletics — • Lengthy historical article. Includes extensive bibliography Catholic Encyclopedia. Kevin Knight. 2006. Homiletics     Homiletics     † …   Catholic encyclopedia