Question

You have a 2-way set associative L1 cache that is 8KB, with 4-word cache lines. You get the following sequence of writes to the cache --each is a 32-bit address in hexadecimal 0x32E4 0x8000 0x1F50 0x8004 0x72EC OxDOOC 0x800C 0x72E8 0x4008 OxD000 0x82E0 a) [7 Pts] How many cache misses occur with an LFU (Least Frequently Used) policy? Give a detailed answer and fill in the table below for each address reference Set Index (in hex) Memory address(in hex) 0x32E4 0x8000 Tag Hit/Miss Data to be placed in set .. way... b) 3 Pts] For part (a) indicate the type of miss (compulsory, conflict, capacity)for each address reference Hit/Miss Memory address 0x32E4 0x8000 Type of miss

Answer 1

Since 1 word = 4 byte. Hence size of cache line = 4*4 = 16 Bytes

Number of bits needed for line offset = log₂ 16 = 4 bits

Total number of cache lines = size of cache / size of line = 8KB/ (4*4) Byte = 512 lines

Since it's a 2-way set associative memory, hence number of sets = number of lines/2 = 512/2 = 256 sets

Hence number of bits needed for set number field = log₂ 256 = 8 bits

So out of 32 bits field, last 4 bit will be line offset, then 8 bits will be set number field and number of bits for tag = 32-8-4 = 20 bits

For example address 0x32E4 , last hexadecimal digit is 0x4, which is line offset, Set index will be 0x2E and remaining is tag field which is 0x00003.

Now given the sequence of address, since rightmoat 16 bits are given so we can append 16 zeroes to make them 32 bit address.

Here in above above memory request, hit occurs only on following addresses:-

0x8004

0x800C

0x72E8

So out of 11 request there are 3 hit and 8 miss.

So the table will be filled as:-

Memory address	Tag	Set Index	Hit/miss	Set...Way...
0x32E4	0x00003	0x2E	miss	Set 2E Way 0
0x8000	0x0008	0x00	miss	Set 00 Way 0

b. 0x32E4 miss compulsory miss since set 2E accessed for first time

0x8000 miss compulsory miss since set 00 accessed for the first time

Please comment for any clarification.