1
$\begingroup$

I was studying branch prediction & predication execution and faced a trouble..

I'm not quite sure whether I understood the concept of predication but based on what I have learned it is taking both taken and not taken at the same time.

For example, let's assume we have 'if' and 'else' each filled with 3 instructions.

For branch prediction, if prediction is correct, we won't have any loss in performance. But if prediction is wrong, there's a waste of 3 instructions.

For predication, either right or wrong, we will have waste of 3 instructions. Then what is the use of predication?

Branch prediction has an accuracy over 90%(I don't know if this only applies to branches with many instructions that can learn from history).

If so, we have a low chance of wasting.

But even besides that, only when prediction accuracy is 0%, branch prediction will be same as predication.

SO where am I getting wrong?

$\endgroup$
  • $\begingroup$ oh.. I think I didn't keep in mind that instructions for predication is less than branch prediction.. $\endgroup$ – kyung sub Song Apr 21 '18 at 12:25
3
$\begingroup$

The cost of a branch misprediction depends on the depth and width of the pipeline and not the amount of code guarded by a condition. A processor keeps fetching and decoding down the wrong path until the branch is resolved and the correct target determined. In a two-wide processor with five stage before branch resolution (a "moderate performance design", say two instruction fetch stages, a decode stage, a register read stage, and an execute stage with a branch resolving at the end of the execution stage), a mispredicted branch could lose up to nine instruction execution opportunities:

br+w1       IF IF ID RR EX
w2+w3          IF IF ID RR EX
w4+w5             IF IF ID RR EX
w6+w7                IF IF ID RR EX
w8+w9                   IF IF ID RR EX
c1+c2                      IF IF ID RR EX

In most real code, two consecutive instructions would not always be able to execute in parallel, so the actual lost performance would be lower. (If the branch was the second instruction of a pair, only 8 instruction execution opportunities would be lost.)

In a fully predicated ISA, the predicated form could also have one less instruction (a branch instruction might include a comparison that would have to be provided as a separate instruction to provide a predicate but often normal instruction results provide a predicate).

Another consideration is that predication avoids fetch redirection. Some implementations have had a one cycle taken branch fetch penalty; for a two-wide processor, this would allow two predicated instructions to execute "for free".

(Out-of-order execution complicates the tradeoffs in providing and using predication. Predication turns an instruction with two dynamic sources into one with three dynamic sources, so the scheduler has to monitor the availability of an additional source (the predicate). In addition, predication converts a control hazard (which can often be bypassed using prediction) into a data hazard (if the predicate is not available, the instruction will not execute and its dependencies cannot execute). In theory, predicates can be predicted just as branch direction is predicted with the prediction only used if the data hazard is expected to introduce excessive slow-down, but this requires both a confidence estimate for the prediction and an estimate of the costs for using and not using the prediction when the prediction is right and when it is wrong.)

Furthermore, not all branches are equally predictable. Some branches approach fifty percent predictability. It is even possible to always mispredict (e.g., with two-bit counters initially at weakly wrong for the first encounter and a branch that alternates between taken and not-taken), though this is a rare occurrence.

Predication of nested conditions can also exponentially increase the number of executed instructions. Branch prediction would choose one path for a switch statement; complete predication would follow all the paths.

Another factor is that processing extra instructions can be relatively inexpensive if the processor has otherwise idle resources. E.g., if one path is stalled waiting for the result of a long latency instruction (or cannot fully utilize available execution width), (predicated) instructions from the other path may be able to execute "for free" (power and other costs would still apply).

Predication also makes more sense with vector/SIMD operations where per-element predication can facilitate the use vector operations that would otherwise need to be executed in a scalar fashion. (Even without predication, one can use bitwise SIMD operations to select operands, choosing between the true operand and the identity value for the operation.)

$\endgroup$
2
$\begingroup$

Many modern processors have predicated instructions, for example the CMOVE (conditional move) on x86 processors, lots of predicated instructions on ARM 32 bits, and a lot fewer instructions on ARM 64 bit.

When these instructions are executed, there is no branching at all. For example, a conditional move "move register A to register B if a condition is true" is just a normal instruction, modifying register B (just like adding 0 to B "modifies" it), with register A as a dependency, and with a condition code register as an additional dependency. An ordinary instruction, just like "add register A to register B", just with one more input.

So it's just one instruction. And there is no branch, which will make your code run a lot faster. Modern processors can run two, three or sometimes four instructions per cycle, and branching interferes with that. Let's say you have code "if condition then X = expression1 else X = espression2". If these expressions are not too complicated, then you can calculate them both, and use a CMOVE to pick the right result. Often there is so much parallelism available that calculating two expressions takes no longer than calculating one, and you avoid branches, and importantly you avoid branch prediction that could go wrong.

Take "if x > 0 then x = x - 1 else x = y+2". You can generate the instructions:

compare x with 0, subtract 1 from x, add tmp = y+2
conditional move tmp to x if not greater

There's a good chance that the first three instructions are performed in one cycle, and the conditional move in another cycle. Two cycles, plus you could have more instructions slotted in that run in parallel. Compare that to

compare x with 0, branch if it is not greater
subtract 1 from x and branch
add x = y + 2

This will always have problems with branch prediction and most likely run slower.

$\endgroup$
1
$\begingroup$

Performance improvement is possible because the fetching of the predicted instructions happens at the same time as executing the current instruction. If you guess right, fetching the next instruction was free.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.