Direct-Mapped Caches

A cache holds a subset of memory, organized into fixed-size blocks (also called lines), each block being some number of contiguous bytes copied from main memory. The fundamental question any cache design must answer is a placement policy: given a block's address, which cache location(s) may it occupy? A direct-mapped cache answers this with the strictest possible rule: each memory block maps to exactly one cache line, computed by

Because the number of lines is chosen to be a power of two, this modulo operation reduces to selecting a contiguous slice of low-order address bits — no divider circuit, no comparator array, just wires routed to a bit slice. This is the central engineering payoff: placement becomes free in hardware. Since many different blocks in main memory map to the same line (they all share the same low-order index bits but differ in higher-order bits), the cache must store, alongside the data, enough information to know which block currently occupies that line. This extra information is the tag — the remaining high-order bits of the block's address, stored in a per-line tag field. On every access, the cache extracts the index from the requested address, reads out the tag stored at that line, and compares it against the tag portion of the requested address. A valid bit per line records whether the line currently holds a real, loaded block at all (as opposed to garbage left over from before the cache was initialized, or an intentionally invalidated entry). A cache hit occurs exactly when the valid bit is set and the stored tag equals the requested tag; anything else — invalid line, or valid line with a mismatched tag — is a miss.

An address presented to the cache is conceptually sliced into three fields, ordered from low bits to high bits:

• Block offset — selects a byte (or word) within the block; width = $\log_2(\text{block size in bytes})$.
• Index — selects one of the cache's lines; width = $\log_2(\text{number of lines})$.
• Tag — the remaining upper bits; uniquely identifies which memory block, among all blocks that alias to this index, is present.

The relationship is additive: `tag bits + index bits + offset bits = total address width`. This decomposition is exactly the topic developed further in Address Breakdown: Tag, Index, and Offset; here we focus on how the index and tag drive lookup and fill.

Lookup algorithm. On a memory reference, the cache controller performs the following steps every single cycle, in hardware, in parallel where possible: ``` function DIRECT_MAPPED_ACCESS(address, is_write, write_data): offset_bits = log2(BLOCK_SIZE) index_bits = log2(NUM_LINES) offset = address[0 : offset_bits-1] index = address[offset_bits : offset_bits+index_bits-1] tag = address[offset_bits+index_bits : MSB] line = cache_lines[index] if line.valid == true and line.tag == tag: // HIT if is_write: line.data[offset] = write_data // write hit line.dirty = true // (write-back caches only) else: return line.data[offset] // read hit else: // MISS: bring the whole block in from lower-level memory block = MEMORY_READ_BLOCK(base_address_of(address)) if line.valid and line.dirty: // must write back the evicted block first (write-back policy) MEMORY_WRITE_BLOCK(line.tag, index, line.data) line.data = block line.tag = tag line.valid = true line.dirty = false if is_write: line.data[offset] = write_data line.dirty = true else: return line.data[offset] ``` Two properties of this pseudocode deserve emphasis. First, there is no search loop — `cache_lines[index]` is a single array access, computable in one hardware step because `index` came directly from address bits. Second, eviction requires no decision-making: because only one line can ever hold this block, "which line do we replace on a miss" has a trivial, forced answer — the line at `index`, whatever currently sits there. This is the deepest structural simplification direct mapping provides relative to associative designs.

Initialization. All valid bits must be cleared to 0 at reset/power-on. Without this, a line's tag field could coincidentally equal a requested tag while holding meaningless data, producing a false hit — this is precisely why the valid bit is a logical necessity, not an optimization.

Time complexity of lookup. A direct-mapped access is $O(1)$: the index bits are extracted by wiring (no computation), the line array access is a single decode-and-read (as in a RAM), and the tag comparison is a single fixed-width equality comparator. No dependence on cache size shows up in the latency of comparison — only in the width of the tag comparator and the depth of the line-select decoder, both of which grow logarithmically with the number of lines and so are negligible in practice. Contrast this with a fully associative cache, where correctness requires comparing the incoming tag against every line's tag simultaneously — functionally still $O(1)$ in parallel hardware, but at the cost of $n$ comparators instead of $1$, and at real cost in area, power, and comparator fan-in delay that grows with associativity. Direct mapping is the design point that minimizes comparator hardware to a single unit.

Space complexity. Storage per line is `1 valid bit + tag_bits + block_size_bits (+ 1 dirty bit if write-back)`. Total cache storage is `NUM_LINES × (block_size_bits + tag_bits + O(1))`. Tag bits shrink as index bits grow (for fixed address width), so increasing the number of lines trades tag overhead for more distinct addressable lines — a real but secondary storage effect worth noting when computing effective cache overhead percentages.

