Question

Consider the following 2-way set associative cache with 24 blocks 8-bits addresses, using the Least Recently used Scheme: Block Valid? LRU Tag Data 1 000 Describe what happens and show the cache state after each of the 001 following sequence of reads. T T 01101 data@01101010 010 T 1 10110 data@10110010 1. 10110000 2. 00101111 011 3. 00110101 100 4. 00110010 5. 01101010 T T 01101 data@01101101 101 . 110 T 111 00101 data 200101111 10110 data@10110111 T

Answer 1

here tag bits=5 (Most significant 5 bits)

Set index = 3bits( Least significant 3 bits)

1) 10110000 => Tag =10110 , Set =000 2 = 010.

Block	valid	LRU	Tag	Data
000	T	T	10110	data@10110000
000	F
001	F
001	F
010	T	T	01101	data @ 10110010
010	T	F	10110	data @ 1011010
011	F
011	F
100	F
100	F
101	T	T	01101	data @01101101
101	F
110	F
110	F
111	T	F	00101	data @ 00101111
111	T	T	10110	data@ 10110111

2) 00101111 => Tag =00101, set =111 =710 . This is a hit. Its LRU bit will be set to True since it is the recent referred one.

Block	valid	LRU	Tag	Data
000	T	T	10110	data@10110000
000	F
001	F
001	F
010	T	T	01101	data @ 10110010
010	T	F	10110	data @ 1011010
011	F
011	F
100	F
100	F
101	T	T	01101	data @01101101
101	F
110	F
110	F
111	T	T	00101	data @ 00101111
111	T	F	10110	data@ 10110111

3) 00110101 => Tag = 00110 , set = 101 = 510.  This a miss. Move the data in block.

Block	valid	LRU	Tag	Data
000	T	T	10110	data@10110000
000	F
001	F
001	F
010	T	T	01101	data @ 10110010
010	T	F	10110	data @ 1011010
011	F
011	F
100	F
100	F
101	T	F	01101	data @01101101
101	F	T	00110	data @ 00110101
110	F
110	F
111	T	T	00101	data @ 00101111
111	T	F	10110	data@ 10110111

4) 00110010 => Tag = 00110, set =010=2. This is a miss. Replace the block in set 2 whose LRU bit is False.

Block	valid	LRU	Tag	Data
000	T	T	10110	data@10110000
000	F
001	F
001	F
010	T	F	01101	data @ 10110010
010	T	T	00110	data @ 00110010
011	F
011	F
100	F
100	F
101	T	F	01101	data @01101101
101	F	T	00110	data @ 00110101
110	F
110	F
111	T	T	00101	data @ 00101111
111	T	F	10110	data@ 10110111

5) 01101010 => tag =01101, set =010 =2. This is a hit, so no changes in cache. Just change of LRU bits.

therefore the final cache is :

Block	valid	LRU	Tag	Data
000	T	T	10110	data@10110000
000	F
001	F
001	F
010	T	T	01101	data @ 10110010
010	T	F	00110	data @ 00110010
011	F
011	F
100	F
100	F
101	T	F	01101	data @01101101
101	F	T	00110	data @ 00110101
110	F
110	F
111	T	T	00101	data @ 00101111
111	T	F	10110	data@ 10110111

If you have any questions, comment down .Also please upvote thanks.