GATE IT 2004 | Question: 12, ISRO2016-77

Question

Consider a system with $2$ level cache. Access times of Level $1$ cache, Level $2$ cache and main memory are $1$ $ns$, $10$ $ns$, and $500$ $ns$ respectively. The hit rates of Level $1$ and Level $2$ caches are $0.8$ and $0.9$, respectively. What is the average access time of the system ignoring the search time within the cache?

• A. $13.0$
• B. $12.8$
• C. $12.6$
• D. $12.4$

Comments

Then i don't know, how they did

---

This is from @Ayush Upadhyaya's comment from this question.

Hierarchical Access is being used but the formula used is above is bit simplified form of what we usually see for hierachical access.
 

h1.t1+ (1-h1) h2(t1+t2) +(1-h1)(1-h2)(t1+t2+tm)

= h1.t1+ (1-h1)h2.t1 + (1-h1)(1-h2)t1
+ (1-h1)h2.t2 + (1-h1)(1-h2)t2
+(1-h1)(1-h2)tm

= h1t1 + (1-h1)t1[h2+(1-h2)]
+(1-h1)t2[h2 + (1-h2)]
+(1-h1)(1-h2)tm

=t1 [h1 + (1-h1)]
+ (1-h1)t2
+(1-h1)(1-h2)tm

= t1
+ (1-h1)t2
+(1-h1)(1-h2)tm

I hope it helps. :)

---

You can refer the following problems:

A cache memory needs an access time of 30 ns and main memory 150 ns, what is the average access time of CPU (assume hit ratio = 80%)?

The answer is 60 ns

What hit ratio is required to reduce the effective memory access time from 200 ns to 140 ns if the cache access time is 20 ns?

The answer is 40%

In both the problems they have given the average (or effective) memory access time as

Effective memory access time = (hit rate x cache access time) + { miss rate x (cache access time + memory access time)}

But in the present problem, they have not considered the access time of the previous levels. Why?

Answer 1

By default we consider hierarchical access - because that is the common implementation and simultaneous access cache has great practical difficulty. But here the question is a bit ambiguous -- it says to ignore search time within the cache - usually search is applicable for an associative cache but here no such information given and so we can assume it is the indexing time in to the cache block.

Access time for hierarchical access, 

$ =  t_1 + (1-h_1) \times t_2 + (1-h_1) (1-h_2) t_m$
$ = 1 + 0.2 \times 10 +  0.2 \times 0.1 \times 500$
$= 13ns.$

Option A.

PS: We should follow simultaneous access only when explicitly mentioned in question as hierarchical access is the default in standard books.

Comments

@Arjun sir why we had not taken formula :-AMAT  = h1*t1 + (1-h1)*h2*(t2+t1) + (1-h1)*(1-h2)*(t1+t2+t3).

as this is the formula for hierarchical access.

 

---

@Philosophical_Virus Read this: https://gateoverflow.in/3653/gate-it-2004-question-12-isro2016-77?show=63277#c63277

---

Thanks @Abhrajyoti00 sir

Answer 2

option C

t1 * h1 + (1- h1) h2 t2 + (1-h1) (1-h2) tm

tm- main memory access time

Comments

which  access  method  have to be  use ..  simultaneous  or  hierarchical..?

---

If access times are given just follow this formula always. If you find any other way in any standard book or PPT please tell me. (Standard books and not any blog posts or notes).

---

In chapter 4 ,William Stallings, under 'APPENDIX 4A PERFORMANCE CHARACTERISTICS
OF TWO-LEVEL MEMORIES' the hierarchical formula is given.

Ts = H * T1 + (1 - H) * (T1 + T2)

But it is mentioned that -

When a memory reference is made, an attempt is made to access the item in M1(Cache). If this succeeds, then a quick access is made. If not, then a block of memory locations is copied from M2(main memory) to M1 and the access then takes place via M1.

I think in this case it is mentioned that in case of cache miss required data is read from Cache only. So total time is (Time to read data from Main memory + Time to read from Cache )

If this kind of information is not explicitly mentioned then we can use simultaneous approcah.

Please comment if my understanding is correct.

---

In current scenario by default simultaneous access makes sense. For this question though, it is not clear. If you use the hierarchical formula, we get 13 rt?

---

Yes, for hierarchical  access it becomes 13.

But I think it is indeed the case of simultaneous access as it is not explicitly mentioned that during cache miss(L1 and L2) data is read from L1.

As you said default case is simultaneous access. So if it is explicitly given that during cache miss data is read from L1 only in the question then we will use hierarchical access otherwise default case is simultaneous access.

Please confirm.

---

if nothing is given in the question than we should take simultaneous access only..

---

It should be   h1*t1+(h1-1)[h2(t1+t2)+(1-h2)*(t1+t2+t3)]..!!!!!!!!!!

---

I am so confused between this question and https://gateoverflow.in/11137/coa.

---

whenever in the question if they have the given the "hierarchy" word than we have to consider hierarchy access method     OR   if they have given like this ." if level 1 cache is miss than a word is transfered from level 2 to level 1 than also we have to use hierarchy access method......

if nothing given in the question then by default we have to consider simultaneous access method..only...

---

"ignoring the search time within the cache" what does it mean?

I am also confused with these two examples.

https://gateoverflow.in/11137/coa.

---

Access time = Access time L1 + miss ration of L1* Access Time L2 + miss ratio of L1* miss ration of L2* Memory access time
= 1 + 0.2*10 + 0.2*0.1*500
= 1 + 2 + 10
= 13.0 ns

---

"ignoring the search time within the cache"

THIS  LINE MEANS SIMULTANEOUS ACCESS.

---

Isn’t this line regarding the search time  associated  with checking of tag directory.inside the cache?

Answer 3

given  " ignoring the search time within the cache " it is applicable for associative and set associative mapping any way we will ignore it :
hierarchical access time : h1t1 + (1−h1)×h2×(t1+t2) + (1−h1)(1−h2)(tm+t1+t2)
                                              ans  13ns
simultaneous access time :  h1t1 + (1−h1)×h2×(t1) + (1−h1)(1−h2)(tm)
                                          ans 12.6ns

Answer 4

Tavg=h1xT1+(1-h1)xh2xT2+(1-h1)(1-h2)Tm

Tavg=1x0.8+0.2*0.9*10+0.2*0.1*500=12.6ns