Cache Memory Organization: Mapping, Replacement, and Write Policies

Cache memory is a small, fast memory that stores copies of data/instructions from a larger, slower main memory to reduce average access time. Cache organization is primarily determined by (1) how main-memory addresses map to cache locations—i.e., mapping techniques such as direct-mapped, fully associative, and set-associative; (2) how cache lines are chosen for eviction—i.e., replacement algorithm; and (3) how writes update cache and/or memory—i.e., write policy such as write-through vs write-back and write-allocate vs no-write-allocate.

Addressing is typically decomposed into block offset, set index (or line index), and tag fields so the cache can quickly decide whether a requested memory block is present and which line holds it. This structure underpins cache hit/miss decisions and determines the cost of lookup (e.g., parallel tag comparisons in associative caches).

Note: I’m unable to complete the required web research and citations because the web-search tool returned a quota error. Since this is mandatory for Coursify output, I cannot provide a compliant, citation-backed course section right now.

Core address decomposition and lookup flow

A byte address is usually broken into fields based on cache geometry: total capacity, block size, associativity, and number of sets. Let:

• Cache block size = $B$ bytes
• Number of sets = $S$
• Associativity = $A$ ways per set
• Cache line (block) identification:
  • offset selects a byte within a block: $\log_2(B)$ bits
  • index selects a set (or a line for direct-mapped): $\log_2(S)$ bits
  • tag identifies the remaining higher-order bits

On a lookup:

1. Extract tag, set index, offset.
2. Use the set index to access the appropriate set (direct-mapped/set-associative) or compare against all ways (fully associative).
3. Compare tags in parallel against valid lines.
4. On hit, select the way’s data and use the offset for the exact byte/word.
5. On miss, choose a victim line per the replacement policy, evict (optionally writing back if dirty), then fill the new block.

Key terms: block offset tag valid bit set index.

Cache mapping techniques

Cache “mapping” describes the relationship between a memory block and the cache line(s) it may occupy.

Direct-mapped cache

• Each memory block maps to exactly one cache line (one location).
• On miss, the victim is predetermined by the index; no per-set choice exists.

Pros: simplest hardware, single tag compare.
Cons: high conflict misses because multiple addresses compete for the same line.

Fully associative cache

• A memory block can be placed in any cache line.
• On lookup, tags must be compared across all lines (or ways), typically in parallel.

Pros: minimal conflict misses.
Cons: expensive lookup (many tag comparisons), larger hardware cost.

Set-associative cache

• Cache is divided into sets; each memory block maps to exactly one set, but can occupy any way within that set.
• Commonly used as a practical compromise.

Pros: reduced conflict misses relative to direct-mapped; lookup constrained to a single set.
Cons: still has conflict misses, and needs tag comparison across A ways.

Key terms: associativity conflict miss way.

Mapping with tag/index/offset (conceptual)

Below is a conceptual view of where the address fields go.

• Direct-mapped:
  • index selects the single line; tag is compared for match.
• Fully associative:
  • no index: tag compared against all lines/ways.
• Set-associative:
  • index selects set; tag compared across ways in that set.

You can think of the cache “decision” as:

• Choose candidate lines (by mapping rule)
• Among those, choose the one with matching tag and valid=1

Key terms: hit miss.

Replacement algorithms

On a miss, a cache needs a policy to decide which line to evict. Replacement quality affects miss rate (and thus performance).

Common policies:

1. LRU
   • Evict the line with the oldest last-access timestamp.
   • Optimal among practical stack policies, but exact LRU is expensive for high associativity.
2. FIFO
   • Evict the oldest inserted line.
   • Cheap metadata, but can evict frequently used lines under some workloads.
3. Random
   • Very simple, can perform surprisingly well depending on workload.
4. Pseudo-LRU
   • Uses fewer bits than exact LRU (e.g., tree-based approximations) to reduce complexity.

Trade-offs:

• More accurate policies reduce miss rate but require more state and/or more complex logic.
• Hardware cost grows with associativity and policy complexity.

Key terms: victim selection dirty bit.

Write policies: write-through vs write-back, and write-allocate vs no-write-allocate

Stores complicate cache consistency with memory because updates must be propagated according to a defined rule.

1) Write-through vs write-back

• Write-through: every store updates cache and memory immediately.
  • Typically no need for dirty eviction handling (dirty bit often unnecessary).
• Write-back: store updates cache only; memory is updated when the dirty line is evicted.
  • Requires a dirty bit and potentially a write-back on eviction.

Impact:

• Write-through: higher write traffic to memory, but simpler eviction behavior.
• Write-back: reduces memory writes for repeated writes to the same block, but needs dirty tracking and write-back latency on eviction.

2) Write-allocate vs no-write-allocate

On a store miss (the block is not currently in cache):

• Write-allocate: bring the block into cache first, then perform the write.
• No-write-allocate: write directly to memory without loading the block into cache.

Impact:

• Write-allocate can help if the same block will be written again soon (temporal locality of stores).
• No-write-allocate avoids polluting cache with one-time store targets.

Key terms: store miss pollution.