Question

Suppose we have a byte-addressable computer with a cache that holds 8 blocks of 4 bytes each. Assuming that each memory address has 8 bits and cache is originally empty, for the cache mapping technique, two-way set associative, trace how cache is used when a program accesses the following series of addresses in order:

0x01, 0x04, 0x09, 0x05, 0x14, 0x21, and 0x01.

Answer 1

given

memory is byte addressable

total number of blocks in cache = 8 and size of each block = 4 byte

now since the memory is byte addressable to represent 4 byte of a single block we require minimum 2 bits ( 00 , 01 , 10, 11)

cache is 2 way set associative which means one set of cache will contain 2 blocks

number of sets in cache = ( total number of blocks in cache ) / number of blocks in each set( = 2 )

number of sets in cache = 8/2 = 4 sets

now to represent 4 distinct set we require minimum 2 bits ( 00 , 01 , 10, 11 )

address size is 8 bits now address format for set associative cache is

tag bits ( 8 - 4 ) = 4 bits

set number bits

block size ( 2 bits )