Correctness argument. We must show the hit/miss decision is always correct: the cache reports a hit if and only if the requested block is genuinely present. Claim: `valid == true and tag == requested_tag` at index $i$ implies the data at line $i$ is exactly the current contents of the memory block whose address maps to index $i$ with that tag. Proof sketch by invariant. Maintain the invariant: whenever `cache_lines[i].valid` is true, `cache_lines[i].data` holds the most recently written version of the unique memory block whose (tag, index) pair equals (`cache_lines[i].tag`, i). This invariant holds initially vacuously (all valid bits false). It is preserved by the miss-handling code: on a miss, the algorithm loads the correct block — the one whose address decomposes to exactly this tag and this index, by construction of how `tag` and `index` were extracted from `address` — and only then sets `valid = true` and updates `tag`. It is preserved by write hits, since a write hit only mutates the data belonging to the block already validated at that line, and updates the coherent view of that same block. Since every memory block address decomposes to a unique (tag, index) pair (this is precisely why splitting address bits into disjoint tag/index/offset fields works — the mapping from address to (tag, index, offset) is a bijection), no two distinct blocks can ever be confused as long as the invariant is maintained: a tag match at index $i$ can only occur for the one block that legitimately owns that (tag, index) pair. Hence hit detection is sound. It is also complete — the cache reports a miss whenever the invariant does not currently hold data for the requested address, since either valid is false (never loaded) or the tag differs (a different block currently resides there), both of which correctly signal absence. $\blacksquare$

Tradeoff, stated honestly. Direct mapping is exposed to conflict misses: two blocks that are both heavily reused but happen to share the same index will repeatedly evict each other, even while most of the cache sits idle. This is a real, measurable performance pathology (classically visible when array strides align with cache size, e.g., accessing every $k$-th element where $k$ is a power of two matching the number of lines). Associativity — explored in Set-Associative Caches — directly targets this weakness by giving each index multiple candidate lines, at the cost of needing multiple comparators and a replacement policy. Direct mapping is thus not universally superior or inferior; it is the right choice when simplicity, power, and clock speed dominate the design goal (e.g., L1 caches under tight timing budgets), while associativity is preferred when miss rate dominates.

Consider a small direct-mapped cache with:

• Total size: 256 bytes
• Block size: 16 bytes → offset = $\log_2 16 = 4$ bits
• Number of lines: $256 / 16 = 16$ → index = $\log_2 16 = 4$ bits
• Address width: assume 12 bits for this example → tag = $12 - 4 - 4 = 4$ bits

We trace the following sequence of byte addresses (in hex, 12-bit): `0x034`, `0x1A2`, `0x038`, `0x234`, `0x1A5`. For each address, split into tag(4) | index(4) | offset(4):

The crucial row is the fourth: `0x038` and `0x234` share index `0011` but carry different tags (`0000` vs `0010`). Even though the line at index `0011` was just loaded and used at row 3, it must be evicted at row 4 because direct mapping permits no alternative slot — this is a conflict miss in action, and it is the single most important behavior this worked trace is meant to expose. Note also that if a sixth access to `0x034` followed, it would miss again — despite having been loaded twice already — purely because `0x234` occupies its line. A set-associative cache with 2-way associativity at this same index would have kept both blocks resident and turned that access into a hit.

The direct-mapped organization was not invented by a single named individual in the way an algorithm might be; it emerged as the natural, simplest engineering solution once cache memories themselves were proposed as an automatic layer between fast registers and slow main memory. Its intellectual lineage traces to the earliest cache hardware built for the IBM System/360 Model 85 and to the foundational analysis of memory hierarchies that followed.

Direct-mapped organization appears wherever latency is paramount and simplicity of hardware translates directly into a faster clock. Many processors use direct-mapped or low-associativity caches for their smallest, fastest L1 instruction caches, since a single-cycle hit time is often more valuable than a marginally lower miss rate. Translation Lookaside Buffers (TLBs), branch target buffers, and certain small first-level caches in embedded and mobile processors frequently adopt direct mapping for exactly this reason — the comparator and multiplexer overhead of associativity would otherwise threaten the target clock frequency. Understanding direct mapping is also the essential stepping stone to reasoning about the entire memory hierarchy: it is the simplest case from which Set-Associative Caches generalize (by allowing multiple lines per index) and fully associative caches represent the opposite extreme (any block anywhere, at the cost of full-array search). It also underlies practical performance tuning: programmers and compilers reasoning about cache-unfriendly access patterns — array strides that trigger repeated conflict misses — are implicitly reasoning about the exact modulo-indexing behavior described here.

Ask the tutor: How does adding associativity change the hit-detection hardware and the address field widths?