ISI 2019 | PCB CS | Question: 9

Question

Consider a byte addressable memory with $16$ bit addresses and a $2$- way set associative $\mathrm{L} 1$ cache of size $8 \mathrm{ kB}$ (kilobyte). Each cache line is $4$ words long. A process sequentially accesses the following memory addresses:

$\textsf{0x1000, 0x1004, 0x1010, 0x11C0, 0x2000, 0x3000, 0x1006, 0x2001}$

Assuming the $\mathrm{L} 1$ cache is initially empty and the LRU (least recently used) page replacement policy is used, indicate whether the cache access will result in a hit or a miss for each of the above addresses.

Comments

what will be the word size? should i take 8 bits?

Answer 1

Word addressable

1 word = 2 byte = 8 bit , then 4 words = 4 * 16 bit = 64 bit = 8 bytes,

Block line address is of 3 bits 

Number of blocks in cache \( ( L_1) \) = \( \frac{cache size }{block size} = \frac{8 kB}{8 B} = 2^{10} blocks \)

Number of sets in cache \( ( L_1) \) = \( \frac{No. of Blocks}{associativity} = \frac{2^{10}}{2} = 2^{9} \  sets \)

Tag size = \(16 \ bit - 12 \  bits = 4 \ bits \)

Sequentially Access of memory address

Hexa	Decimal Tag   Set no.     cache byte	Set no.	Hit / Miss	Memory block no.
1000	0001 000000000 000	0	Miss	512
1004	0001 000000000 100	0	Hit	512
1010	0001 000000010 000	2	Miss	514
11C0	0001 000111000 000	56	Miss	568
2000	0010 000000000 000	0	Miss	1024
3000	0011 000000000 000	0	Miss	1536
1006	0001 000000000 110	0	Hit	512
2001	0010 000000000 001	0	Hit	1024

---

Byte addressable

1 word = 1 byte = 8 bit , then 4 words = 4 bytes,

Block line address is of 2 bits

Number of blocks in cache \( ( L_1) \) = \( \frac{cache size }{block size} = \frac{8 kB}{4 B} = 2^{11} blocks \)

Number of sets in cache \( ( L_1) \) = \( \frac{No. of Blocks}{associativity} = \frac{2^{11}}{2} = 2^{10} \ sets \)

Tag size = \(16 \ bit - 12 \  bits = 4 \ bits \)

Sequentially Access of memory address

Hexa	Decimal Tag   Set no.     cache byte	Set no.	Hit / Miss	Memory block no.
1000	0001 0000000000 00	0	Miss	1024 occupy at set 0 col 1
1004	0001 0000000001 00	1	Miss	1024 occupy at set 1 col 1
1010	0001 0000000100 00	4	Miss	1028 occupy at set 4 col 1
11C0	0001 0001110000 00	112	Miss	1136 occupy at set 112 col 1
2000	0010 0000000000 00	0	Miss	2048 occupy at set 0 col 2
3000	0011 0000000000 00	0	Miss	3072   Replace set 0 col 1 with 0011
1006	0001 0000000001 10	1	Hit	1025  at set 1 col 1
2001	0010 0000000000 01	0	Hit	2048  at set 0 col 2