Q3Computer Architecture

Cache mapping schemes define the rule by which a block of main memory is placed into, and subsequently located within, the cache.

Direct Mapping: each main memory block can be placed in only one specific, predetermined cache line, calculated typically as (block address) MOD (number of cache lines). The memory address is divided into a tag field, a line/index field (identifying the specific cache line), and a word/offset field (identifying the word within the block). On access, the hardware simply indexes directly to the corresponding cache line and compares the stored tag with the incoming address's tag to check for a hit. This scheme is simple and fast to implement (no search required) but suffers from a high conflict-miss rate when multiple frequently used blocks map to the same line and repeatedly evict one another, even if other cache lines are free.

Fully Associative Mapping: a memory block can be placed in any available cache line whatsoever, with no fixed mapping rule. The memory address is divided only into a tag field and a word/offset field (no line/index field is needed). On access, the hardware must simultaneously compare the incoming tag against the tags of all cache lines in parallel (using comparator hardware for each line) to determine a hit. This scheme offers maximum flexibility and the lowest possible conflict-miss rate for a given cache size, but requires expensive, complex parallel-comparison hardware that becomes impractical for large caches.

Set-Associative Mapping: a compromise between the two extremes, in which the cache is divided into a number of sets, each containing a small number of lines (e.g., a 4-way set-associative cache has sets of 4 lines each), and a given memory block maps to exactly one specific set (via a modulo calculation on the set index field) but can occupy any of the lines within that set. The memory address is divided into a tag field, a set-index field, and a word/offset field. On access, the hardware indexes to the correct set and then compares the tag against only the (small number of) lines within that set in parallel, balancing the simplicity/speed of direct mapping with much of the reduced-conflict benefit of full associativity, making it the mapping scheme most commonly used in real-world processor cache designs (typical values are 2-way, 4-way, or 8-way set-associative).

Comparative trade-off: as associativity increases from direct-mapped (equivalent to 1-way set-associative) toward fully associative (where the entire cache is a single set), the conflict-miss rate decreases since a block has more candidate locations to occupy without evicting another actively-used block, but the hardware cost, access latency, and power consumption of the parallel tag-comparison logic increase correspondingly. Empirical studies of real workloads generally show diminishing returns beyond 4-way or 8-way associativity, which is why most modern processor caches settle on these values as the practical sweet spot between direct-mapped simplicity/speed and fully-associative flexibility, reserving fully associative designs mainly for very small structures like the Translation Lookaside Buffer (TLB), where the total number of entries is small enough that full parallel comparison remains hardware-feasible.