Analyzing parallel performance question

Question

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?

Answer 1

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$.