Question

Here is a series of address references given as word addresses: 18, 19, 27, 16, 21, 0, 64, 48, 19, 11, 19, 22, 4, 27, 6, and 27. Assuming a direct-mapped cache with 16 one-word blocks that is initially empty, label each reference in the list as a hit or a miss and show the final contents of the cache.

Answer 1

Solution:

Given,

=>Number of blocks = 16

=>Direct mapped cache is used.

=>Addresses = 18, 19, 27, 16, 21, 0, 64, 48, 19, 11, 19, 22, 4, 27, 6 and 27

Explanation:

=>In direct mapped cache we use mapping function i % B = p where i is the address, B is the number of blocks in cache, p is the block number in cache in which main memory address will be mapped, % is modulus function.

=>By default we use LRU(least recently used) algorithm.

Mapping addresses:

18:

=>18 % 16 = 2 => block 2 => Miss

19:

=>19 % 16 = 3 => block 3 => Miss

27:

=>27 % 16 = 11 => block 11 => Miss

16:

=>16 % 16 = 0 => block 0 => Miss

21:

=>21 % 16 = 5 => block 5 =>Miss

0:

=>0 % 16 = 0 => block 0 => Miss(replace 16 with 0)

64:

=>64 % 16 = 0 => block 0 => Miss(replace 0 with 64)

48:

=>48 % 16 = 0 => block 0 => Miss(replace 64 with 48)

19:

=>19 % 16 = 3 => block 3 => Hit

11:

=>11 % 16 = 11 = > Block 11 => Miss(replace 27 with 11)

19:

=>19 % 16 = 3 => block 3 => Hit

22:

=>22 % 16 = 6 => block 6 =>Miss

4:

=>4 % 16 = 4 => block 4 =>Miss

27:

=>27 % 16 = 11 => block 11 => Miss(replace 11 with 27)

6:

=>6 % 16 = 6 => Block 6 => Miss(replace 22 with 6)

27:

=>27 % 16 = 11 => block 11 => Hit

Final cache content:

48

18

19

4

21

6

27

     0         1     2              3           4         5         6      7 8 9 10    11    12 13 14 15

I have explained each and every part with the help of statements attached to the answer above.