The GATE Grind

GATE 2024 CS (CS1) – Question 55

Computer Organization and Architecture · ALU and Control Unit Design · 2 marks · Numerical answer

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

More ALU and Control Unit Design questions

All ALU and Control Unit Design questions →