0
$\begingroup$

I was reviewing for my CS class and came across this question and answer combo that didn't have any explanation why it was correct. I'm confused on how they got the answer:

We have a system to which we can instantaneously add and remove cores -- adding more cores never leads to slowdown from things like false sharing, thread overhead, context switching, etc

When the program foo() is executed to completion with a single core in the system, it completes in 20 minutes. When foo() is run with a total of three cores in the system, it completes in 10 minutes.

If 100% of foo() is parallelizable, with 3 cores it would take 20/3=6.66 minutes. Since it instead takes 10 minutes, what fraction of foo() is parallelizable?

ANSWER GIVEN: 0.75

How many minutes would it take to execute foo on this magical system as the number of cores approaches infinity?

ANSWER GIVEN: 5

Could someone explain how the staff got these answers?

$\endgroup$

1 Answer 1

0
$\begingroup$

Suppose that the fraction of foo() that is parallelizable is $\alpha$. Then the total execution time with $n$ cores is:

  • the non-parallelizable execution, done by only one core: $(1- \alpha)\times 20$
  • the parallelizable execution: $\alpha \times 20 \times \frac{1}{n}$

Then, for the first question, we have to consider that the number of cores is $3$, and the total time is $10$. The equation becomes:

$(1-\alpha)\times 20 + \alpha\times \frac{20}{3} = 10\Leftrightarrow \alpha = 0.75$.

For the second question, we suppose known the answer to the first question: $\alpha = 0.75$, and we suppose then that $n = \infty$. The total execution time becomes:

$0.25 \times 20 + 0.75\times \frac{20}{\infty} = 0.25 \times 20 = 5$.

$\endgroup$
2
  • $\begingroup$ Thank you! What if you set things up to be a quadratic with two solutions? Like say everything is the same but when foo() is run with a total of four cores, it completes in 9 minutes, and if foo() was completely parallelizable, with 4 cores it would take 20/4=5 minutes. But it takes 9 minutes. In that case wouldn't you end up with $(1-a)*20+a*20/4=9$ which has 2 solutions? Would you just choose the 0.9 because it makes more sense? $\endgroup$
    – Melanie
    Apr 22, 2021 at 18:14
  • $\begingroup$ $(1-\alpha)\times 20 + \alpha\times \frac{20}{n} = C$ always has one solution, given by $\alpha = \frac{n\times (20 - C)}{(n-1)\times 20}$. $\endgroup$
    – Nathaniel
    Apr 22, 2021 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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