cho.sh
Cache Mapping

Cache Mapping

Warning

This post is more than a year old. Information may be outdated.

  • While with logical operators, it is possible to check if a value exists or not, if a block can be anywhere, we need to search everywhere.
  • Where is the block we are looking for?
  • Fully Associative Mapping
    • Any block from memory can be put in any cache block (i.e., no restriction)
    • $S=1$, $K=N$
    • Byte offset bits $b = \log_2B$ bits where $B$ is the block size
    • No set index because there is one set.
    • Most flexible (fewer evictions)
    • Longest search time $O(N)$
  • Direct Mapping
    • Each block from memory can only be put in one location
    • $S=N$, $K=1$
    • Each set has one block.
    • Least flexible (more evictions)
    • Shortest search time $O(1)$
  • K-Way Set-Associative Mapping
    • Given S sets, block $i$ of main memory maps to set $i\mod S$
    • Within the set, the block can be put anywhere.
    • Byte offset bits $b = \log_2B$ bits where $B$ is the block size
    • Set bits $s = \log_2S$ bits where $S$ is the number of cache sets
    • Tag bits $t$ = remaining bits
    • Compromised
      • 1-way set associative = Direct
      • N-way set associative = Fully Associative
    • Search Time is $O(K)$
    • For small $K$ Parallel Search with Hardware Optimization: $O(1)$