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