Previous | Next --- Slide 31 of 59
Back to Lecture Thumbnails
afa4

Can someone explain how the constant is 1.5 in this case?

ChandlerBing

I have the same doubt, could someone clarify where the 1.5 comes from?

cacay

Each processor does a sequential scan on half the elements. This takes ~0.5n work each, so ~n work total. Then, each processor adds the base to ~0.25n elements (a half of the second half). This is ~0.5n work. Adding these we get ~1.5n work.

kayvonf

@cacay. Yup!

BryceToTheCore

The Span is then n*.75. So we are using ~1.5x processing power to achieve a total theoretical real world computation time of .75.

the original efficiency was 1.0 power/time, whereas with this 2 processor parallel algorithm our ration is 1.5 power / .75 time = 2 power / time.

This makes sense, because if we have a factory that only did 2 processor sequential scans each day, it would cost us 2 power / time to operate each day assuming the rate of incoming jobs is not limiting.

A side effect of parallel algorithms that are not perfectly parallel is that some of the processors may have a resting time and thus the power/time ration will be less than P.

I wonder if it is possible to improve the amount of energy used to perform a computation? Maybe it is inherently tied to the complexity of the algorithm itself.