Question

Assume a memory model where you have a cache size of 4 blocks, a block size of 8, and addresses from 0 through 511. Assume that the n-way associative cache and fully associative cache use a LRU (least recently used) eviction strategy. Consider the following sequence of memory accesses: 17, 66, 22, 66, 80, 41, 85, 66, 17, 104.

1. (a) Show the updates to a 2-way associative cache in a table using a similar format to the table shown on Slide 69 of Module 3. All of the values in the table should be decimal numbers (not bits). Since there are 10 accesses, there should be 10 rows of data in the table.

2. (b) Show the updates to a fully associative cache in a table using a similar format to the table shown on Slide 70 of Module 3. All of the values in the table should be decimal numbers (not bits). Since there are 10 accesses, there should be 10 rows of data in the table.

Answer 1

As there is not format for answers is mentioned I have done the best I could it to make it easy to understand.

Columns Access1 to Access 10 shows the states of each block of the cache.

A GREEN colored cell denotes a new insertion of a block which did not need any replacement

A RED colored cell denotes accesses where a replacement(Or eviction of existing block needed)

2-Way Associative mapping

The cache has 4 blocks in total.

In 2 way mapping all the 4 blocks are divided into 2 sets;Set 0 and Set 1

There 4*8 32 blocks in cache in total. 5 bit are needed to address each block.

As there is only 2 sets only. Least significant 4 bits will be used for block offset and 5th bit will be used for deciding in which cache block should the incoming block should be placed.

For Eg. Block 17

Binary 17=10001 5th bit is 1 and it will be placed in Set 1

2-Way Set associative m 41 41 80 85 41 Set 0 17 1. 17 85 Set 1

Fully Associative Cache

In this any block can be placed anywhere in the cache.

Fully Associative Block 1 Block 2 Block 3 Block 4 17 17 17 17 .1 AS MS 85 80 17