GATE CS Mastery
Cheat sheets

GATE CS 2024 Set 1 · Computer Organization and Architecture

Question 55

NAT2 marksNo negative markingMedium (estimate)

Question

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 ________

Official answer and solution
Official answer
3
From
Official GATE 2024 answer key

Solution

Formulate the execution time T(k)T(k) on kk cores as the sum of serial time, parallel time 90/k90/k, and multicore overhead, then minimize over integer k≥1k \ge 1.

Out of the 100 ns100\text{ ns} baseline single-core execution time:

  • Serial (non-parallelizable) portion =10% of 100 ns=10 ns= 10\% \text{ of } 100\text{ ns} = 10\text{ ns}
  • Parallelizable portion =90% of 100 ns=90 ns= 90\% \text{ of } 100\text{ ns} = 90\text{ ns}

When running on kk cores (where each additional core adds 10 ns10\text{ ns} of overhead), the total execution time is:

T(k)=10+90k+10(k−1)=90k+10k nsT(k) = 10 + \frac{90}{k} + 10(k - 1) = \frac{90}{k} + 10k \text{ ns}

(Even if the overhead is modeled as 10k ns10k\text{ ns} for k≥2k \ge 2, the variable part is still 90k+10k\frac{90}{k} + 10k.)
Setting the derivative with respect to kk to zero (or applying AM-GM):

dTdk=−90k2+10=0  ⟹  k2=9  ⟹  k=3\frac{dT}{dk} = -\frac{90}{k^2} + 10 = 0 \implies k^2 = 9 \implies k = 3

Checking integer values: T(1)=100 nsT(1) = 100\text{ ns}, T(2)=65 nsT(2) = 65\text{ ns}, T(3)=60 nsT(3) = 60\text{ ns}, T(4)=62.5 nsT(4) = 62.5\text{ ns}. Thus k=3k = 3 cores minimize the execution time.

Final answer

3

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper
GATE 2024 Computer Science and Information Technology - Set 1 (CS1)
Question
55 of 65
Section
Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.