Cache direct mapping example - Computer Architecture

Cache direct mapping example – Computer Architecture



hello guys this is Sina and tonight I'm going to do this computer system architecture problem now I'm going to try my best to keep it short and straight to the point so you can learn it easily do you need to have any background to understand this no I didn't have any background and I hadn't really studied cache that much before this but I could still understand it so let's start a byte addressable and as you can see the important part of the question are bold already so we can see which things actually matter a byte addressable computer has a small data cache capable of holding eight 32-bit words I'm later I'm going to show you a table I'm going to use this information to our table so you can visually feel it and you can see it so it should cache line consists of two 32-bit words so let's just draw this so far we know what a byte is one byte is eight bits and in 32 bits there are four bytes right so one byte is eight bits how many bytes in 32 bits four and each cache line printers have two 32-bit words so can you imagine it yep easy here's a is going to look like we have 1 2 we have 1 2 3 4 5 6 7 & 8 32-bit words so each of these with 32 bits and since we said there are 4 bytes in each 32-bit word I just divided it into this shape and the question says that it cache line or each cache block has two 32-bit words now what is a cache block and what is the cache line they are exactly the same cache block is defined as the basic unit for cache storage cache line same as cache block note that this is not the same thing as there row of a cache so this row when we talk about cache line we don't mean one row a cache line or a cache block depends on this computer in this example each cache line or each cache block is two 32-bit words so this is like zero cache line 0 this is line 1 or block one and these two are 2 & 3 now after this point let's go read the rest of question so when a given program is executed the processor reads data sequentially from the following hexadecimal addresses what we know about hexadecimal is that each hexadecimal digit can be represented in four bits here's an example 500 hexadecimal if you want to write it – or comparator to binary this has going to look for four four so in this example because all of our addresses have three hexadecimal digits it when we convert them to binary we're going to have over all 12 bits so this is another important information that we need and after this point I've let's to read the rest of the question and then move on to the solution so this pattern is repeated two times the cache is initially empty show the contents of blah blah blah blah if a direct mapping blah blah blah hit break if you still don't know what the question one from you doesn't matter I had no idea either but I keep proceeding to see what I can understand further so this question is not really meant to make sense because it's different it's something we're experienced for the first time probably anyway so let's really beginning and start converting all of these hexadecimal addresses to binary I've done it here and you can see all of these in binary now the next step and the next thing we want to do is to find out the value of tag line and work alright I'm going to use a very simple and cool analogy here to teach you what we're actually looking for so the next thing we need to read we need to do is to find out the values tagline and work now why do we need these things how do we actually use them you're going to see it very soon imagine okay we have four blocks imagine each of these bytes or one house our task right now is to find a number of bids to generate eight unique addresses for each of these houses so this is our question how many bits that we need to generate eight unique addresses the answer is simple three why because 8 is 2 to power of 333 bits to create or to generate 8 unique addresses this is one address 2 3 4 5 6 7 & 8 so let's say in each block we can say this is the 0 5 this is the first 5 second third fourth fifth sixth and seven and same for all other bikes now this is four bytes so we can say the word is three have outlines we have four cache line or four cache blocks since cache line and block are exactly the same we have four blocks here we need a number of bits to generate four unique addresses for each of these blocks easy right to 2 power of 2 is 4 so we need 2 bits to do that 1 2 3 4 unique addresses to and you gonna see we're going to use this addressed later to locate data in these memories later if you want to see if data is here this is going to be block 1 house number 0 1 2 so that's basically the idea and I'm going to show you later so 3 2 and since we said we have 12 bits overly so the tag is going to be 7 3 plus 3 is 5 minus 12 7 here is the binary equivalent of all of these exact same addresses and as you can see I've actually divided them into airline water packet so since we have 3 words you can see three bits here and lion attack as well so how are we actually going to do this what computer does here and the question told us that the data cache is initially empty so nothing is inside here and this yellow doesn't actually mean anything and just want to make it more visible for you so let's become computer and see how it searches for data so if we come here and see if they tie if this there's data in this address so 500 in binary is line 0 which is here or this yellow part and word and words 0 this we can assume this is 0 or you can say this is right this is just a logical presentation to editing the 30 methods so I'm going to say this is 0 is 1 then 2 3 4 5 6 7 so 9 0 4 0 here the data isn't there so we can write it here we go to next one five one four nine two four four line 2 4 4 0 1 2 3 4 write it here this was a Miss so is this how do we define hit miss when computer looks for data and cache if it can find it it's a hit if it can't find it it's a Miss right now we're searching but there's nothing there sweets submits so three to eight goes to line one word 0 line 1 or 0 3 to 8 miss 3 3c line for value in form so our line 3 work 4 so 3 3 3 C third line or third block to the fourth bike in this block 0 1 2 3 4 5 6 7 and the next one is 4 4 4 0 block number 0 and word for so it's going to sit here it's in the yellow blocking and one thing important we need to know is that every time we import or every time the computer enters a new value enters this block it moves in and out as a block that this is very confusing thing I'm saying what I'm trying to say is that four four four moves in as a block and kicks the former block out so it's not like we can have one bite and we keep the previous five years ago the whole blocks move in and the whole block will move out so now we have four four four here 500 is out does it mean this is a hit no that's a different definition are we going to see it soon this is another miss 4 4 4 2 F 0 is second line and 0 0 I'm going to do this a bit faster because now I can you know it this is going to be 2 again because it's in this block the previous block will be swapped at 200 0 0 0 here again this block will be out 3 to 4 0 0 4 3 2 4 block out previous blackout 5 1 8 a third block 0 here mmm oh is it 5 1 8 again new block in old walk out 3 3 3 3 3 C is here this block but this were the fourth one this is 3 so I know that this is black 3 and this is 4 in decimal so I know is here and again I keep this old previous block out four four four again we go up here now here we have three to four at this position and four four four let me highlight this 3 to 4 you may think this is a hit but no it's not a hit even though four for four and three to four have the exact same word and line and they actually seem to sit in the same place this is not a hit this is another miss why because they have different tags and that matters to us a hit happens when two data have the exact same tag line and fell and work here if you look the others a three two four four five same line of work but obviously different tags so we keep moving up the last value is 4 F 4 which would sit in the second block because this is representation of 2 in decimal and fourth word of it so for F form here and this dude will be kicked out so we did one round of searching for data the question told us the cache was initially empty so everything we did here was I miss there was no hit now as the question says this process should be repeated twice so we did it once we need to do it one more time we go back to the beginning and we repeat 0 0 0 0 where does it go here brother out rather in 5 1 4 second a line or second block here block number 2 and fourth value again it may seem like it's a hit but it's not why because they have same line in word but not the same tag so 3 2 8 block 1 value 0 oh this is a hit this is a hit because 3 to 8 is already here and a game room searching for it is it there yes it is there so this is hit and we usually I'm going to show you this X so 3 3 see wow it's again here so this is another hit to hit so far four four four zero four look up here this goes out miss to f-zero block number two zero or it's another mess 200 it's zero zero miss three to four here it's another miss five one eight is here and here miss I'm going to delete this but we're going to remember the fact that it was hit three three series right up here again another miss 4 4 4 goes up here another miss 4 F 4 comms we're here plus two valid for for F another miss so we had 12 addresses we repeated two times so we had an overall of 12 times 2 equal to 24 attempts out of which we have two hits which means we have two out of 24 hit ratio this is what we're looking for in this question that's it nothing else I know at first we may seem really confusing in rear then we may not make any sense but it's not actually that hard and yeah if there's any question you can ask me I'm going to try to answer it if I don't know I'm going to try to ask someone else so yeah thank you


