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

Comments

Y

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

Answer 3

Baseline execution time is 100 ns.

Program that can be parallelized is 90% i.e. 90 ns program.

Overhead cost of additional core is 10 ns.

 

Execution time (for n core) =    $\frac{Parallelized\,time}{n}$ + Fixed time + (overhead time $*$ (n - 1))

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

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

 

To minimise t(n), derivative of t(n) = 0

\begin{align*}
&\Rightarrow -\frac{90}{n^2} + 10 = 0 \\
&\Rightarrow 10 = \frac{90}{n^2} \\
&\Rightarrow n^2 = 9 \\
&\Rightarrow n = \sqrt{9} \\
&\Rightarrow n = 3
\end{align*}

 

Hence, Answer = 3

Comments

Hi. U written  executive time for n core ,  =   parallels time'/n+ extra data ,

How it equations came , please explain

,Is it relates toh amdhal law anyway 

---

Hi,

This equation came as below,

 

Let's break the program into parts

1: Program that can be parallelized (90% program).

    Execution time (t1) depends on the number of cores

    $ t1(n) = \frac{90}{n} $, as n cores will work parallelly​​​​​​​

 

2: Program that can't be parallelized (10% program).

    Execution time (t2) is fixed / independent of number of cores.

    $t2(n) = 10$, as it's fixed

 

So to execute the program completely, we need to execute parallelized and unparallelized programs.

So, the total execution time (t) will be given by

$t(n) = t1(n) + t2(n)$

 

3. But for the addition of each new core, there is an overhead time of 10ns, that will be added to program execution with each extra core added.

    So we will have to add overhead cost (t0) to total execution time t(n).

    t0 is dependent on the number of cores (n)

    $t0(n) = 10 * (n - 1)$

 

\begin{align*}
&\Rightarrow t(n) = t_1(n) + t_2(n) + t_0(n) \\
&\Rightarrow t(n) = \frac{90}{n} + 10 + 10 *(n-1)
\end{align*}