Cache Organization and Policies

Cache organization concerns how a cache maps memory blocks to storage — its placement and associativity — and the policies that govern replacement and writes, which together determine how often the cache hits and how it interacts with main memory.

Definition

Cache organization and policies are the structural and management choices of a cache — where blocks may be placed, which block is evicted on a miss, and how writes are propagated to lower levels — that govern its hit rate and behavior.

Scope

This topic covers the internal design of a single cache: direct-mapped, set-associative, and fully associative placement; replacement policies such as LRU and its approximations; write policies (write-through versus write-back) and write-allocation; block size; and the classification of misses into compulsory, capacity, and conflict. It excludes multi-cache coherence (cache coherence protocols) and address translation (virtual memory and paging).

Core questions

• How do direct-mapped, set-associative, and fully associative placement differ in cost and conflict behavior?
• What replacement policy should evict a block on a miss, and how is it approximated cheaply?
• How do write-through and write-back policies differ in traffic and complexity?
• How are misses classified, and which design changes reduce each kind?

Key concepts

• direct-mapped cache
• set-associative cache
• fully associative cache
• least-recently-used (LRU) replacement
• write-through vs write-back
• write-allocate
• block (line) size
• compulsory, capacity, and conflict misses

Key theories

Three Cs miss model

Cache misses can be categorized as compulsory (first access), capacity (cache too small for the working set), and conflict (too little associativity), a framework that links each design parameter — size, block size, associativity — to the misses it reduces.

Mechanisms

A memory address is split into tag, index, and offset fields. The index selects a set, the tag identifies the block within it, and associativity sets how many blocks share a set. On a miss the cache fetches the block and evicts another chosen by a replacement policy (often an approximation of least-recently-used). Writes either update main memory immediately (write-through) or mark the block dirty and defer the update (write-back).

Clinical relevance

Cache organization governs effective performance because miss penalties are large relative to hits. Programmers improve cache behavior through data layout, blocking, and access patterns that raise locality, while architects tune associativity, block size, and write policy to balance hit rate against area, power, and bandwidth.

History

Wilkes proposed the slave (cache) memory in 1965, and caches were soon adopted commercially. Alan Jay Smith's 1982 survey synthesized extensive measurements of placement, replacement, and write policies, establishing the design vocabulary still used today. The three-Cs model later gave a structured way to reason about miss causes and remedies.

Key figures

• Maurice Wilkes
• Alan Jay Smith
• John L. Hennessy
• David A. Patterson

Seminal works

• smith1982cache
• hennessy2019

Frequently asked questions

What is the difference between write-through and write-back caches?

A write-through cache updates both the cache and main memory on every write, keeping memory current but generating more traffic. A write-back cache updates only the cache, marking the block dirty, and writes it to memory only when evicted, reducing traffic at the cost of extra bookkeeping.

Why use set-associative instead of direct-mapped caches?

A direct-mapped cache allows each block exactly one location, so blocks that map to the same slot conflict. Set associativity gives each block several possible locations within a set, reducing conflict misses at the cost of more comparison hardware and slightly slower hits.