gateoverflow test

Question

Q-Consider the following two types of Cache Designs :

 

Cache 1 : It is a direct-mapped cache with eight 1-word cache lines. The miss penalty is 8 clock cycles.

Cache 2 : It is a two-way associative cache with 1-word cache lines. It can store the same total number of items as Cache 1, but Least-recently-used is utilized to determine which items should be removed from the cache. The miss penalty is 10 clock cycles.

Suppose there are eight memory references like 0, 3, 14, 11, 4, 11, 8, 0

If the caches being empty at beginning then how much time will these designs spend on cache miss penalties ?

 

A. Cache 1 spends 48 cycles and Cache 2 spends 70 cycles

B. Cache 1 spends 64 cycles and Cache 2 spends 80 cycles

C. Cache 1 spends 56 cycles and Cache 2 spends 60 cycles

D. Cache 1 spends 56 cycles and Cache 2 spends 70 cycles

Answer 1

Cache 1
Since its direct mapped cached, we use  x mod 8 to check, in which cache block, following reference will go.
0 - M, 3 - M, 14 - M, 11 - M, 4 - M, 11 - H, 8 - M, 0 -M
So Total misses = 7, Number of cycle spent on misses = 7 * 8    = 56 clock cycles.

Cache 2
Total number of set  = $\frac{8}{2}$ = 4 sets.
Number of line in each set = 2 (since its 2 way set associative)
To address reference into cache block we use x mod 4
0 - M, 3 - M, 14 - M, 11 - M, 4 - M, 11 - H, 8 - M ( In LRU we replace 0 ), 0 - M
So Total misses = 7, Number of cycle spent on misses = 7 * 10 = 70 clock cycles

Option D is correct.