Cache Memory: Organization, Write and Replacement Policies: short notes (Computer Organization & Architecture)

Revision mode

Introduction

A cache is a small, fast memory between the processor and main memory that holds copies of recently used blocks (also called lines) of main memory. The processor sends every address to the cache first. If the block is there (a hit), the word is returned at cache speed; if not (a miss), the block is brought in from memory, possibly evicting another block.

Three design questions define a cache. Where may a block go? That is mapping (direct, fully associative, set-associative), treated in Cache Mapping. Which block is evicted on a miss? That is the replacement policy. What happens on a write? That is the write policy. This note covers the organisation of a cache line, the lookup, both policies, the classification of misses, and the timing and memory-traffic consequences that GATE asks about. The averages used here are defined in Memory Hierarchy and Performance.

Prerequisites

Memory Hierarchy and Performance: hit ratio, miss penalty, hierarchical and simultaneous average access time.

Core concepts

What a cache line holds

Field	Purpose
Data block	$B$ bytes copied from one aligned block of main memory
Tag	High-order address bits that say which memory block the line holds
Valid bit	1 if the line holds real data (0 after power-on or invalidation)
Dirty (modified) bit	Write-back caches only: 1 if the block was written since it was loaded
Replacement state	Bits per set for LRU or FIFO order (set-associative and fully associative caches)

The processor's address is split into tag, index (selects a line or set; absent in a fully associative cache) and block offset (selects the byte within the block). The split is computed in Cache Mapping.

Read handling

Read hit: return the word.
Read miss: fetch the whole block from memory into the chosen line, set its tag and valid bit, then return the word. Load-through (early restart) forwards the requested word to the processor as soon as it arrives instead of waiting for the full block.

Write policies

Policy	On a write hit	Main memory
Write-through	Update the cache line and main memory	Always up to date
Write-back (copy-back)	Update only the cache line; set its dirty bit	Updated when a dirty line is evicted

Write-miss policy	On a write miss
Write-allocate (fetch on write)	Bring the block into the cache, then treat it as a write hit
No-write-allocate (write-around)	Write the word to main memory only; the cache is unchanged

Write-back with write-allocate and write-through with no-write-allocate are common pairings. Write-back benefits from allocation because later writes can hit without immediate memory writes. With write-through, no-write-allocate avoids cache-fill traffic on a write miss; write-allocate may still improve later reads and locality, although every write still propagates to memory.

Write buffer. A write-through cache usually places writes in a small buffer that drains to memory in the background, so the processor does not wait for memory on every write. It stalls only when the buffer is full.

Write-through versus write-back. Write-through keeps memory consistent and makes eviction free, but every store costs memory bandwidth. Write-back sends a block to memory only once per eviction, however many times it was written, but a miss that evicts a dirty block costs two block transfers (write the old one, read the new one).

Replacement policies

A direct-mapped cache has no choice: the index names the only possible line. With associativity, one line of the set must be chosen.

