Predication (computer architecture)(Redirected from Branch predication)
This article needs additional citations for verification. (March 2014) (Learn how and when to remove this template message)
In computer science, predication is an architectural feature that provides an alternative to conditional branch instructions. Predication works by executing instructions from both paths of the branch and only permitting those instructions from the taken path to modify architectural state. The instructions from the taken path are permitted to modify architectural state because they have been associated (predicated) with a predicate, a Boolean value used by the instruction to control whether the instruction is allowed to modify the architectural state or not.
Most computer programs contain conditional code, which will be executed only under specific conditions depending on factors that cannot be determined beforehand, for example depending on user input. As the majority of processors simply execute the next instruction in a sequence, the traditional solution is to insert branch instructions that allow a program to conditionally branch to a different section of code, thus changing the next step in the sequence. This was sufficient until designers began improving performance by implementing instruction pipelining, a method which is slowed down by branches. For a more thorough description of the problems which arose, and a popular solution, see branch predictor.
if condition do this else do that
branch if condition to label 1 do that branch to label 2 label 1: do this label 2: ...
With predication, all possible branch paths are coded inline, but some instructions execute while others do not. 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 predication might look something like this:
(condition) do this (not condition) do that
Note that beside 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.
Predication's simplest form is partial predication, where the architecture has conditional move or conditional select instructions. Conditional move instructions write the contents of one register over another only if the predicate's value is true, whereas conditional select instructions choose which of two registers has its contents written to a third based on the predicate's value. A more generalized and capable form is full predication. Full predication has a set of predicate registers for storing predicates (which allows multiple nested or sequential branches to be simultaneously eliminated) and most instructions in the architecture have a register specifier field to specify which predicate register supplies the predicate.
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.
- Elimination of the cost of a branch misprediction which can be high on deeply pipelined architectures.
Predication's primary drawback is in increased encoding space. In typical implementations, every instruction reserves a bitfield for the predicate specifying under what conditions 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 (see below). Other detriments are the following:
- Predication complicates the hardware by adding levels of logic to critical paths and potentially degrades clock speed.
- A predicated block includes cycles for all operations, so shorter paths may take longer and be penalized.
Predication is most effective when paths are balanced or when the longest path is the most frequently executed, but determining such a path is very difficult at compile time, even in the presence of profiling information.
Predicated instructions were popular in European computer designs of the 1950s, including the Mailüfterl (1955), the Zuse Z22 (1955), the ZEBRA (1958), and the Electrologica X1 (1958). The IBM ACS-1 design of 1967 allocated a "skip" bit in its instruction formats, and the CDC Flexible Processor in 1976 allocated three conditional execution bits in its microinstruction formats.
Hewlett-Packard's PA-RISC architecture (1986) had a feature called nullification, which allowed most instructions to be predicated by the previous instruction. IBM's POWER architecture (1990) featured conditional move instructions. POWER's successor, PowerPC (1993), dropped these instructions. Digital Equipment Corporation's Alpha architecture (1992) also featured conditional move instructions. MIPS gained conditional move instructions in 1994 with the MIPS IV version; and SPARC was extended in Version 9 (1994) with conditional move instructions for both integer and floating-point registers.
In the Hewlett-Packard/Intel IA-64 architecture, most instructions are predicated. The predicates are stored in 64 special-purpose predicate registers; and 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 IA-64's implementation of software pipelining because it avoids the need for writing separated code for prologs and epilogs.[clarification needed]
In the x86 architecture, a family of conditional move instructions (
FCMOV) were added to the architecture by the Intel Pentium Pro (1995) processor. The
CMOV instructions copied the contents of the source register to the destination register depending on a predicate supplied by the value of the flag register.
In the ARM architecture, the original 32-bit instruction set provides a feature called conditional execution that allows most instructions to be predicated by one of 13 predicates that are based on some combination of the four condition codes set by the previous instruction. ARM's Thumb instruction set (1994) dropped conditional execution to reduce the size of instructions so they could fit in 16 bits, but its successor, Thumb-2 (2003) overcame this problem by using a special instruction which has no effect other than to supply predicates for the following four instructions. The 64-bit instruction set introduced in ARMv8-A (2011) replaced conditional execution with conditional selection instructions.
- Rick Vinyard (2000-04-26). "Predication". cs.nmsu.edu. Retrieved 2014-04-22.
- Mahlke, Scott A.; Hank, Richard E.; McCormick, James E.; August, David I.; Hwn, Wen-mei W. (22–24 June 1995). "A Comparison of Full and Partial Predicated Execution Support for ILP Processors". The 22nd International Symposium on Computer Architecture.
- Joseph A. Fisher, Paolo Faraboschi, Cliff Young (2004) Embedded Computing - A VLIW Approach to Architecture, Compilers, and Tools. Page 172.
- Clements, Alan (2013). Computer Organization & Architecture: Themes and Variations. Cengage Learning. pp. 532–539. ISBN 1-285-41542-6.