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 3 = What is the miss rate? ---------------------------------------------------- Every block will hold 4 integers (16B / 4B per int), so there will be a miss 1/4 of the time. 1 In the previous example, what code modifications can change the miss rate? ---------------------------------------------------- Changing the order of the array access or swapping the inner and outer for loops will accomplish this (not doing both) 2 What cache changes can changes the miss rate? ---------------------------------------------------- 2.1 Changing the cache size? ---------------------------------------------------- No, it doesn't matter how big the cache is in this case (as long as the block size doesn't change). We will still be pulling the same amount of data each miss, and we will still have to go to memory every time we exhaust that data 2.2 Changing the associativity ---------------------------------------------------- No, this is helpful if we want to reduce conflict misses, but since the data we're accessing is all in contiguous memory (thanks arrays!), booting old data to replace it with new data isn't an issue 2.3 Changing the block size ---------------------------------------------------- Yes, bigger blocks mean we pull bigger chunks of contiguous elements in the array every time we have a miss. Bigger chunks at a time means less misses down the line. Likewise, smaller blocks increase the frequency with which we need to go to memory.