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