The baseline execution time of a program on a 2 GHz single core machine is 100 nanoseconds (ns). The code corresponding to 90% of the execution time can be fully parallelized. The overhead for using an additional core is 10 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 ________
Answer
3
Explanation
Of the 100 ns, 10 ns is serial and 90 ns can be shared. With \(p\) cores the shared part takes \(90/p\) ns, and each of the \(p - 1\) additional cores costs 10 ns:
\[T(p) = 10 + \frac{90}{p} + 10(p - 1)\]
This gives \(T(1) = 100\), \(T(2) = 65\), \(T(3) = 60\), \(T(4) = 62.5\) and \(T(5) = 68\) ns. A fourth core saves only \(30 - 22.5 = 7.5\) ns on the parallel part but adds 10 ns of overhead, so the time is smallest with 3 cores.
Charging the overhead for every core (\(10p\)) raises each time by 10 ns and still gives 3. The 2 GHz clock rate plays no part.
Answer: 3