Direct-Mapped Cache - Difference Hit & Miss

Discussion in 'Homework Help' started by tquiva, Dec 12, 2012.

  1. tquiva

    Thread Starter Member

    Oct 19, 2010
    Hello, could someone please help me better understand what a hit and miss are. From what I know:

    Cache: Holds copies of the contents of memory
    Hit: Find element in cache
    Miss: Element not in cache

    I'm currently trying to figure out these problems. The solutions were provided, but I tried the problem out myself and still do not understand how solutions were obtained.

    A) Direct-mapped cache
    8 One-word blocks (initially empty)
    Label each reference as hit or miss
    Word Addresses: 2,3,11,16,21,13,64,48,19,11,3,22,4,27,6,11

    My approach to the solution is in attachment A below.

    However, I view the solutions and it says:

    ***3(2) means that 3 was accessed for the 2nd time

    My question is, how are the "contents in block #s" obtained? And why are they all misses?

    I am given another similar problem below:

    B) Direct-mapped cache
    Two-word blocks, Total = 8 words
    Block # = quotient of word address/2
    Word Addresses: 1,1,5,8,10,6,32,24,9,5,1,11,2,13,3,5

    My solution is in the attachment (B) below again, and the solution is:


    For this one, how do I know which is a hit and which is a miss? It is indicated that 1(2) is a hit ... but I'm not sure how to differentiate this from everything else?

    If anyone could enlighten me, I greatly appreciate it. Thank you!
    Last edited: Dec 12, 2012
    Prabhashani likes this.
  2. WBahn


    Mar 31, 2012

    When you say, "how are the "contents in block #s" obtained?" that seems to refer to something with that specific label. I can't find that in your attachments. It appears you have it correct on the sheet where you tried to work the problem.

    So, taking a guess at what you are asking, if I have, say, 16 blocks of cache memory, then they are addressable with 4 bits, right? If each block holds 1 byte of data and, assuming that memory is addressed at the byte level, then any memory address that ends in, say 0101, is going to be mapped to cache block 0101.

    As you said at the top of your post, a Hit is when you access the cache and the block you are looking for happens to the block that is presently stored there. If it isn't, then it is a Miss and you have to load that data value from main memory (or the next higher level of cache) before you can use it.

    In a direct mapped cache where every cache location can only hold a single block of memory at one time, the only way you can have a Hit is if the last attempt to access a value at the same cache location was, in fact, an access to the same memory address. Do you see why?

    In your attempt at the first one, I can't tell which you think are hits and which you think are misses? You have three accesses that have slashes through them -- what do the slashes mean?

    In this case, each cache location holds two words, meaning that each cache has one bit of offset relative to the start of the block. Since you only have eight total words of cache memory, that means you have 4 blocks of cache available, meaning you have a 2-bit cache index. The map to main memory as follows:

    memory address = [reference][2-bit cache index][1-bit offset]

    So a reference to memory address
    42 => 0x00101010 => [00101][01][0]

    loads memory locations 42 and 43 into memory into cache block #1.

    If the next attempt to access a memory location that has this same index, namely 01, then if that address is 42 or 43 it will be a hit. If it is anything else, it will be a miss and the new values will have to be loaded. If the next access through that same index is then 42 or 42, it will be a miss because those values were previous overwritten.