home | about

set associative cache
Complete

Summary

Bit allocation

  • set index - which set the block would get mapped to
o®setn-1:0blocknumber...:no®setn-1:0setindexn+m-1:ntag...:n+m

Cache structure

00011011validtagdatavalidtagdata

Concept

Set associative cache

  • each block is mapped to a corresponding set in cache
  • the set can store multiple blocks, n-way -> n blocks per set
  • several colliding blocks can be stored alongside
cache_idx = block_num % num_cache_sets
...00000......00001......00010......00011......00100......00101......00110......00111......01000......01001...00011011

Block replacement policy

  • least recently used
    • for temporal locality
    • keep track of which blocks were accessed
    • preserve the more recently accessed blocks
  • first in first out
  • random replacement
  • least frequently used

Application

Memory accesses

  • 8 byte blocks -> 3 bit offset
  • 4GB memory -> 2³² bytes -> 32-bit memory addresses
  • 32B cache -> 2⁵ bytes -> 4 blocks -> 2 sets -> 1 bit set index
  • 2-way associative cache