The baseline execution time of a program on a 2 GHz single core machine is 100…
2024
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 — Key idea: split the program into serial and parallel parts, include the per-core overhead, write the total time as a function of the number of cores, and…
Attempted by 33 students.
Show answer & explanation
Correct answer: 3
Key idea: split the program into serial and parallel parts, include the per-core overhead, write the total time as a function of the number of cores, and minimize that function.
Baseline total time = 100 ns. Serial fraction = 10% → serial time = 10 ns. Parallel fraction = 90% → parallel work = 90 ns.
If n cores are used, assume the overhead is 10 ns for each additional core, so total overhead = 10 × (n − 1) ns. The parallel work is divided equally, taking 90/n ns.
Total time T(n) = serial + parallel/n + overhead = 10 + 90/n + 10(n − 1) = 10n + 90/n.
Minimize T(n) over positive n: dT/dn = 10 − 90/n^2. Set to zero → 10 − 90/n^2 = 0 ⇒ n^2 = 9 ⇒ n = 3.
Check nearby integers: T(2) = 65 ns, T(3) = 60 ns, T(4) = 62.5 ns, so n = 3 gives the minimum.
Answer: 3 cores.
A video solution is available for this question — log in and enroll to watch it.