Editing Predication (computer architecture) (section)

==Overview==
Most [[computer program]]s contain [[conditional (computer programming)|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 [[central processing unit|processors]] simply execute the next [[instruction (computer science)|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]].

Luckily, one of the more common patterns of code that normally relies on branching has a more elegant solution. Consider the following [[pseudocode]]:<ref name="rvinyard"/>

<syntaxhighlight lang="c">
if condition
    {do_something}
else
    {do_something_else}
</syntaxhighlight>

On a system that uses conditional branching, this might translate to [[machine language|machine instructions]] looking similar to:<ref name="rvinyard"/>

<syntaxhighlight lang="c">
    branch_if_condition_to label1
    do_something_else
    branch_always_to label2
label1:
    do_something
label2:
    ...
</syntaxhighlight>

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:<ref name="rvinyard"/>

<syntaxhighlight lang="c">
(condition)     do_something
(not condition) do_something_else
</syntaxhighlight>

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 <code>do_something</code> and <code>do_something_else</code> 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.<ref>{{cite conference |last1=Mahlke|first1=Scott A.|last2=Hank|first2=Richard E.|last3=McCormick|first3=James E.|last4=August|first4=David I.|last5=Hwn|first5=Wen-mei W.|title=A Comparison of Full and Partial Predicated Execution Support for ILP Processors |conference=The 22nd International Symposium on Computer Architecture, 22–24 June 1995 |year=1995 |doi=10.1145/223982.225965 |isbn=0-89791-698-0 |citeseerx=10.1.1.19.3187}}</ref>