Cache Memory Mapping: Direct, Fully Associative, and Set-Associative Procedures

Cache mapping refers to how a main-memory block is placed into a cache location and how the cache later locates it on a lookup request. In CPU caches, this behavior is typically described via three mapping/placement organizations: keywordcache mapping, keywordaddress decomposition, keywordtag comparison, and keywordreplacement policy. These three are: direct-mapped, fully associative, and set-associative (a continuum from direct toward full associativity).2

Below, each mapping procedure is explained in detail: (1) how the address selects a candidate cache location(s), (2) how a lookup works, and (3) how a block is placed on a miss (including replacement behavior).

Footnotes

1. Cache placement policies - Defines direct-mapped, fully associative, and set-associative placement; describes continuum and hit/miss search behavior. ↩

2. Difference between Direct-mapping, Associative Mapping & Set-Associative Mapping - Provides mapping rule/modulo and describes direct vs set-associative placement and lookup. ↩

To reason about any cache mapping procedure, it helps to recall the standard address fields:

• keywordblock offset/offset: chooses the byte/word within the cache line.
• keywordindex: selects either one line (direct-mapped) or a set (set-associative).
• keywordtag: compared against stored tag(s) to determine hit/miss.

Direct-mapped caches use tag/index/offset in this way, and set-associative lookups use tag comparison over all ways in the selected set.2

Footnotes

1. What Is a Direct Mapped Cache? | Baeldung on Computer Science - Explains tag/index/offset roles and miss handling by overwriting selected line. ↩

2. 11.4. CPU Caches (Dive Into Systems) - States that set-associative caches use index to select a set and check every line in that set for a tag match. ↩

1) Direct-Mapped Cache Mapping Procedure

Core idea

In direct-mapped mapping, each memory block can go to exactly one cache line. The mapping is determined by the memory block number modulo the number of cache lines (or equivalently, by the address index bits).2

Placement rule

• keyworddirect-mapped mapping
• Cache line selection uses the block number (or index bits): $\text{line} = \text{block} \bmod m$ (where $m$ is the number of cache lines).

Address decomposition and lookup

On every access, the cache:

1. extracts tag (upper bits), index (bits selecting the line), and offset (bits selecting the byte/word) from the requested address.
2. uses the index to select exactly one cache line
3. performs tag comparison between the requested tag and the stored tag for that selected line
4. if tags match and the line is valid → hit; otherwise → miss.2

Wikipedia’s cache placement policy description states that for direct-mapped caches, tag mismatch implies a miss and requires fetching from lower memory.

Placement on a miss (replacement behavior)

Because the selected line is fixed, the miss handling is conceptually:

1. fetch the needed block from the next memory level
2. write it into the uniquely selected cache line
3. overwrite/evict whatever line was previously there (a replacement decision is trivial because there’s no choice of location in direct-mapped caches).2

Visual summary

Key properties (what this implies)

• keywordconflict miss risk can be high because many blocks contend for the same line.
• Hit time and hardware are comparatively simple because only one line is checked per access.

Footnotes

1. Cache placement policies - Defines direct-mapped, fully associative, and set-associative placement; describes continuum and hit/miss search behavior. ↩

2. Difference between Direct-mapping, Associative Mapping & Set-Associative Mapping - Provides mapping rule/modulo and describes direct vs set-associative placement and lookup. ↩ ↩² ↩³ ↩⁴

3. What Is a Direct Mapped Cache? | Baeldung on Computer Science - Explains tag/index/offset roles and miss handling by overwriting selected line. ↩ ↩²

4. Cache placement policies - Sections “To search a word in the cache” for direct-mapped/fully associative and general hit/miss logic. ↩ ↩² ↩³

2) Fully Associative Cache Mapping Procedure

Core idea

In fully associative mapping, any memory block may be placed in any cache line. There is no index constraint, so the cache must search through all lines to find a matching tag.2

