Predication
Home Up

 

Pipeline
EPIC
Instruction Format
Instruction Sequencing
Operating Environments
Predication
Compares
Speculation
Branching
Register Rotation
Other

Predication is the conditional execution of instructions. Conditional execution is implemented through branches in traditional architectures. Predication removes branches used for conditional execution. Predicated execution avoids branches, and simplifies compiler optimization by converting a control dependency to a data dependency.

The following is an example presented in [1]:

Given the following source code:

    if (emp_status == ACTIVE) {
        n_active_emps++;
        total_payroll += emp_pay;
     }
    else {
        n_inactive_emps++;
     }

This code is typically compiled into a sequence such as:

    {
        cmp.ne p1 = rs, ACTIVE   // compare emp_status
        (p1) br else             // jump to else code if condition fails
    }
    .label then
    {
        add  rt = rt, rp         // sum total_payroll + emp_pay
        add  ra = ra, 1          // increment n_active_emps
        br  join
    }
    .label else
    {
        add  ri = ri, 1          // increment n_inactive_emps
    }
    .label join

The generated predicated code would look like:

    {
        cmp.eq  p1, p2 = rs, ACTIVE  // compare emp_status
    } {
        (p1)  add rt = rt, rp        // sum total_payroll + emp_pay
        (p1)  add ra = ra, 1         // increment n_active_emps
        (p2)  add ri = ri, 1         // increment n_inactive_emps
    }

Predication provides many advantages over prediction. In the example above the three predicated instructions can be executed in parallel. Each of the instructions above are predicated. If the instruction's predicate evaluates to a 1, the instruction is executed. Otherwise, the instruction equates to a NOP. On a machine with three or more add units, the above example utilizes the same cycles as a non-predicated machine except there is no possibility of a branch penalty.

Important concept:

"Predicated execution avoids branches, and simplifies compiler optimization by converting a control dependence to a data dependence." [2]

The following diagram from Byte.com illustrates predication: