What's the difference to execute both cases of instructions into result_if, result_else, and choose the result according to T/F after the execution?
ArbitorOfTheFountain
In the worst case described in this slide (resulting in 1/8 utilization due to one branch being much longer than the other), wouldn't the alternative solution of following both sides of the branch also be inefficient because (unless you have a way of aborting) you would have to run until the longer side of the branch completes?
memebryant
@cyl, consider the code
if (x > 0)
x = BusyBeaver(x)
else
x = 42
and the input [0, 0, ..., 0].
anizmatic
@memebryant, In that case, as sir said, the compiler would skip the if branch totally.
But yes, if one branch is much longer than the other, or the length of the branch depends on the input, it does not make sense to execute both branches.
qqkk
I'm still confused why one branch being much longer will lead to 1/8 utilization?
memebryant
@qqkk, if we replace the orange section of code with a section that's n lines long, we're now spending n instructions at 1/8th utilization and 2 instructions at 7/8th utilization. As n grows, the utilization approaches 1/8.
jpd
In that case, you need to store 2 result vectors, then use a few extra instructions to combine them into a final result. This would be slower in all cases, though only by a small fraction if the branches contain enough instructions.
randomized
Regarding utilization in case of if/else branch, is utilization the ratio of average time per data-parallel stream of instructions, and the total time taken to execute the entire if/else snippet ?
What's the difference to execute both cases of instructions into result_if, result_else, and choose the result according to T/F after the execution?
In the worst case described in this slide (resulting in 1/8 utilization due to one branch being much longer than the other), wouldn't the alternative solution of following both sides of the branch also be inefficient because (unless you have a way of aborting) you would have to run until the longer side of the branch completes?
@cyl, consider the code
and the input
[0, 0, ..., 0]
.@memebryant, In that case, as sir said, the compiler would skip the if branch totally.
But yes, if one branch is much longer than the other, or the length of the branch depends on the input, it does not make sense to execute both branches.
I'm still confused why one branch being much longer will lead to 1/8 utilization?
@qqkk, if we replace the orange section of code with a section that's
n
lines long, we're now spendingn
instructions at 1/8th utilization and 2 instructions at 7/8th utilization. Asn
grows, the utilization approaches 1/8.In that case, you need to store 2 result vectors, then use a few extra instructions to combine them into a final result. This would be slower in all cases, though only by a small fraction if the branches contain enough instructions.
Regarding utilization in case of if/else branch, is utilization the ratio of average time per data-parallel stream of instructions, and the total time taken to execute the entire if/else snippet ?