in this video we're going to look at how a set of accesses map to caches with different types of parameters in all of these examples have a cache that has 128 bytes worth of storage and we're going to assume that the addresses that are fed to the cache are 12 bits wide well typical processors generally have 32 or 64 bit addresses for simplicity we're going to have 12 bits in this example and so in this first pass from this first example we're going to look at a direct mapped cache that has 32 byte blocks so one of the first things we want to figure out is how many bits of the address we're going to need for the offset for the set or the index and then finally for the tag and so first for the number of offset bits that's based off of the number of bytes and a block and so we would take the log base 2 of the number of bytes in a block and we would find that that's equal to 5 so that means we need 5 bits for the offsets from there we can then look at the number of sets in this cache the total cache capacity is 128 bytes and each set is going to contain 32 bytes so if we divide these two this says that we have a total of four sets and from there we can figure out how many bits we need so the number of sets or index bits that we need to address one of these sets is the log base 2 of 4 and that would mean we need 2 bits for the index or the sets and then finally for the number of tag bits basically anything that remains our addresses for the tag so if we've got 12 total and we've already used 5 of them for the offset 2 of them for the index of the set that leaves us with five bits remaining for the tag so the uppermost 5 bits would be for the tank and as an example of how you would break out these different parts if we had an address of X 0 6 0 which in binary breaks down into 0 0 0 0 1 1 0 0 0 0 0 he sends we have 5 offset bits the least significant 5 bits are the offsets with 2 set or index bits the next two bits would be our index or our set and then everything else that remains would be our tag bits to look at how a set of addresses would map to a particular cache or a cache for this configuration or this shows a simplified version of the cache so we found that we had 4 sets and so I'm showing the 4 set 0 through 3 and then I'm showing the tag that is currently stored at the set as well as whether it's valid or not and while each of these sets would also have data that doesn't really impact how a set of addresses would map to this particular cache and whether or not they'd hit or miss and then to have a particular example here we've got a set of 9 addresses that we're going to look at in sequence and I've already broken these up into the tag set and offset based off of the calculation that we did previously and so we're going to look at these accesses both on the first set of accesses on the second time through so if this was in a loop and we access these repeatedly because we'll find that this will actually change whether some of the accesses hit or miss in the cache and so to start off on the first line we've got address zero seven zero that maps to set three or set one one so we would make that valid and then we'd put in the tag here which is zero and we would say since this wasn't in the cache this was a miss going to the next one it maps to set zero there is nothing currently in set zero so this is also a Miss and so then we would put tag one into here and we would set this to valid for the next axis it goes back to set one one or set three and we look at that and we see that the tag that's currently in there of zero matches the tag that this new request is for so this would be a hit the next request accesses set zero we go over there and find that it's valid but the tag one in the cache does not match the tag one one that is in the request so this is a Miss and it means we're also going to change the tag in the cache to be one one because we're going to bring in this new cache line and replace the old one for the next axis we're again going back to sets zero and we see that this new axis is looking for tag one but that doesn't match the tag of one one we have in our cache currently so this would be a Miss we would again replace the entry and so that would update our tag to one for the next line we're looking at sets 1-1 we currently have a tag of zero in there but we're looking for a tag of one zero so that would mean we'd have a Miss and we're going to update our tag here to one zero the next axis is going back to set zero it's looking for tag one and since we currently have tag 1 in there already we would have a hit for the next one we're going back to set zero again the tag of one that's currently in the cache does not match the tag of one one one zero so we would have a Miss and we'd update our tag for that entry and then finally for the last access we are looking at sets three we find that it's looking for tag zero but we currently have tagged one zero in there so this is a Miss and we would update this tag to be zero and so this would be the pattern of misses and hits we'd have for the first time we had this sequence of addresses if this sequence is repeated again we'd have the cache in its current state at the end so we could repeat this and so looking at the first axis again it's going to set three and we see that it's looking for tag zero and if we look at our cache we see the tag zero is already there so this first access is a hit when it would they miss the first time through for the the second access we're going to set 0-0 and looking for tag one but unfortunately the tag is not doesn't match so we've got another miss and we would update our tag to be one for the next access we're going back to set three and we're finding that we're looking for tag zero also have tag zero so like the first time this is going to be a hits for the next axis we're looking at set zero again and we're looking for tag one one which doesn't match what we have in there so this is a Miss and we'd update our tag to 1 1 the next axis is going back to set zero and again now looking for tag 1 which we just replaced so we're going to have another Miss and we're going to fill in the block with tag 1 again for the next axis we're going back to set 3 we're looking for 1 0 which is not currently in the cache so we have a Miss and we update our tag to 1-0 for that entry for the next access we're looking at sets 0 0 and we're looking for tag 1 which is what we have in there so we have a hits for the second-to-last address we're looking at set 0 again we're looking for the tag 1 1 1 0 and that isn't in the cache currently so this is going to be a Miss and we'd update our tag again and then finally for the last access we're going to set three looking for tag zero but finding that we have currently tagged one zero so this is a Miss and we'd replace it with tag zero and so then we could look at what was the hit rates for these two different sets so the first time through for our hit rates we found that we hits two of the times and we had a total number of nine accesses so this will give us a hit rate of approximately 22% and then the second time through we have a hit rate where if you look we look we see we have three hits and again we had nine total accesses so in the second time through our hit rate improved to 33%