edited by
28,274 views
67 votes
67 votes

In a two-level cache system, the access times of $L_1$ and $L_2$ caches are $1$ and $8$ clock cycles, respectively. The miss penalty from the $L_2$ cache to main memory is $18$ clock cycles. The miss rate of $L_1$ cache is twice that of $L_2$. The average memory access time (AMAT) of this cache system is $2$ cycles. The miss rates of $L_1$ and $L_2$ respectively are

  1. $0.111$ and $0.056$
  2. $0.056$ and $0.111$
  3. $0.0892$ and $0.1784$
  4. $0.1784$ and $0.0892$
edited by

6 Answers

Best answer
92 votes
92 votes
In two-level memory system (hierarchical), it is clear that the second level is accessed only when first level access is a miss. So, we must include the first level access time in all the memory access calculations. Continuing this way for any level, we must include that level access time (without worrying about the hit rate in that level), to all memory accesses coming to that level (i.e., by just considering the miss rate in the previous level). So, for the given question, we can get the following equation:

$\text{AMAT} = \text{L1 access time}$
$+ \text{L1 miss rate} \times \text{L2 access time}$
$+ \text{L1 miss rate} \times \text{L2 miss rate} \times \text{Main memory access time}$

$2 = 1 + x \times 8 + 0.5 x^2 \times 18$
$\implies 9x^2 + 8x -1 = 0$

$\implies x = \dfrac{-8 \pm \sqrt{64 + 36}}{18} = \dfrac{2}{18} = 0.111$.

So, Answer is option (A).
selected by
54 votes
54 votes

Let us consider

  • The miss rate of L2 cache as M
  • So the hit rate of L2 would be 1 - M

As per question, Miss rate of L1 is twice that of L2,

So,

  • Miss rate of L1 would be 2M
  • Hence its hit rate would be 1 - 2M

Now, to access anything,

  • We would first go to L1
  • If it is a L1 hit, then return                                               ==> L1 access time
  • If it is a L1 miss, then we would go to L2                          ==> L1 access time* +  L2 access time
  • If it is a L2 hit, then return                                               ==> L2 access time
  • If it is a L2 miss, then we would go to memory and return  ==> L2 access time** + Memory access time

*In case of a miss also, we would include L1 access time, because only after accessing L1, we would come to know that element is now there in L1

**In case of a miss also, we would include L2 access time, because only after accessing L2, we would come to know that element is now there in L2

So, average time to access memory would be

(L1 hit rate) x (Time to access L1)                     + 
(L1 miss rate) x [ Time to access L1                    + 
                  (L2 hit rate) x (Time to access L2)   + 
                  (L2 miss rate) x [(Time to access L2) + (Time to access memory)]
                ]

As per question,

  • Time to access L1 = 1 cycle
  • Time to access L2 = 8 cycles
  • Time to access memory = 18 cycles

And our assumption

  • L1 hit rate = 1 - miss rate = 1 - 2M
  • L1 miss rate = 2M
  • L2 hit rate = 1 - miss rate = 1 - M
  • L2 miss rate = M

Putting these values in above equation:

(1 - 2M) x (1) + (2M) x [ 1 + (1 - M) x (8) + (M) x [(8) + (18) ]]

1 - 2M + 2M [ 1 + 8 - 8M + M (26) ]
1 - 2M + 2M[ 9 -7M + 26M]
1 - 2M + 2M [ 18M + 9]
1 - 2M + 36M^2 + 18M
36M^2 + 16M + 1 = Average time to access memory

Given that Average time to access memory is 2 cycles

36M^2 + 16M + 1 = 2

36M^2 + 16M - 1 = 0

On Solving, M = 0.05555555   ==> 0.056 Approx

So, miss rate for L1 ==> 2M ==> 2 x 0.055555 = 0.1111

So, miss rate for L2 ==> M  ==> 0.055555 which is approx 0.056

30 votes
30 votes

Do not categories a question into Hierarchical Or simultaneous access. Otherwise, you'll be confused to solve GATE questions as there is no standard way to assume which question is based on Hierarchical or simultaneous access.

The only standard formula is AMAT=  H1∗(TIME to access from L1)  + (1−H1)*H2*(total time to access from L2)   +  (1-H1)*(1-H2)*(Total time to access from main memory)

= H1*L1 + (1-H1)*H2*(L1+L2) + (1-H1)(1-H2)*(L1+L2+M.M)

Yes! this is Hierarchical access formula BUT do not simplify this formula.

