Official PYQ · 1996Q26Memory Hierarchy: Cache, Main Memory and Secondary StorageNAT1 mark

GATE CS 1996 Q26 — Memory Hierarchy: Cache, Main Memory and Secondary Storage

A computer system has a three-level memory hierarchy, with access time and hit ratios as shown below:

$\overset{ \text{Level $1$ (Cache memory)} \\ \text{Access time = $50 nsec/byte$}}{\begin{array}{|l|l|} \hline \textbf{Size} & \textbf{Hit ratio} \\ \hline \text{$8 M $ bytes} & \text{$0.80$} \\ \hline \text{$16 M $ bytes} & \text{$0.90$} \\ \hline \text{$64 M $ bytes} & \text{$0.95$} \\ \hline \end{array}} \quad \overset{\text{Level $2$ (Main memory)} \\ \text{Access time = $200 nsec/byte$}}{\begin{array}{|l|l|l|} \hline \textbf{Size} & \textbf{Hit ratio} \\ \hline \text{$4 M$ bytes} & \text{$0.98$} \\ \hline \text{$16 M$ bytes} & \text{$0.99$} \\ \hline \text{$64 M$ bytes} & \text{$0.995$} \\ \hline \end{array}} \quad \overset{ \text{Level $3$} \\ \text{Access time = $5$} \mu \text{sec/byte}}{\begin{array}{|l|l|l|} \hline \textbf{Size} & \textbf{Hit ratio} \\ \hline \text{$260M$ bytes} & \text{$1.0$} \\ \hline\end{array}}$

What should be the minimum sizes of level $1$ and $2$ memories to achieve an average access time of less than $100 nsec$ ?
What is the average access time achieved using the chosen sizes of level $1$ and level $2$ memories?

View worked solution

Answer: 61.25

For a three-level hierarchical memory system, the average access time ( $T_{\text{avg}}$ ) is calculated as:

T_{\text{avg}} = T_1 + (1 - H_1) \left[ T_2 + (1 - H_2) T_3 \right]

Given parameters:

$T_1 = 50 \text{ nsec}$
$T_2 = 200 \text{ nsec}$
$T_3 = 5 \mu\text{sec} = 5000 \text{ nsec}$

Part (A): Minimum sizes to achieve $T_{\text{avg}} < 100 \text{ nsec}$

Let's evaluate different combinations of Level 1 and Level 2 sizes:

L1 = 8M ( $H_1 = 0.80$ ), L2 = 4M ( $H_2 = 0.98$ ): $T_{\text{avg}} = 50 + 0.20 \times [200 + 0.02 \times 5000] = 50 + 0.20 \times 300 = 110 \text{ nsec} \quad (\ge 100)$
L1 = 8M ( $H_1 = 0.80$ ), L2 = 16M ( $H_2 = 0.99$ ): $T_{\text{avg}} = 50 + 0.20 \times [200 + 0.01 \times 5000] = 50 + 0.20 \times 250 = 100 \text{ nsec} \quad (\ge 100)$
L1 = 8M ( $H_1 = 0.80$ ), L2 = 64M ( $H_2 = 0.995$ ): $T_{\text{avg}} = 50 + 0.20 \times [200 + 0.005 \times 5000] = 50 + 0.20 \times 225 = 95 \text{ nsec} < 100$
L1 = 16M ( $H_1 = 0.90$ ), L2 = 4M ( $H_2 = 0.98$ ): $T_{\text{avg}} = 50 + 0.10 \times [200 + 0.02 \times 5000] = 50 + 0.10 \times 300 = 80 \text{ nsec} < 100$

Comparing the total memory capacity of valid configurations, $\text{L1} = 16\text{M}$ and $\text{L2} = 4\text{M}$ (total $20\text{M}$ ) is smaller than $\text{L1} = 8\text{M}$ and $\text{L2} = 64\text{M}$ (total $72\text{M}$ ). Thus, the minimum sizes are L1 = 16M and L2 = 4M.