The baseline execution time of a program on a 2 GHz single core machine is 100 nanoseconds ($\textit{ns}$). The code corresponding to 90% of the execution time can be fully parallelized. The overhead for using an additional core is 10 $\textit{ns}$ when running on a multicore system. Assume that all cores in the multicore system run their share of the parallelized code for an equal amount of time. The number of cores that minimize the execution time of the program is ______

Let $T_1 = 100\text{ ns}$ be the single-core baseline execution time.

• Non-parallelizable (serial) portion: $T_{\text{serial}} = 10\% \times 100\text{ ns} = 10\text{ ns}$

• Parallelizable portion: $T_{\text{parallel}} = 90\% \times 100\text{ ns} = 90\text{ ns}$

When using $p$ cores, the number of additional cores used is $(p - 1)$. The overhead for using $(p - 1)$ additional cores is $(p - 1) \times 10\text{ ns}$.

The total execution time $T(p)$ on $p$ cores is:

Evaluating $T(p)$ for integer values of $p \ge 1$:

• For $p = 1$: $T(1) = \frac{90}{1} + 10(1) = 100\text{ ns}$

• For $p = 2$: $T(2) = \frac{90}{2} + 10(2) = 45 + 20 = 65\text{ ns}$

• For $p = 3$: $T(3) = \frac{90}{3} + 10(3) = 30 + 30 = 60\text{ ns}$

• For $p = 4$: $T(4) = \frac{90}{4} + 10(4) = 22.5 + 40 = 62.5\text{ ns}$

• For $p = 5$: $T(5) = \frac{90}{5} + 10(5) = 18 + 50 = 68\text{ ns}$

The execution time is minimized when the number of cores $p = 3$, giving $T(3) = 60\text{ ns}$.

Thus, the number of cores that minimizes execution time is 3.