here Miss penalty means the extra time incurred in the desired process(in addition to the original time). Here "miss penalty from the L2 cache to main memory is 18 clock cycles" -  It means in addition to L2 cache access time(8 clock cycle), main memory will take 18 clock cycle to reach the desired block. or simple main memory access time is 18 clock cycle.

Assume miss rate of L1=x

2 = (1-x)*1  + x*(1 - 0.5x)(1+8)  + x * 0.5x * (1+8+18)

 

9x^2 + 8x - 1 = 0

x = 0.1111

so option A) is correct.


If you are obsessed with solving a question in the hierarchical or simultaneous way then here are some hints:-

By default use Hierarchical organization.

Hint for simultaneous organization-(If question contains any statement like this)

  • It is write-through cache system.
  • Ignore the search time in cache OR searching cost in the cache is negligible.
  • 5ns on cache hit and 50ns on cache miss  OR   1ns with hit in cache and 5ns with miss in cache.
3 votes
3 votes

 

These type of questions look very confusing to students. But if you read this answer, everything will be cleared.

In Hierarchical memory access,

CPU ←→ L1 cache ←→ L2 cache ←→ Main memory

Let,

H1 → L1 cache hit rate 

H2 → L2 cache hit rate

T1 → L1 cache access time (1 clock cycle)

T2 → L2 cache access time (8 clock cycles)

Tmm → memory access time (18 clock cycles) => miss penalty from the L2 cache to main memory

 

AMAT = H1*T1 + (1-H1)*H2*(T1+T2) + (1-H1)*(1-H2)*(T1+T2+Tmm)            --------- 1

or

AMAT = H1*T1 + (1-H1)*L1 miss penalty

L1 miss penalty= H2*(T1+T2) + (1-H2)*L2 miss penalty

L2 miss penalty= T1 + T2 +Tmm

If you solve these three equations you will get the result same as equation 1.

 

or

AMAT = T1 + (1-H1)*T2 + (1-H1)*(1-H2)*Tmm (This equation is formed by solving equation 1 further, let’s consider this as equation 2)

or

AMAT = T1 + (1-H1)*L1 miss penalty 

L1 miss penalty= T2 + (1-H2)*L2 miss rate

L2 miss penalty= Tmm

If you solve these three equations you will get the result same as equation 2.

It is given that miss rate of L1 cache is twice that of L2

=> L1 miss rate (Let x) = 2 * L2 miss rate

=> L2 miss rate = x/2;

It is also given that the miss penalty from the L2 cache to main memory is 18 clock cycles

=> Tmm = 18

By solving from above equation 2,

AMAT = T1 + (1-H1) * T2 + (1-H1) * (1-H2) * Tmm

AMAT = T1 + L1 miss rate * T2 + L1 miss rate * L2 miss rate * Tmm

=>  $2 = 1 + x * 8 + x * x/2 * 18$      (AMAT = 2)

=>  $2 = 1 + 8x + 9x^2$

=>  $9x^2 + 8x - 1 = 0$

=>  x = 0.111 

=> L1 miss rate = 0.111

=>  L2 miss rate = 0.111 / 2 = 0.05

If you solve by equation 1 you will get the same result but that will be lengthy, so always try to solve by using equation 2 in these type of questions.

Let me solve this also

AMAT = H1 * T1 + (1-H1) * H2 * (T1+T2) + (1-H1) * (1-H2) * (T1+T2+Tmm)

           = (1 – L1 miss rate) * T1 + L1 miss rate * (1 – L2 miss rate) * (T1 + T2) + L1 miss rate * L2 miss rate * (T2 + T2 + Tmm)                 -----------so lengthy

           = $(1 - x) * 1 + x * (1 - x/2) * (1 + 8) + x * x/2 * (1 + 8 + 18)$

           = $1 - x + 9x -9x^2/2 + 27x^2/2$

           = $1 + 8x + 18x^2/2$

 =>  $2 = 1 + 8x + 9x^2$

=>  $9x^2 + 8x - 1 = 0$

Which will gave the same answer.

Please upvote if you like the answer.

 

Answer:

Related questions

29 votes
29 votes
8 answers
1
78 votes
78 votes
5 answers
2
Madhav asked Feb 14, 2017
29,719 views
The read access times and the hit ratios for different caches in a memory hierarchy are as given below:$$\begin{array}{|l|c|c|} \hline \text {Cache} & \text{Read access ...
31 votes
31 votes
5 answers
3
Madhav asked Feb 14, 2017
10,827 views
In a B+ Tree , if the search-key value is $8$ bytes long , the block size is $512$ bytes and the pointer size is $2\;\text{B}$ , then the maximum order of the B+ Tree is ...
39 votes
39 votes
4 answers
4