Cache Memory 2: Direct Mapping

the size of the cache is always significantly smaller than the size of main memory so a way is needed to decide what parts of memory go in the cache and where they go this video focuses on a simple cache mapping scheme known as a direct mapping first recall that the cache consists of tagged lines a portion of each line is a tag and the remaining portion of each line is a block this is the actual storage portion of the line the storage portion of each line is equal in size to one block of memory which itself consists of several memory words in this diagram we'll list one line in memory for each block the same way we are depicting things in the cache so this is block zero in block one in block two however memory is typically addressed using memory addresses and there are multiple addressable memory words within each block but before i start indicating what those addresses are let's make up some numbers for various sizes our memory word size will be eight bits or one byte our block size will be four words or bytes which adds up to 32 bits our cash will have 2 to the 14 number of lines that's roughly 16 000 lines in the cash that means that it takes 14 bits to refer to any particular line in the cache and if you want to refer to a specific word stored in the cache that will require 16 bits because we have four words per block and it takes two bits to represent the values 0 1 2 and 3. so we add those two to the 14 to get 16 bits per word finally each memory address will consist of 24 bits that means the memory can store 2 to the 24 bytes but the cache can only store 2 to the 16 bytes and 24 is a lot more than 16. so which blocks of memory go in the cache first note that if we divide the 2 to the 24 bytes in memory by the 2 to the 16 bytes of the cache that leaves us with 2 to the 24 minus 16 which is 2 to the 8 which is 256. so memory is 256 times larger than the cash in other words we can break memory into 256 distinct cash sized chunks here is a zoomed out view of a portion of memory and the cache and you can see that the memory is broken up into several cache sized chunks now i've just highlighted the first line of each of these chunks in green and the second line of each of these chunks in red and i've done the same in the cache and the reason for that is this in a direct mapping only the green lines can ever occupy this green line in the cache and only the red lines can ever occupy this red line in the cache and so on so if you are the fifth line within your particular cash sized chunk of memory then the only place in the cash that you are ever allowed to occupy is the fifth line of the cache so this red line in the cache must be one of those lines and each of these red lines in memory can never occupy any other place in the cache except for this one particular red line but how does the cache know which of these lines in memory it currently holds well that's what the tags are for whereas the block portion of the cache contains data that exactly matches the particular memory contents that it was copied from the tag portion of the cache will contain addressing information for this to make sense recall that memory addresses are 2 to the 24 bits whereas within a cache we only have 2 to the 16 addressable words a consequence of this is that within each cash sized chunk of memory the first eight bits of the memory address will be identical in fact i'll write them out here using hexadecimal these first eight bits of the memory address correspond to the tags stored in the cache so if at this location in the cache i was to store the hex value 0 2 meaning the bit sequence of zeroes a one then a zero then that would mean that this particular green line came from this particular memory location and if the tag for this cache line were four then that would mean that that red line came from this memory address let's put all of this together into one final complex example recall that our memory addresses are 24 bits long the first eight bits of each address will correspond to the tag at which that address contents will be stored in the cache the next 14 bits of the address refer to the cache line and then finally we have two bits which determine the specific memory word within that line of the cache now remember that for a given address we will actually store the tag portion of the memory address in the cache however the line and word portions of the memory address correspond to specific physical locations in the cache so here are the partial contents of a cache filled with fake data and simply by looking at these values which are all in hexadecimal by the way i can tell you what the memory contents are at certain specific addresses for example i know that the very first block of memory contains this hex sequence because that is what is contained here and the tag indicates that the memory addresses start with 0 0 and the line 0 indicates that this data is all within block 0 of memory so this is block 0 here now if i'm very strict about the addresses then the memory address that consists of 24 0 bits which also corresponds to six zeros in hexadecimal only corresponds specifically to this byte here the hex value one six the memory address zero zero zero zero zero one h maps specifically to this byte containing a zero and then the byte with four or five would be a bunch of zeros and a two and a bunch of zeros followed by a three would map to the one f right there however for ease of notation we'll simply use the address of the first byte within a given block to refer to that whole block in memory the other bit of data in the cache that is also within this particular cache size chunk of memory comes from cache line 0 to a1 its contents are fff000 it's right here the block number will match the line number and be 0 to a1 but what will the memory address be we know that the memory address must start with 0 0 because all addresses in this first cache size chunk start with zero zero that's why the tag right here is zero zero but what about the remaining hex values well there's a bit of a trick in the notation here because i'm using hex to depict the block numbers and the line numbers but recall that the line number only consists of 14 bits which is then followed by two bits that represent the word so i actually need to shift over the binary representation by two positions to make room for the word portion of the address and so if i take the hex value and convert it to binary and then shift over by 2 i'm effectively adding two zeros right here and so now i have to regroup this all in groups of four to figure out what the hex portion of the address for the line number is so this is what the resulting hex value is and that's what goes into the actual memory address down here so what that means is that this particular zero zero portion right here is exactly this memory address but if i wanted to find out what this address was i would have to add 1 to this thus replacing the 4 with a 5 and then this ff would replace that 5 with a 6 and this ff would replace that 6 with a 7. if we want to find out where this last bit of data occurs in memory we have to move forward a bit so this is the first cache size chunk and so all of these start with zero zero in their memory address so we have to skip ahead a bit to find the portion of memory where all the addresses start with a zero five but because we are looking at line three f f f that will correspond to the last line of the cache size chunk which starts with zero five so if this is the very end of that chunk then this data goes right there in that chunk here that's going to be within this sequence so if this is block 0 of this particular chunk then this would be block 3 fff of that particular chunk and the address would start with 0 5 but then we would have to shift this over by 2 to find out what goes here fortunately that's easy to do because 3 in binary is simply 0 0 1 1 if we shift that over by 2 then we have two ones and then f's are nothing but ones over and over again so what we get is an f an f an f and then this last f got shifted to the left we're left with two ones followed by two zeros which is 12 which is c in hex so this particular address corresponds to the 4 4 byte specifically and if we replace the c with a d that would refer to the five five if we replace it with an e that would refer to this one one and if we replace it with an f it would refer refer to this one one byte even further along in memory we eventually come to a cache size chunk whose addresses all start with one three and so this is that chunk there is a line of data here in memory but the second line contains this data because line 0 0 0 1 in the cache has this data the tag is 13. so if we start with 13 then all of this data corresponds to this memory location or rather this set of four memory addresses and the exact address at least of this right most byte would result from shifting this one over by two to get four preceded by zeros and once again we can increment this rightmost hex digit to address the other bytes in this block so if the 4 becomes a 5 we're referring to the 4 4 if it becomes a 6 we're referring to the 5 5 and if it becomes a 7 we're referring to the 6 6. so this mapping scheme is not terribly complicated but it has some clear disadvantages mainly what if within the chunk of addresses that start with the tag05 i want to read the line number one so since line numbers start at zero it would actually be the second line within that chunk so it would start with zero five and have zero zero 0 4 as the address of its right most byte and i'll make up some data here for that and i want to read this data for my program well currently the cache stores data with tag one three in line one so i would have to evict this data from the cache in order to replace it with this data and that would be true even if i'm not really using any of the other data in the cache and that's the problem is that we have a very rigid strict mapping that doesn't allow us to replace the cache lines which are least needed instead whenever i want to read line one of any given cache size chunk in memory i have to replace what's there no matter how often i'm using it this inefficiency is the reason that better more sophisticated schemes have been developed

Channel: Jacob Schrum

Views: 1,414

Rating: 4.8709679 out of 5

Keywords: cache, direct mapping, memory, line, block, frame, RAM, hexadecimal, William Stallings, Stallings, Computer Organization, Architecture, Designing for Performance, Tag, Word, Memory Word, byte, bit

Id: B-EMkzv2AHE

Length: 17min 8sec (1028 seconds)

Published: Tue Aug 11 2020