ISRO-2013-16

Question

How much speed do we gain by using the cache, when cache is used $80$% of the time? Assume cache is faster than main memory.

• A. $5.27$
• B. $2.00$
• C. $4.16$
• D. $6.09$

Comments

All ISRO 2013 questions are already added.
https://gateoverflow.in/tag/isro2013

Only 2014 ISRO questions are not fully added here.

---

thank you

Answer 1

$T_{​cache} << T_{memory}$

We can assume memory is accessed only on a cache miss (hierarchical memory access by default) and hence on cache miss we first access cache and then only main memory (both times are added here)

$$\text{Speed Gain} = \frac{ \text{MemoryAccessTime without Cache}}{\text{Memory Access Time with Cache}}$$

                  $=\frac{ T_{memory}}{T_{​cache} + 0.20.T_{memory}} = \frac{1}{\frac{T_{​cache}}{T_{memory}} + 0.20}$
$\frac{T_{​cache}}{T_{memory}}  = x, 0 < x \leq 0.1$ ( Since cache (say last level cache) is faster than memory by at least 10 times)

$\text{Speed Gain} = \frac{1}{0.20 + x} \implies \\3.33 \leq \text{Speed Gain} < 5$  

I will go through 4.16.

Comments

@Kiran that is because by default cache access is hierarchical- that is only if cache is missed we have a memory access. This may not be true always but unless specified in question we can assume this.

Why 10 times- because otherwise there is not much advantage of using a cache- again this is from practical values and L1 cache can be even 100s of times faster compared to memory.

---

Thank u  sir..

bt sir i ws confused dat why arent we multiplying t_cache by 0.80 here.. ( t_cache+0.20 t_memory)

---

Because in case of cache miss also cache is accessed- $0.8 t_{cache}+ 0.2t_{cache}  = t_{cache}$

Answer 2

The correct answer should be option C i.e. 4.16

Probably the assumption : "Cache is faster than main memory" is not sufficient to answer this question precisely.It should be given that "Cache is how many times faster than the main memory".

However with the given information we can guarantee that speed up has to be strictly less than 5.

In general cache memory access is around ~100 times faster than the main memory access so,

ASSUMING : Cache access time is 1 ns & main memory access time is 100 ns.

So If there are total P memory accesses, then

1) Time Required Without Cache - P main memory accesses & 0 cache accesses = ( P * 100 ) + (0 * 1) = 100P nanoseconds.

2) Time Required With Cache - (2/10) * P main memory accesses & (8/10) * P cache accesses

    = ((2P/10) * 100) + ((8P/10) * 1) = (208/10)P nanoseconds.

Speed gain = Time Without Cache / Time With Cache = 100P/{(208/100)P} = 1000 / 208  = 4.8

Thus speed up will be around 4.8(less than 5 but near 5), assuming the cache is 100 times faster than main memory.

_______________________________________________________________________________

Proof for guarantee:

Suppose we are going to make 100 memory accesses.

Then suppose each main memory access takes 1 unit of time.

& all of the cache accesses(= 80 out of 100) takes total x units of time.

Then speed up will be 100 / (x + 20).

Now clearly x is strictly greater than 0 i.e. x > 0

It means (x + 20) is strictly greater than 20 i.e. (x + 20) > 20.

Hence 100/(x + 20) is strictly less than 5.

Now since generally cache is very fast than main memory (around 100 times), value of x would not be too much, so answer should be 4 point “something”.

Answer 3

SPEED GAIN =TIME NEEDED WITHOUT CACHE(SAY tM) /EFFECTIVE MEMORY ACCESS TIME WITH CACHE

NOW, EFFECTIVE ACCESS TIME=hC*tC+(1-hC)*(tC+tM)   NOW hC=0.8 AND 1-hC=0.2

SUBSTITUTING THE VALUES THE DENOMINATOR WILL BECOME (tC+0.2tM)....DIVIDE BOTH NUMERATOR AND DENOMINATOR BY tM.....THE RESULT WILL BE  1/((tC/tM)+0.2)....0<(tC/tM)<1... SO SUBSTITUTING THE LOWER RANGE AND UPPER RANGE THE RESULT IS COMING AS 3.33 AND 5 RESPECTIVELY....ONLY 4.16 FALLS IN THIS RANGE.

HERE WE ARE ASSUMING A WRITE BACK CACHE.

Comments

Write back cache is different where a write happens to memory only during cache replacement and it uses dirty bits.

Answer 4

Answer is C

Comments

((1-0.80)- 0.8/2)=0.24? How?

---

Yeah..my analysis was wrong.

Thanks for pointing it out.

 But answer is C (As per the key )

Can anyone explain.