1 = Direct Mapped (2 bit offset, 4 bit set, ...) ------------- 0x7AC = 0111 1010 1100 Offset: 0 Set: 0b1011 = 0xB = 11 Tag: 0b01 1110 = 0x1E It's in the cache but invalid. 0x24 = 0010 0100 Offset: 0 Set: 0b1001 = 0x9 = 9 Tag: 0 It's in the cache and valid, we read 0x01. 0x99F = 1001 1001 1111 Offset: 0b11 = 0x3 = 3 Set: 0b0111 = 0x7 = 7 Tag: 0b10 0110 = 0x26 It's not in the cache. 2-way Set Associative (2 bit offset, 3 bit set, ...) --------------------- 0x435 = 0100 0011 0101 Offset: 0b01 = 1 Set: 0b101 = 0x5 = 5 Tag: 0b010 0001 = 0x21 It's in the cache and valid, we read 0xAD. 0x388 = 0011 1000 1000 Offset: 0 Set: 0b010 = 0x2 = 2 Tag: 0b001 1100 = 0x1C It's not in the cache. 0x0D3 = 0000 1101 0011 Offset: 0b11 = 3 Set: 0b100 = 0x4 = 4 Tag: 0b110 = 0x6 It's in the cache but not valid. Fully Associative (2 bit offset, 0 bit set, ...) ----------------- 0x1DD = 0001 1101 1101 Offset: 0b01 = 1 Set: 0 Tag: 0b0111 0111 = 0x77 It's in the cache but not valid. 0x719 = 0111 0001 1001 Offset: 0b01 = 1 Set: 0 Tag: 0b01 1100 0110 = 0x1C6 It's in the cache and valid, we read 0x11. 0x2AA = 0010 1010 1010 Offset: 0b10 = 2 Set: 0 Tag: 0b1010 1010 = 0xAA It's not in the cache. 2 = 1 Can we say that the block size/cache line size is greater than 8 bytes? ------------------------------------------------------------------------- No, because the access to address 8 misses. 1 Can we say that the block size/cache is less than or equal to 8 bytes? ------------------------------------------------------------------------ Yes, because the access to address 8 misses! 2 What is the associativity of the cache? ----------------------------------------- We know that the cache is at most 2-way set associative because the fourth access caused one of the previous entries to be evicted. 2 Then is the cache 2-way set associative or direct mapped? ----------------------------------------------------------- Since we know that the block size is between 1-8 bytes, we can exhaustively check this. Is it a direct-mapped cache? Block size 1 byte: 16 sets, 4 bits per set, notice that the access to address 16 would evict 0. This does not match the behavior we observed. Set indices: 0->0000 8->1000 16->0000 Block size 2 bytes: 8 sets, 3 bits per set, notice that the access to address 16 would evict 0. This does not match the behavior we observed. Set indices: 0->000 8->100 16->000 Block size 4 bytes: 4 sets, 2 bits per set, notice that the access to address 16 would evict 0. This does not match the behavior we observed. Set indices: 0->00 8->10 16->00 Block size 8 bytes: 2 sets, 1 bit per set, notice that the access to address 16 would evict 0. This does not match the behavior we observed. Set indices: 0->0 8->1 16->0 Therefore the cache must be 2-way set associative. 3 How many sets could this cache have? -------------------------------------- Notice that even though we have determined the cache's associativity, we have not determined how many sets it has. To determine the number of sets we must also know the block size. Since the cache is 2-way set associative, and the cache size is 16 bytes, we can write: 16 = 2*num_sets*block_size Therefore the number of sets could be 1, 2, 4, or 8, and the block size could be 1, 2, 4, or 8 bytes. Notice that in each of these combinations, the offset and set index in total will use 3 bits. If we want to be thorough, we can exhaustively check which cases are possible: If the cache has 8 sets, then 3 bits are dedicated to the set index. 0->000, 8->000, 16->000 This is one possible configuration of the cache as the access to 16 would evict 8. If the cache has 4 sets, then 2 bits are dedicated to the set index, with 1 bit for the block offset. 0->00, 8->00, 16->00 This is one possible configuration of the cache as the access to 16 would evict 8. If the cache has 2 sets, then 1 bit is dedicated to the set index, with 2 bits for the block offset. 0->0, 8->0, 16->0 This is one possible configuration of the cache as the access to 16 would evict 8. If the cache has 1 set, 3 bits are used for the block offset. 0->0, 8->0, 16->0 This is one possible configuration of the cache as the access to 16 would evict 8. Note that this configuration is also fully-associative! 4 How many bits will tag use given an n bit address? ---------------------------------------------------- n - 3 bits