Previous | Next --- Slide 35 of 79
Back to Lecture Thumbnails
cyl

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 ?