Caches

Caches

Direct Mapped with One Word Blocks

  • Each data item has a unique place in the cache.
  • LSBs of address index into cache.
  • MSBs of address are tage field to indicate whether we have a hit.
  • Direct Mapped with Multi-Word Blocks

  • Each data item has a limited number of places in the cache.
  • LSBs of address index into cache.
  • MSBs of address are tage field to indicate whether we have a hit.
  • Middle bits of address indicate which word in block we want.
  • Set Associative

  • Each data item has a limited number of places in the cache.
  • LSBs of address index into cache.
  • MSBs of address are tag field to indicate whether we have a hit.
  • Must compare tag against multiple entries in index.
  • Fully Associative

  • Any data item can be anywhere in the cache.
  • MSBs of address are tag field to indicate whether we have a hit.
  • Must compare tag against all entries in cache.







  • A := 7
    B := [1,2,3,4,5]
    C := [6,7,8,9,10]
    
    for i := 2 to 5
      C[i] := B[i]
      B[i] := A + B[i-1]
    end
    

    Data Item Address
    A 0...0 0000 00
    B[1] 0...0 0001 00
    B[2] 0...0 0010 00
    B[3] 0...0 0011 00
    B[4] 0...0 0100 00
    B[5] 0...0 0101 00
    C[1] 0...0 0110 00
    C[2] 0...0 0111 00
    C[3] 0...0 1000 00
    C[4] 0...0 1001 00
    C[5] 0...0 1010 00
    i 0...0 1011 00