Predication Flashcards
What is predication?
Doing the work of both branches until branch is resolved, then throwing away the work of the wrong path.
Waste’s up to 50% of work.
ALWAYS wastes some work, no matter how the branch resolves.
What to use predication vs branch prediction?
Predication works well on small if-then-else statements (about 5 instructions or less). This is because we do the work of both paths and then keep going after the paths converge. Once the branch is resolved, we only have to throw away the work done on the (short) wrong path.
Branch prediction works better on large if-then-else statements, loops, and function calls/returns.
Should you use prediction on a function call/return?
No! Function returns are always “taken”, so doing the work of “both paths” doesn’t even make sense. There’s only one path!
Should you use prediction on a function call/return?
No! If we draw the behavior of a loop as a branching tree, every not taken branch will split into two. The more iterations, the more branchings. If we use predication for this, we will do the work along every path in the branching tree. However, we will only ever need ONE of those paths. It’s a huge waste.
Should you use prediction on a large if-then-else statements?
No! By large, we mean the number of instructions on each branch of the if-then-else is large relative to the number of pipeline stages we go through before resolving the branch. You’re better off predicting and wasting, at max, the misprediction penalty.
What is if-conversion?
How the compiler creates the code needed to perform predication, i.e. do work along both paths.
If the code is:
if (cond) {x = whatever}
else {x = whatever else}
Then it would look like:
x1 = whatever
x2 = whatever else
x = cond ? x1 : x2
What is a conditional move instruction?
A conditional move lets us compile x = cond ? x1 : x2 in a way that doesn’t require a branch. Instead, all it one cycle, it will move x1 or x2 to x, depending on the condition.
In MIPS, we have MOVZ and MOVN for this.
How do you use MOVZ and MOVN?
MOVZ Rd, Rs, Rt means if(Rt == 0){Rd = Rs}
MOVN Rd, Rs, Rt means if(Rt != 0){Rd = Rs}
To execute x = cond ? x1 : x2, do:
R3 = cond
R1 = x1
R2 = x2
MOVN x, R1, R3
MOVZ x, R2, R3
What kind of support does conditional move require?
Compiler support. We need to be able to test a condition and move and value in one instruction.
What is the benefit of conditional move?
It removes hard to predict branches!
What are the downsides of conditional move and is there a way to address them?
- Requires additional registers to store results from both paths (maybe we can do something about this??)
- Executes more instructions because it works through both paths (can’t do anything about this, it’s just about if-conversion works)
- Executes more instructions because we have to add MOVN and MOVZ to select actual results (maybe we can do something about this??)
We can address the first and third by making ALL INSTRUCTIONS CONDITIONAL.
What hardware support is necessary for Conditional Move vs Full Predication?
Conditional Move requires a new “opcode” (basically a new instruction) for each condition. In other words, we have MOVZ and MOVN, one for when the predicate equals zero and one for when it doesn’t.
Full Predication instead uses all the same instructions as without conditions, but adds condition bits to them that point to the predicate that determines the condition for writing to the destination register.
What would a full prediction version of the following code look like?
BEQZ R1, Else
ADDI R2, R2, 1
B End
Else:
ADDI R3, R3, 1
End:
MP.EQZ P1, P2, R1
(P2) ADDI R2, R2, 1
(P1) ADDI R3, R3, 1
The first line sets the predicate. If R1 is equal to zero, P1 is true and P2 false. If it’s not, P1 if false and P2 true.
Then the next two lines only execute if their predicate (in parentheses) is true.
