11.3k views
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?
1. $13.0$
2. $12.8$
3. $12.6$
4. $12.4$

edited | 11.3k views
+1
what is the answer in ISRO key?
+1

The answer in the ISRO key is-  C. 12.6 and that means that it uses simultaneous access.

0

AMAT = 1(L1 access) + 0.2(L1 miss) * penalty 1

similarly penalty 1 = (1+10) + 0.1 * penalty 2

penalty 2 = 500+1+10.

penalty 1 becomes 11 + 0.1 * 511 = 62.1

AMAT becomes 1 + 0.2 * 62.1= 1 + 12.42 = 13.42

@srestha what is wrong with these steps for hierarchical access? m getting .42 extra :(

0
getting 13 for simultaneous access.
0
Plz check ans

Here hierarchical and simultaneous both gives correct result
0

@tusharp

AMAT = 1(L1 access) + 0.2(L1 miss) * penalty 1

i hope you written, AMAT = L$_1$ access + (L1 miss) * penalty$_1$

but it is wrong...

the correct one is, AMAT = ( L$_1$ hit ) * ( L$_1$ access ) + ( L1 miss ) * penalty$_1$

where penalty$_1$ = ( L$_2$ hit ) * ( L$_1\; access$ + L$_2\; access$ ) + ( L$_2$ miss ) * penalty$_2$

where penalty$_2$ = (1) * ( L$_1\; access$  +  L$_2\; access$  + Memory Access )

explanation :-

with the hit$_1$ probability, you get the word from L$_1$, with the miss$_1$ probability you have to do something.

do something = penalty$_1$, what is value of penalty$_1$?

with the hit$_2$ probability, you get the word from L$_2$ but note that in sequential you are already consumed L$_1$ time, with the miss$_2$ probability you have to do something more.

do something more = penalty$_2$, what is value of penalty$_2$?

with the hit$_3$ = 1 probability, you get the word from memory but note that in sequential you are already consumed L$_1$ time + L$_2$ time.

0

I'm also thinking same but some reference is giving penalty1 = L2 Hit*(L2 access) + L2 miss*(penalty2).

which means they don't add the L1 access time while accessing L2,but it should be as per my understanding.

see page number 17 in http://inst.eecs.berkeley.edu/~cs61c/resources/su18_lec/Lecture16.pdf

here it should be (c1 + c2) - https://www.geeksforgeeks.org/multilevel-cache-organisation/

0
My previous comment is for strict hierarchy but not for simultaneous access
0
I'm also talikng about hierarchical model & by default is hierarchical model if nothing is defined.
0

Are you sure that those links are for hierarchal access ?
0
yes.

if nothing is explicitly mentioned about simultaneous access, then we should consider always the hierarchical access, because simultaneous is the special case.
0
Then i don't know, how they did

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. So, may be they are telling to ignore the search time for $L1$ and just consider the time for $L2$ for an $L1$ miss and similarly just consider memory access time for $L2$ miss. This is nothing but simultaneous access.

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

Access time for simultaneous access,

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

Both options in choice.

by Veteran (425k points)
edited by
+1
"ignoring search time in cache  " means what ?? does it means simultaneous [email protected] sir????
+2
@shikha that's the only thing I can assume
+6
guys is this formula correct for hierarchical access,

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

how do you get this, ??

t1+(1-h1)t2+(1-h1)(1-h2)tm
+23
Do simplification - you will get.

How I got the formula is simpler than that- Just following the access sequence
L1 is accessed everytime, L2 on L1 miss and memory on L2 miss. So, the formula follows logically.
0
94.92ns i am getting this answer with my formula, i cant simplify it to the second one?!
+34

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

This is really useless maths as the final formula is more intuitive than the initial one :O

0
yes, i got it thanks.

+11
We can look Both cases like this-

In case of Hierarchal access:
AMAT's formula is = Hit Time + Miss Penalty * Miss Rate.

In case of Simultaneous access:
AMAT's formula is = Hit Time X Hit Rate + Miss Penalty * Miss Rate

AMAT is Average (Or Effective) Memory Access Time.
+1
if heirarchial access or cache keyword is mention in question then in that case cpu will access the data only from level-1 cache ,,,,,,,,

otherwise if simultaneous access or not any keyword is mentioned then it will be simultaneous memory access(it is also bydefault memory access)

formula for heirarchial memory access Tavg=h1t1+(1-h1)h2(t2+t1)+(1-h1)(1-h2)h3(t3+t2+t1)+..........and so on

for simultaneous memory access Tavg=h1t1+(1-h1)h2(t2)+(1-h1)(1-h2)h3(t3)+..........and so on
+3

@Arjun Sir, Please verify my explaination and correct me if I am wrong.

I think that even if we consider it as hierarchical access then also answer will be 12.6 ns (option c). Following is the explaination

In case of hierarchical access we first search the L1 cache ( Let searching time be TL1 search ), if search is success then access L1 cache ( Let access time be TL1 access )  else if L1 search failed then search L2 cache ( Let searching time be TL2 search ), if search is success then access L2 cache ( Let access time be TL2 access ) else if L2 search failed then access main memory.

So,

Tavg = p1 * (TL1 search + TL1 access)  +  (1-p1) * p2 * (TL1 search + TL2 search + TL2 access)  +  (1-p1) * (1-p2) * (TL1 search + TL2 search + main memory access).

Now, as in the question it is mentioned to ignore the search time within the cache. So we can eliminate both TL1 search and TL2 search.

So, final formula is

Tavg = p1 * (TL1 access)  +  (1-p1) * p2 * (TL2 access)  +  (1-p1) * (1-p2) * (main memory access).

So, this gives answer as 12.6 ns.

0

@Vishal Rana your approach seems correct

0
my opinion would be not to remeber any formula. the one you gave is easy to derive while solving .
0
What is the reference of this formula
option C

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

tm- main memory access time
by Active (1.3k points)
+1
which  access  method  have to be  use ..  simultaneous  or  hierarchical..?
0
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).
+1

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.

+4
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?
+3
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.

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

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

+1

I am so confused between this question and

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

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

I am also confused with these two examples.

+2
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
+14

"ignoring the search time within the cache"

THIS  LINE MEANS SIMULTANEOUS ACCESS.

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
by (71 points)
+1 vote

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

by Boss (10k points)