44 thoughts on “Cache direct mapping example – Computer Architecture

  1. One hour sitting in lecture, didnt understand a thing… Gets back home, opened YouTube and typed "cache hit and miss", found this video, after just 14min, i finally understand what is going on, LIKED AND SUBSCRIBED

    So, it's like a full round of attempted searches (with a data value list, both in decimal and binary form provided of course), it may find a hit only if at least two round of searches was committed since cache memory is empty in the first place, I see…

    Edit: Also, a hit is basically when a new value meets an old value and both are the exact same value like uh, new 444 meets an old 444, they matched, so it's a hit…

  2. best video for direct mapped cache can you please make a video on associative and set associative mapped cache

  3. At 8:58 The address 444 should already be loaded, because normally you load the whole block from the memory in the cache and not only one address in one block. That's the whole thing about it. That it should't have to get all data from the memory everytime

  4. Awesome explanation. Lecturer couldn't explain it, WIllaim Stallings couldn't explain it, other youtube channels that I visited couldn't explain it but you nailed it. Thank you!

  5. hi. thnx for video. it was great. however i didnt get one thing why u asume 11 in line as 4, 10 in line as 2?
    thnx beforehand

  6. Thank you my friend you really did explain it very well!
    You mentioned there, when we hit the same block and line but we have different tags, is not a hit, is it the situation when we call it "Miss-Tag" ?

  7. in the question you have 11 addresses, but you make a table of 12 and say in the end that we had 12 addresses. what I got wrong from the question? didnt it have 11 addresses?

  8. This is my only educational video so far 😂 I guess it wasn’t too horrible! Should I do more? If yes, what? Frontend/backend Web dev, AI, maths etc? or should i just retire here while i'm at my peak 😂 😂

  9. Thanks for the wonderful video. I need some clarification regarding the first line of the question. The question says "data cache capable of holding eight 32 bit words", when you are navigating through the memory address it always looks like only four 32 bit words is stored at any point of time. Please clarify if I misunderstood any idea.

  10. Is this a direct mapped cache or a 2-way associative cache? Looks like you had a choice on where to put the address.

  11. thank you so much! this was really helpful. also, the waves(?) in the background made this a really soothing lesson.

  12. Thanks, I'm studying for a final in my comp architecture class and this helped a lot. Really surprised how simple this is.

  13. there is some incorrect information in this video, you should start with understanding cache lines vs blocks

Leave a Reply

Your email address will not be published. Required fields are marked *