GATE CS 2024 Set 1 — Question 55

NAT+2 / -0MediumSpeedup & EfficiencyInstruction PipeliningComputer Organization & Architecture

Computer Organization & Architecture → Instruction Pipelining → Speedup & Efficiency

Last updated 20 August 2026

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 ________

Correct answer

3 to 3

Solution

To find the number of cores that minimize the execution time, we define the total execution time

T(n)

as a function of the number of cores

n

1.Identify Sequential and Parallel Components:

Total baseline time $T_1 = 100$ ns.
Parallelizable part $P = 90\% \text{ of } 100 = 90$ ns.
Sequential part $S = 10\% \text{ of } 100 = 10$ ns.

2. Formulate the Execution Time Function $T(n)$ :

When using $n$ cores, the parallel part is divided by $n$ .
The overhead for using an additional core is 10 ns. For $n$ cores, there are $(n-1)$ additional cores, so the total overhead is $10(n-1)$ ns.
$T(n) = S + \frac{P}{n} + \text{Overhead}(n)$
$T(n) = 10 + \frac{90}{n} + 10(n-1)$
$T(n) = 10 + \frac{90}{n} + 10n - 10 = \frac{90}{n} + 10n$

3. Minimize $T(n)$ :

To find the minimum, take the derivative with respect to $n$ and set it to zero:

\frac{dT}{dn} = -\frac{90}{n^2} + 10 = 0

10 = \frac{90}{n^2}

n^2 = 9

n = 3

4.Verification with Discrete Values:

$T(1) = 100$ ns (Baseline)
$T(2) = \frac{90}{2} + 10(2) = 45 + 20 = 65$ ns
$T(3) = \frac{90}{3} + 10(3) = 30 + 30 = 60$ ns
$T(4) = \frac{90}{4} + 10(4) = 22.5 + 40 = 62.5$ ns

The execution time is minimized when the number of cores is 3.

More questions on Instruction Pipelining

2024 Set 2 Q11Consider a computer with a 4 MHz processor. Its DMA controller can transfer 8 bytes in 1 cycle from…2024 Set 1 Q15Which one of the following statements is FALSE?2024 Set 1 Q30Consider a 5-stage pipelined processor with Instruction Fetch (IF), Instruction Decode (ID),…2024 Set 2 Q31An instruction format has the following structure: Instruction Number: *Opcode destination reg,…2024 Set 2 Q53Consider a disk with the following specifications: rotation speed of 6000 RPM, average seek time of…

Practice GATE CS PYQs with adaptive difficulty

Timed practice, skill tracking, and AI explanations — free to start.

Start practicing free