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

@Yashraj_Jain

I didn't get you. ISRO official key is "Option C" which is conceptually correct. 

---

Can anyone explain why we are multiplying 1ns with 0.8 becuase we will access L1 always even if the element is not present ?
 

---

We will not consider the access times during misses in each level

Answer 1

Average memory access time

$ =  h_1 \times t_1 + (1-h_1) \times h_2 \times (t_2 + x_1)  + (1-h_1) (1-h_2)  (t_m + x_1 + x_2)$

Here, $x_1$ and $x_2$ are the search times for $L_1$ and $L_2$ caches respectively and as per the question we can consider them as $0.$

So, average memory access time
$ = 0.8\times 1 + 0.2 \times 0.9 \times 10 +  0.2 \times 0.1 \times 500$
$= 12.6ns.$

Option C.

Comments

rather we can also write like this : removing 1 from 10 in L2 and 10 from 500 in MM access times with eqn : (1+0.2(9+0.1(490))) = 12.6 ns which is the exact answer.  

 

 

When you algebraically factor the simultaneous access formula $T_{avg} = (1-M_1)T_1 + M_1(1-M_2)T_2 + M_1 M_2 T_m$, it simplifies beautifully to:

$$T_{avg} = T_1 + M_1 \cdot [ (T_2 - T_1) + M_2 \cdot (T_m - T_2) ]$$

Here is how the numbers plug into that exact equation:

• L2 Adjustment: $T_2 - T_1 = 10 - 1 = 9$

• Main Memory Adjustment: $T_m - T_2 = 500 - 10 = 490$ (rather than $489$)

Putting it together:

$$T_{avg} = 1 + 0.2 \cdot (9 + 0.1 \cdot 490)$$

$$T_{avg} = 1 + 0.2 \cdot (9 + 49)$$

$$T_{avg} = 1 + 0.2 \cdot (58)$$

$$T_{avg} = 1 + 11.6 = 12.6 \text{ ns}$$

---

I was looking for this formula, but I cannot understand why 10 will be substracted from 500. In original formula it is access time of main memory, and in the question mm access time is given as 500. So it should be 500 and not 490, right? Or am I wrong somewhere

---

see this ans by me : https://gateoverflow.in/3653/gate-it-2004-question-12-isro2016-77?show=547930#a547930 @Sirr

Answer 2

Answer must be C - 12.6ns

"ignoring the search time within the cache" means on L1 miss, we access L2, but we ignore the time it took to detect L1 miss. Similarly, on L2 miss, we access main memory, but we ignore the time it took to detect L1 miss & L2 miss.

So, Average access time of the system (ignoring the search time within the cache) = $(0.8)(1) + (0.2)(0.9)(10) + (0.2)(0.1)(500) $

=  $12.6ns$

NOTE: The above formula has nothing to do with so-called "simultaneous access" or "look-aside cache".. It's All hierarchical only.. NO famous Standard Book mentions any concept called "simultaneous access" or "look-aside cache".. These concepts exists but in theory, and NO GATE PYQ is based on them. In ALL GATE PYQs, it's Always Hierarchical access only (look through).

Comments

got it

Answer 3

option C

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

tm- main memory access time

Comments

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

---

there is no concept of simultaneous access , please refer Deepak poonia sir's answer below
https://gateoverflow.in/3653/gate-it-2004-question-12-isro2016-77?show=489139#a489139

---

https://youtu.be/W442i0Q_pPg?si=4sVLvWvguCQhJ9Q0

Answer 4

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

Comments

simultaneous access time :  h1t1 + (1−h1)×h2×t2+ (1−h1)(1−h2)(tm) --> correction

Answer 5

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

Answer 6

Average access time = [H1 * T1] + [(1 - H1) * Hm * Tm]
H1 = 0.8, (1 - H1) = 0.2
H2 = 0.9, (1 - H2) = 0.1
T1 = Access time for level 1 cache = 1ns
T2 = Access time for level 2 cache = 10ns
Hm = Hit rate of main memory = 1
Tm = Access time for main memory = 500ns
Average access time = [(0.8 * 1) + (0.2 * 0.9 * 10) + (0.2)(0.1) * 1 * 500]
= 0.8 + 1.8 + 10
= 12.6ns