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

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