GATE CSE 2024 | Set 1 | Question: 45

Question

The baseline execution time of a program on a $2 \mathrm{GHz}$ single core machine is $100$ nanoseconds ( $n s)$. 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 1

The code that cannot be parallelized runs for 10ns.

For every additional core, additional 10ns overhead is added to total execution time, overhead for n cores is $(n-1)10$ns.

The code that can be parallelized runs for 90ns on one core, it runs for $\frac{90}{n}$ns on n cores.

Let t(n) be the execution time, it is given by -

$t(n) = 10 + (n-1)10 + \frac{90}{n} = 10n + \frac{90}{n}$

$t(1) = 100, t(2) = 65, t(3)  = 60, t(4) = 62.5, t(5) = 68, ...$

Answer - 3

Answer 2

2 GHz Machine implies Cycle-Time of 0.5 ns or you can say for every 1 ns, there are 2 cycles

Now, Given Exec Time of 100 ns implies 200 cycles out of which 90% i.e. 180 cycles can be parallelized

Task is to distribute 180 cycles equally in 'x' number of cores (each 2 GHz) such that exec time gets minimized

Now 

Take x=2, which means 20ns(Overhead) + 90 cycles(each core i.e. 180 cycles/2) i.e. 45ns totaling to 65ns

Take x=3 which means 30ns(Overhead) + 60 cycles(each core i.e. 180 cycles/3) i.e. 30ns totaling to 60ns

Take x=4 which means 40ns(Overhead) + 45 cycles(each core i.e. 180 cycles/4) i.e. 22.5 ns totaling to 62.5ns

Take x=5 which means 50 ns(Overhead) + 36 cycles(each core i.e. 180 cycles/5) i.e. 18 ns totaling to 65 ns

Clearly, minima can be observed at x=3 i.e. 60 ns