11.3k views

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 | 11.3k views
+20

Miss Rate of L1 is twice of miss rate of L2. So far so good to eliminate the options (B) and (C).
We're left with the options (A) and (D). keep the values one by one.

AMAT = Hit_TimeL1 + MissRateL1*Miss_PenaltyL1
Miss_PenaltyL1 = HitTimeL2 + MissRateL2*Miss_PenaltyL2

AMAT = Hit_TimeL1 + MissRateL1*(HitTimeL2 + MissRateL2*Miss_PenaltyL2)

Keep the values from option (A).
$= 1 + 0.111( 8 + 0.056*18) = 1.9998888 = 2ns$

Hence, (A) is the correct choice!

0
The miss penalty from the L2cache to main memory is 18 clock cycles

So why we are taking 18 for total. I think we should take 27.

And i got c as answer
0

@Manu Thakur

why did you take hit time as 1? Shouldnt it be 1*(1-x) means access time*hit ratio?

0
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.
0
miss rate L1=2x

miss rate L1=x

E.A.T=(1-2x)*1+2x*(1-x)(1+8)+(1-2x)(1-x)(1+18+8)

why this is wrong????
0
Can you please type more clean.
+7

@BASANT KUMAR

You are partially right.

The equation for AMAT will be as follows:

AMAT = (h1)(t1) + (1-h1)(h2)(t1+t2) + (1-h1)(1-h2)(t1+t2+t3)

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

=1-2x+18x-18x$^{2}$+54x$^{2}$

=1+16x+36x$^{2}$

Using the information given in question, we have EMAT = 2 cycles.

36x$^{2}$ + 16x + 1 = 2

x = $\frac{-16 \pm \sqrt400 }{72}$

Ignoring the negative root we get,

x = (-16 + 20)/72 =1/18 = 0.055

2x = 0.111

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

by
selected by
+4
why people do not consider hit rate into account? I mean 2 = 1*(1-x) + x(8(1-0.5x) + 18*0.5x)
+3
You are assuming cache levels can be accessed simultaneously. Unfortunately that is not common :)
+1
Not about simultaneous access. I think hit rate indicates with what probability you'll get data from a particular cache/memory.  For instance in this case probability of getting data in 8 cycles from L2 cache is (1-0.5x).

I read somewhere that hit rate is very high almost equals to 1, that is why people do not consider hit rate while calculating average memory access time. But in the given question, it does not seem this case.
+2
No. It is considered. But when we count the time from the next lower level, we have to include the time of going through the hierarchy. i.e., my calculation goes like this, 100% of time level 1 is ccessed, whenever it is missed level 2 is accessed and so on.
+2
got your point wih the assumption that data fetch and tag checking are done in parallel (not any extra time for data fetch) :) :)
0
Sir, please elaborate a bit: How you came up with this equation
+1
It is the same equation to be used in any scenario of hierarchical memory access. But if one by-hearts it, it wont work usually. I have explained the reason of the equation now..
+1
0
Arjun Sir, is my answer technically fine or are any assumptions wrong, even though answer is right ?
+1
Whenever it is mentioned as 2 level or 3 level system,then can we assume it a hierarchical system,@arjun sir?or is it because the miss penalty from L2 to main memory is given which is indicating that it is heirarchial system?
+10

yes, Whenever it is mentioned as 2 level or 3 level system, and we can access 2nd level only after miss in 1st level then can we assume it a hierarchical .

Your assumption is right, the miss penalty from L2 to main memory is given which is indicating that it is hierarchical system .

The miss penalty from the L2 cache to main memory is 18 clock cycles.

This line indicates that when there is a miss in level 2 we have to search in MMU , so it goes level by level in memory hierarchy , it means we have to use Hierarchical access here .

+2

I know this is silly but can anyone point me where I am committing mistake.. i assumed L1 = 2x and L2= x and result i got is 0.555 why is it so ? 0

Hi @arjun, In Hamacher,

AMAT = hC + (1 - h)M                    where, h = hit rate, C = access time in cache, M = Miss penalty.

For a two cache system who works sequentially, I guess, above equation can be updated as

AMAT = h1C+ (1 - h1)M1                       where M1 = Miss penalty for cache 1 i.e. L1

And acc. to Hamacher, Miss penalty is time needed to bring a block of data from a slower unit in the memory hierarchy to a faster unit.

So, I think

M1 = AMAT2 i.e. h2C2 + (1-h2)M2            where M2 = Miss penalty for cache 2 i.e. L2

So final equation should be

AMAT = h1C+ (1 - h1)[h2C2 + (1-h2)M2]

What am i missing?

My primary issue is AMAT = hC + (1 - h)M equation. only Hamacher wrote it like h*C. Even on Wikipedia, it is AMAT = C + (1 - h)M

+1
Both are same :

H1 . T1 + (1-H1) (T1+T2)  + (1-H1) (1-H2) (T1+T2+T3 ) .............Solve it, u will get T1 + (1-H1) T2 + (1-H1) (1-H2) T3
0

But sir in hamacher they said .

Consider a system inclydinc an L2 cache now the avg access time experienced by the processor in such a system is

Tavg = h1c1+(1-h1)(h2c2+(1-h2)m)

h1 is the hit rate in the L1 cache

h2 is the hit rate in the L2 cache

c1 is the time to access info in the L1 cache

c2 is the miss penalty to transfer info from L2 toL1

M is the miss penalty to transfer info from main memory to L2

According to that the equation would be

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

Where x is the miss penalty of L2

Sir, correct me where i am wrong..

0

@saif your equation is correct but you missed this part.

The miss penalty from the L2 cache to main memory is 18 clock cycles...

So they have given miss penalty only from higher hierarchy to lower hierarchy.  Also, being two level which means access is not parallel otherwise it would have been $1$ level. From both these points we are supposed to add search time of lower hierarchy to make miss penalty complete. So equation becomes -

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

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

0
@Arunav when there is a miss in L2 total time will be [1+8+18) why u have done only 8+18
0
It appears in my equation that I have taken 8 + 18. See when L1 miss occur, I added the time 1 + ... in equation to account for time wanted in L1 search, now when even after searching L2, it was miss, I added 8 + ... so the time calculation is correct, it is appearing otherwise.

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.
0

Okay, so should we solve the questions using hierarchical by default ?. What about this question https://gateoverflow.in/584/gate1992-5-a  . I'm literally confused when to go for hierarchical and when for simultaneous.

0

for your given question see the 1st point in the above "Hint for simultaneous organization".

0

As its given write through that's why for write we are considering simultaneous whereas for reading we are considering hierarchical as nothing is mentioned. Am I right?

0

Yeah!

0
A better explanation for last point would be "They have directly given the time needed when a miss or hit happens instead of giving access times"

Correct me if iam wrong..