retagged by
10,110 views
8 votes
8 votes

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.

  1. $5.27$
  2. $2.00$
  3. $4.16$
  4. $6.09$
retagged by

5 Answers

Best answer
25 votes
25 votes
$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.
selected by
6 votes
6 votes

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

1 votes
1 votes

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.

0 votes
0 votes

Answer is C

edited by
Answer:

Related questions

9 votes
9 votes
7 answers
1
makhdoom ghaya asked Apr 26, 2016
8,538 views
A pipeline $P$ operating at $400$ MHz has a speedup factor of $6$ and operating at $70$% efficiency. How many stages are there in the pipeline?$5$$6$$8$$9$
3 votes
3 votes
2 answers
2
makhdoom ghaya asked Apr 27, 2016
3,597 views
In 8085 microprocessor, the ISR for handling trap interrupt is at which location?$3CH$$34H$$74H$$24H$
5 votes
5 votes
5 answers
3
makhdoom ghaya asked Apr 27, 2016
3,823 views
How many number of times the instruction sequence below will loop before coming out of the loop? MOV AL, 00H A1: INC AL JNZ A11255256Will not come out of t...
2 votes
2 votes
3 answers
4
makhdoom ghaya asked Apr 27, 2016
4,410 views
In $8086$, the jump condition for the instruction $JNBE$ is?CF = 0 or ZF = 0ZF = 0 and SF = 1CF = 0 and ZF = 0CF = 0