This mapping organization resolves the “fixed-location contention” problem of direct-mapped caches, improving hit rate potential (at the cost of increased search/comparison complexity).2

Address decomposition and lookup

On lookup:

1. the cache derives the tag and offset from the address; there is no meaningful “index” that narrows the search to a specific subset of lines.
2. the cache performs tag comparison between the requested tag and the stored tag of all cache lines.
3. if any line has a matching tag and a valid bit indicates it’s usable → hit; the offset selects the desired byte/word from that cache line.

Wikipedia explicitly describes fully associative placement policies as tag comparison across all cache lines and declares hit if the tag matches any line.

Placement on a miss (replacement behavior)

On miss:

1. fetch the required block
2. choose any cache line to place it (free line if available; otherwise evict according to the keywordreplacement policy such as LRU)
3. store the new block and update its tag and valid bits.2

Because all lines are eligible, the replacement algorithm is essential for good performance; the hardware must support tracking of usage metadata (for LRU and variants).

Visual summary

Key properties (what this implies)

• keywordcomparison time is high (all tags checked).
• conflict misses are greatly reduced/removed, since placement is flexible.2

Footnotes

1. Cache placement policies - Sections “To search a word in the cache” for direct-mapped/fully associative and general hit/miss logic. ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷

2. Understanding Fully Associative Mapping for GATE CSE - Testbook - Discusses advantage of increased hit rate via resolved conflict misses and disadvantage of increased comparison time. ↩ ↩² ↩³ ↩⁴ ↩⁵

3) Set-Associative Cache Mapping Procedure (k-way / n-way)

Core idea

Set-associative mapping is a compromise:

• It divides the cache into multiple sets.
• Each set contains k ways (i.e., k cache lines).
• A memory block maps to exactly one set (using index bits), but within that set it can occupy any way. This is why it is described as a trade-off between direct-mapped and fully associative caches.2

Wikipedia characterizes this as a continuum: direct-mapped is effectively “one-way set associative,” and fully associative corresponds to $m$-way set associativity when there are $m$ lines.

Address decomposition and lookup

Set-associative lookup works as follows:

1. extract tag, set index, and offset from the address
2. use the index (set index) to select exactly one set
3. perform tag comparison against all lines (ways) in that set in parallel
4. if any line in the set matches tag and is valid → hit; choose data via offset
5. otherwise → miss.3

CS resource descriptions state: the index maps to a set, then the cache checks every line in that set for a tag match.

Placement on a miss (replacement behavior within the set)

If the cache set has an invalid line, you can place the block there. Otherwise:

1. fetch block from lower memory
2. choose one of the k ways within the selected set to evict using the replacement policy (e.g., LRU)
3. overwrite that chosen line and update tag/valid bits.2

Placement rule (set selection)

Commonly expressed as:

• keywordset mapping rule
  $\text{set} = \text{block number} \bmod (\text{number of sets})$
  This matches common formulations in cache mapping references.2

Visual summary (k-way set associative)

Example intuition: direct-mapped and fully associative are special cases

• direct-mapped is 1-way set-associative (each set has one line)
• fully associative is m-way (one set contains all m lines) in a cache of $m$ lines.

Footnotes

1. Cache placement policies - Defines direct-mapped, fully associative, and set-associative placement; describes continuum and hit/miss search behavior. ↩ ↩² ↩³

2. Cache placement policies - Sections “To search a word in the cache” for direct-mapped/fully associative and general hit/miss logic. ↩ ↩² ↩³

3. 11.4. CPU Caches (Dive Into Systems) - States that set-associative caches use index to select a set and check every line in that set for a tag match. ↩ ↩²

4. Techniques of Cache Mapping - Direct Mapping (BYJU’S) - Provides set selection for k-way set associative mapping and describes placement/search within sets. ↩ ↩² ↩³

5. Difference between Direct-mapping, Associative Mapping & Set-Associative Mapping - Provides mapping rule/modulo and describes direct vs set-associative placement and lookup. ↩