5,078 views
6 votes
6 votes

A computer system contains a main memory of 32K 16-bit words. It also has a 4Kword cache divided into four-line sets with 64 words per line. Assume that the cache is initially empty. The processor fetches words from locations 0, 1, 2, . . ., 4351 in that order. It then repeats this fetch sequence nine more times.The cache is 10 times faster than main memory. Estimate the improvement resulting from the use of the cache. Assume an LRU policy for block replacement.


2 Answers

Best answer
10 votes
10 votes

$\text{Memory access time without cache} = 4352 \times 10 x = 43520x$, where $x$ is the time for one access.

In cache we have 64 words per line and 4 lines per set (4 way associativity) and total size is 4096 words. So,

$\text{number of sets}= \frac{4096}{64\times 4}= 16$

So after accessing $16\times 64=1024$ words (0-1023) all the sets will be filled with one entry each. But with 4-way associativity each set has space for 3 more. So filling can go like this for 4096 words (0-4095). After this next entry (cache line from 4096-4159) will go to first set and will replace the cache line 0-63 due to LRU policy. Like wise total no. of cache replacements = (4351-4096)/64 = 256/64 = 4.

Now for the second iteration the first four cache line accesses will be cache misses as they got replaced. But these cache lines will be replacing the oldest used one in the set. For example cache line 0-63 will be replacing 1024-1095.  Now the cache line 1024-1095 will in turn be replacing 2048-2111 and likewise all new cache line accesses will be cache misses (LRU works badly). This will trigger 16 cache line misses - 4 each from the first four sets. For 5th set to 16th set, there won't be any cache miss. Now, for the cache lines 4096-4351, there will be 4 more cache misses which are again coming from the first 4 sets. So, totally 16+4 = 20 cache misses. (Shown in figure at end)




Thus,

$\begin{align*}\text{Access time with cache} &=\text {no. of memory access} \times \text{hit time} \\&+ \text{no. of cache misses}\times \text{memory access time for a block}\\ &\text{(Hierarchical access taken as default)} \\&= (4352 \times 10 ) \times 0.1x + (68 + 9\times 20) 64x \\& = 20224x \end{align*} $

PS: When a cache miss happens a cache line is fetched from main memory. So, we have to wait for the whole memory fetch time for one cache line and include it in the miss penalty. But in practice, this is avoided by a technique called sniffing, where the requested data is given to the CPU as soon as it is available. Anyway for problems unless otherwise stated, include the whole block fetch time as miss penalty.

So,

$\text{Performance improvement} = \frac{43520x}{20224x} = 2.15\text{ times}$

Associative cache replacement for second iteration

edited by
2 votes
2 votes

Now, if memory access time = x

Therefore, cache access time = (x / 10) = 0.1x

 

Now, access time without using cache

= x (Here, time is only determined by the memory access time)

 

Now, access time using cache

= (h * cache access time) + ((1 - h) * (cache access time + memory access time))

= (0.64 * 0.1x) + (0.36 * (0.1x + x))

= 0.46x

 

Therefore, improvement

= access time without cache / access time with cache

= x / 0.46x

= 2.17

Answer:

No related questions found