Cache Mapping

• 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)$