GATE 2024 CS (CS1) – Question 55
The baseline execution time of a program on a 2 GHz single core machine is 100 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 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 ________
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 3
Explanation
**1. Separate serial and parallel execution.** Of the 100 ns baseline, 10 ns cannot be parallelized and 90 ns can be divided equally across c cores. Parallel work therefore takes 90/c ns.
**2. Include overhead for additional cores.** There are c−1 extra cores, each contributing 10 ns overhead. Thus $T(c)=10+90/c+10(c-1)=90/c+10c$ ns.
**3. Find and check the integer optimum.** For positive real c, $T^{\prime}(c)=-90/c^2+10=0$ gives c = 3; $T^{\prime\prime}(c)=180/c^3>0$. Since 3 is already an integer, it is optimal. T(2) = 65, T(3) = 60 and T(4) = 62.5 ns. **Answer: 3 cores.**