edited by
14,925 views
36 votes
36 votes

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}}$$

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

  2. What is the average access time achieved using the chosen sizes of level $1$ and level $2$ memories?

edited by

5 Answers

2 votes
2 votes

Let us first write the formula for average memory access time for hierarchical memory access:

$$T_{avg}= T_{L_1}+(1-h_1)\times T_{L_2}+(1-h_1)(1-h_2)T_M$$$$=T_{L_1}+(1-h_1)\{T_{L_2}+(1-h_2)T_M\}$$

Where:
$$T_{L_1}= \text{Cache Access Time of Level 1 cache= 50 ns (given)}\\T_{L_2}= \text{Cache Access Time of Level 2 cache= 200 ns (given)}\\T_{M}= \text{Access Time of Memory = 5000 ns (given)}\\h_1=\text{Hit ratio of L1}\\h_2=\text{Hit  ratio of L2}$$

Substituting the given values in the $T_{avg}$ we have:

$$T_{avg}=T_{L_1}+(1-h_1)\{T_{L_2}+(1-h_2)T_M\}\\=50+(1-h_1)\{200+(1-h_2)5000\}$$

Now we need to choose appropriate hit ratios $h_1$ and $h_2$ such that $T_{avg}$ is less than $100$ ns.

But we should keep in mind one thing:

$$\color{red}{\text{As per the given statistics, as $T_{L_1}$ is less than $T_{L_2}$ so size of L1 should be less than L2!!!}}$$

Note: Whether we assume inclusion property or not, in modern processors, $L2$ is made larger than $L1$, and $L1$ is designed to have less access time than $L2$ [Quite obvious, as larger the size, larger is the access time of the cache], such a set up helps to reduce the average memory access time. Also, usually $L1$ is present in the processor and needs to be small (due to processor chip area) and fast (to provide data at one cpu cycle time) and $L2$ are usually placed off chip and made larger!!! With this being said, let us dive into the problem.

What is need is memory sizes should be as less as possible, but nothing is said about minimum $T_{avg}$. except that it just needs to be less than $100 ns$.
 

So let us start with $L1 = 8 MB$ but then $L2$ should be greater than $8 MB$ and we take $L2= 16 MB$
So, $$T_{avg}=50+(1-0.8)\{200+(1-0.99)5000\}= 100 ns$$ which is not less than $100 ns$

So we assume, $L2=64 MB$ keeping $L1=8MB$
So, $$T_{avg}=50+(1-0.8)\{200+(1-0.995)5000\}= 95 ns$$ which is less than $100 ns$

Further Reading

edited by
Answer:

Related questions

33 votes
33 votes
6 answers
6