GATE CS 2024 Set 1 Q45 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

To find the number of cores that minimizes the execution time, we can model the execution time as a function of the number of cores, $N$.

1. Analyze the Baseline Execution Time

The baseline execution time on a single core ($N = 1$) is $100\text{ ns}$.

• Parallelizable portion: $90\%$ of $100\text{ ns} = 90\text{ ns}$
• Sequential portion: $10\%$ of $100\text{ ns} = 10\text{ ns}$

2. Formulate the Execution Time for $N$ Cores

When running on a multicore system with $N$ cores ($N \ge 1$):

• The sequential portion still takes $10\text{ ns}$.
• The parallelizable portion is divided equally among the $N$ cores, taking $\frac{90}{N}\text{ ns}$.
• There are $N - 1$ additional cores, each contributing an overhead of $10\text{ ns}$. Thus, the total overhead is $10(N - 1)\text{ ns}$.

The total execution time $T(N)$ is given by:

3. Minimize the Execution Time

To find the value of $N$ that minimizes $T(N)$, we can differentiate $T(N)$ with respect to $N$ and set it to zero:

Since the second derivative $\frac{d^2T(N)}{dN^2} = \frac{180}{N^3} > 0$ for $N = 3$, this point represents a local and global minimum.

4. Verification for Integer Values

Let us evaluate $T(N)$ for nearby integer values of $N$ to confirm:

• For $N = 1$: $T(1) = 10 + 90 + 0 = 100\text{ ns}$
• For $N = 2$: $T(2) = 10 + 45 + 10 = 65\text{ ns}$
• For $N = 3$: $T(3) = 10 + 30 + 20 = 60\text{ ns}$
• For $N = 4$: $T(4) = 10 + 22.5 + 30 = 62.5\text{ ns}$

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