Policy	Evicts	Notes
LRU (least recently used)	The line unused for the longest time	Exploits temporal locality; a stack algorithm (no Belady anomaly)
FIFO	The line loaded earliest	Ignores hits; can show Belady's anomaly
Random	Any line	Simple hardware; close to LRU for large associativity
LFU	The line used least often	Needs counters
Optimal (Belady's MIN)	The line whose next use is farthest in the future	Not implementable; used as a lower bound on misses

LRU state. A $k$ -way set has $k!$ possible recency orders, so exact LRU needs at least $\lceil \lg (k!) \rceil$ bits per set. The usual counter implementation keeps a $\lg k$ -bit age per line, $k \lg k$ bits per set.

The three Cs of misses

Miss type	Cause	Reduced by
Compulsory (cold)	First reference to a block	Larger blocks (prefetching)
Capacity	The cache cannot hold all blocks the program is using; the miss would occur even in a fully associative cache of the same size	Larger cache
Conflict (collision)	Too many blocks map to one set; the miss would not occur in a fully associative cache of the same size	Higher associativity

Classification rule. A miss is compulsory if the block was never referenced before. Otherwise, it is a capacity miss if a fully associative LRU cache of the same total size would also miss, and a conflict miss if that cache would hit. A fully associative cache has no conflict misses.

Block size trade-off. Larger blocks exploit spatial locality and cut compulsory misses, but for a fixed cache size they mean fewer lines, which can raise conflict and capacity misses, and each miss transfers more data (a larger miss penalty).

How it works

Cache lookup flowchart with hit and miss paths — Figure 1. Write-back, write-allocate cache lookup: compare valid tags in the indexed set; a read hit returns data, while a write hit updates data and sets dirty. A miss writes back a dirty victim, fetches the new block and updates the tag; only a write request sets its dirty bit.

Algorithms and pseudocode

Text

CACHE-ACCESS(addr, isWrite, data)          // write-back, write-allocate
  (tag, index, offset) <- SPLIT(addr)
  S <- set[index]
  for each line L in S
    if L.valid and L.tag = tag then        // hit
      if isWrite then L.block[offset] <- data; L.dirty <- 1
      update replacement state of S (LRU)
      return L.block[offset]
  V <- VICTIM(S)                           // invalid line first, else by policy
  if V.valid and V.dirty then WRITE-BLOCK(memory, V)
  V.block <- READ-BLOCK(memory, addr); V.tag <- tag; V.valid <- 1; V.dirty <- 0
  if isWrite then V.block[offset] <- data; V.dirty <- 1
  update replacement state of S
  return V.block[offset]

For write-through with no-write-allocate: on a write hit, update the line and memory; on a write miss, update memory only. Cost model: one tag comparison per line of the set (done in parallel by hardware), one block transfer per fill, one block transfer per dirty eviction.

Mathematical explanation

Let $t_c$ be the cache time, $t_m$ the memory time for one access (or one block transfer when the question says so), $h$ the hit ratio, $f_r$ and $f_w$ the read and write fractions.

Write-through, no-write-allocate, no write buffer (hierarchical reads, each write waits for memory):

T = f_r\,[\,t_c + (1 - h)\,t_m\,] + f_w\,t_m .

With a write buffer that never fills, the write term becomes $f_w\,t_c$ .

Write-back, write-allocate (all accesses look up the cache; a miss fetches a block and first writes back the victim if dirty, with probability $d$ ):

T = t_c + (1 - h)(1 + d)\,t_{\text{block}} .

Memory traffic. Write-through sends one word per store. Write-back sends one block per eviction of a dirty line. Which is smaller depends on how many times a block is written before eviction.

Worked examples

Example 1: replacement policies on one reference string

A fully associative cache, block references 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.

Policy	3 lines: misses	4 lines: misses
FIFO	9	10
LRU	10	8
Optimal	7	6

FIFO misses more with 4 lines than with 3: this is Belady's anomaly. LRU and optimal never do this, because the contents of a smaller LRU cache are always a subset of the contents of a larger one (the stack property). With 3 lines, the FIFO hits are the references to 1 and 2 right after 5 enters, and the final 5.

Example 2: write policies and memory traffic

A direct-mapped cache with 2 lines and 4-word blocks (word addresses; block $= \lfloor a/4 \rfloor$ , line $=$ block mod 2). Trace: R 0, W 1, W 4, R 8, W 9, R 0, W 5.

Policy	Hit/miss sequence	Block reads	Block write-backs (after a final flush)	Word writes
Write-back, write-allocate	M H M M H M H	4	2 (3)	0
Write-through, no-write-allocate	M H M M H M M	3	0	4
Write-through, write-allocate	M H M M H M H	4	0	4

Under write-back, R 8 evicts block 0, dirty from W 1, and R 0 evicts block 2, dirty from W 9: two write-backs. Block 1, dirty from W 4 and W 5, is still in the cache at the end, so a final flush adds a third. Under no-write-allocate, W 4 and W 5 both miss: the block is never brought in. In words of memory traffic: write-back moves $4 \times 4 + 3 \times 4 = 28$ words including the flush, write-through with no-write-allocate moves $3 \times 4 + 4 = 16$ . Write-back wins only when blocks are written many times before eviction.

Example 3: average time with write-through

80% reads and 20% writes, read hit ratio 0.9, $t_c = 10$ ns, $t_m = 100$ ns, write-through with no-write-allocate, hierarchical reads.

Without a write buffer: $T = 0.8 \times (10 + 0.1 \times 100) + 0.2 \times 100 = 16 + 20 = 36$ ns.
With a write buffer that never fills (writes cost $t_c$ ): $T = 16 + 0.2 \times 10 = 18$ ns.

Example 4: write-back miss penalty with dirty victims

Hit ratio 0.95, $t_c = 2$ ns, block transfer 50 ns, 30% of evicted blocks are dirty.

T = 2 + 0.05 \times (1 + 0.3) \times 50 = 2 + 3.25 = 5.25 \text{ ns}.

If the cache were write-through (no dirty victims, writes buffered) the miss term would be $0.05 \times 50 = 2.5$ ns.

Example 5: classifying misses

A direct-mapped cache with 4 lines (block $b$ goes to line $b \bmod 4$ ), block trace 0, 4, 0, 4, 8, 1, 2, 3, 5, 0. Every reference misses.

Compulsory: the first references to 0, 4, 8, 1, 2, 3, 5: 7.
Conflict: the second 0 and the second 4. A fully associative 4-line LRU cache would hold both: 2.
Capacity: the last 0. Between the previous 0 and this one, six other distinct blocks (4, 8, 1, 2, 3 and 5) were used, so even a fully associative 4-line cache would have evicted it: 1.

A fully associative 4-line LRU cache on the same trace hits on the second 0 and the second 4, and misses the other 8 references (7 compulsory, 1 capacity).

Example 6: LRU bits

A 4-way set has $4! = 24$ recency orders, so exact LRU needs at least $\lceil \lg 24 \rceil = 5$ bits per set. Two-bit age counters per line use $4 \times 2 = 8$ bits per set. An 8-way set needs at least $\lceil \lg 40320 \rceil = 16$ bits.

Important properties and observations

Valid bits matter. After power-on, no tag match counts until the valid bit is set; the first accesses are compulsory misses.
Direct-mapped caches need no replacement policy.
Write-back needs a dirty bit; write-through does not.
Write-allocate is what makes write-back pay off. With no-write-allocate, repeated writes to an absent block all go to memory.
Stack property. LRU, and OPT with a consistent capacity-independent tie order, have the stack property and cannot show Belady's anomaly. OPT's minimum fault count is nonincreasing even when arbitrary ties break set inclusion. Non-stack algorithms, including FIFO and some LFU variants, can; it is not restricted to FIFO-like policies.
Conflict misses vanish in a fully associative cache; capacity misses vanish only with a larger cache; compulsory misses vanish only with prefetching or larger blocks.
Common misconceptions.
- "Write-through makes every write slow." A write buffer hides most of the memory latency.
- "A larger block always lowers the miss rate." For a fixed cache size, very large blocks raise it again.
- "A write miss always loads the block." Only under write-allocate.

Related material. In a multiprocessor, private caches can hold different values for one address; coherence protocols such as MESI keep them consistent (Stallings, Section 17.3). This is outside the GATE CS 2027 syllabus wording.

GATE examination perspective

POLICY PAIRS. Read whether the cache is write-back or write-through and whether it allocates on a write miss; count block reads, write-backs and word writes separately.
AVERAGE TIME WITH WRITES. Combine read and write times with their fractions; under write-through without a buffer, each write costs a memory access.
DIRTY VICTIMS. In write-back, a miss whose victim is dirty costs two block transfers.
REPLACEMENT TRACES. Trace LRU and FIFO carefully; FIFO order is set on loading and not changed by hits.
BELADY. LRU and OPT cannot miss more with increased capacity for the same reference string; OPT's set-inclusion property additionally requires consistent capacity-independent ties. Non-stack policies such as FIFO and some LFU variants can.
THREE Cs. Classify by first reference, then by a fully associative cache of the same size.
LRU BITS. Minimum $\lceil \lg (k!) \rceil$ per set; counter scheme $k \lg k$ .

Summary

Sources

C. Hamacher, Z. Vranesic, S. Zaky, Computer Organization, 5th ed., McGraw-Hill, 2002: Chapter 5, Sections 5.5 (Cache Memories, including 5.5.2 Replacement Algorithms) and 5.6.2 (Hit Rate and Miss Penalty).
D. A. Patterson, J. L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 5th ed. (MIPS edition), Morgan Kaufmann, 2013: Sections 5.3 (The Basics of Caches) and 5.4 (Measuring and Improving Cache Performance).
W. Stallings, Computer Organization and Architecture, 10th ed., Pearson: Sections 4.2 (Cache Memory Principles) and 4.3 (Elements of Cache Design); Section 17.3 (Cache Coherence and the MESI Protocol) for the related material.