 | This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Predication" computer architecture – news ·newspapers ·books ·scholar ·JSTOR(March 2014) (Learn how and when to remove this message) |
Incomputer architecture,predication is a feature that provides an alternative toconditional transfer ofcontrol, as implemented by conditionalbranch machineinstructions. Predication works by having conditional (predicated) non-branch instructions associated with apredicate, aBoolean value used by the instruction to control whether the instruction is allowed to modify the architectural state or not. If the predicate specified in the instruction is true, the instruction modifies the architectural state; otherwise, the architectural state is unchanged. For example, a predicated move instruction (a conditional move) will only modify the destination if the predicate is true. Thus, instead of using a conditional branch to select an instruction or a sequence of instructions toexecute based on the predicate that controls whether the branch occurs, the instructions to be executed are associated with that predicate, so that they will be executed, or not executed, based on whether that predicate is true or false.[1]
Vector processors, someSIMD ISAs (such asAVX2 andAVX-512) andGPUs in general make heavy use of predication, applying one bit of a conditionalmask vector to the corresponding elements in the vector registers being processed, whereas scalar predication in scalar instruction sets only need the one predicate bit. Where predicate masks become particularly powerful invector processing is if anarray ofcondition codes, one per vector element, may feed back into predicate masks that are then applied to subsequent vector instructions.
Mostcomputer programs containconditional 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 ofprocessors simply execute the nextinstruction in a sequence, the traditional solution is to insertbranch 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 implementinginstruction pipelining, a method which is slowed down by branches. For a more thorough description of the problems which arose, and a popular solution, seebranch predictor.
Luckily, one of the more common patterns of code that normally relies on branching has a more elegant solution. Consider the followingpseudocode:[1]
ifcondition{do_something}else{do_something_else}
On a system that uses conditional branching, this might translate tomachine instructions looking similar to:[1]
branch_if_condition_tolabel1do_something_elsebranch_always_tolabel2label1:do_somethinglabel2:...
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 inpredicate 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:[1]
(condition)do_something(notcondition)do_something_else
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 thedo_something anddo_something_else blocks of code are short enough.
Predication's simplest form ispartial predication, where the architecture hasconditional move orconditional 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 isfull 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.[2]
The main purpose of predication is to avoid jumps over very small sections of program code, increasing the effectiveness ofpipelined execution and avoiding problems with thecache. It also has a number of more subtle benefits:
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 onembedded devices, this space cost can be prohibitive. However, some architectures such asThumb-2 are able to avoid this issue (see below). Other detriments are the following:[3]
Predication is most effective when paths are balanced or when the longest path is the most frequently executed,[3] but determining such a path is very difficult at compile time, even in the presence ofprofiling information.
Predicated instructions were popular in European computer designs of the 1950s, including theMailüfterl (1955), theZuse Z22 (1955), theZEBRA (1958), and theElectrologica X1 (1958). TheIBM 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'sPA-RISC architecture (1986) had a feature callednullification, which allowed most instructions to be predicated by the previous instruction.IBM'sPOWER architecture (1990) featured conditional move instructions. POWER's successor,PowerPC (1993), dropped these instructions.Digital Equipment Corporation'sAlpha architecture (1992) also featured conditional move instructions.MIPS gained conditional move instructions in 1994 with the MIPS IV version; andSPARC was extended in Version 9 (1994) with conditional move instructions for both integer and floating-point registers.
In theHewlett-Packard/IntelIA-64 architecture, most instructions are predicated. The predicates are stored in 64 special-purpose predicateregisters; and one of the predicate registers is always true so thatunpredicated instructions are simply instructions predicated with the value true. The use of predication is essential in IA-64's implementation ofsoftware pipelining because it avoids the need for writing separated code for prologs and epilogs.[clarification needed]
In thex86 architecture, a family of conditional move instructions (CMOV andFCMOV) were added to the architecture by theIntelPentium Pro (1995) processor. TheCMOV 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 theARM architecture, the original 32-bit instruction set provides a feature calledconditional 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'sThumb 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.
SomeSIMD instruction sets, like AVX2, have the ability to use a logicalmask to conditionally load/store values to memory, a parallel form of the conditional move, and may also apply individual mask bits to individual arithmetic units executing a parallel operation. The techniqueis known in Flynn's taxonomy as "associative processing".
This form of predication is also used invector processors andsingle instruction, multiple threads GPU computing. All the techniques, advantages and disadvantages of single scalar predication apply just as well to the parallel processing case.
Unlike with control dependencies (branches), they don't predict or speculate what the flags will be, so a cmovcc instead of a jcc can create a loop-carried dependency chain and end up being worse than a predictable branch.gcc optimization flag -O3 makes code slower than -O2 is an example of that.
{{cite web}}:External link in|quote=