Cache Memory: Mapping, Replacement, and Writing

In the previous article, Memory Hierarchy, we saw that DRAM is too slow for the processor and that SRAM, although fast, is too expensive for large volumes. We ended with the principles of temporal and spatial locality: the empirical observation that real programs tend to reuse the same data and to access neighboring addresses. These are exactly the principles that make the cache memory viable, and that is what we are going to explore now.

In this article you will understand:

• the speed bottleneck between CPU and DRAM and why it grows over time;
• how the principles of locality translate into hit and miss;
• the three types of mapping that define where a block of MM can go in the cache;
• the algorithms that decide which block to replace when the cache is full;
• the write policies and how they keep cache and MM consistent;
• the physical organization of memory in chips: 1D versus 2D.

The CPU/MM Speed Problem

#

DRAM transfers data to the CPU at a speed lower than the one at which the processor can consume it. When this happens, the CPU has to wait, inserting wait states (waiting cycles) and sitting idle for part of the time.

Historically, processor performance has evolved faster than the latency and bandwidth of main memory. This mismatch was one of the main reasons for the appearance of cache memory.

It even has a name: the memory wall, a phrase made famous by the paper Hitting the Memory Wall: Implications of the Obvious, by Wulf and McKee, in 1995. And there are numbers behind it. From the mid-1980s on, processor performance started to grow at around 50% per year, while DRAM latency improved by something like 7% per year. Two different exponential rates do not drift apart slowly. That is why, in a current processor running at a few gigahertz, a main memory access costs on the order of two hundred cycles: two hundred opportunities to do work that the CPU spends waiting. Memory got better, but the processor got better much faster, and the gap has never stopped growing.

The figure below shows this divergence since 1980. The vertical axis is logarithmic: each grid line is worth ten times the previous one, and that is the only reason the two curves fit on the same chart. On a common scale, the memory curve would be a line practically glued to zero.

Two things can be read from the figure besides the gap itself. The first is that it was already tens of times when the term was coined, in 1995. The second is the processor curve flattening from the mid-2000s: the performance gain per core slowed down, for reasons that the last article of the series explains and that pushed the industry toward multicore processors.

In theory, a simple solution would be to build the entire main memory with SRAM, which is much faster. In practice, this is unfeasible: SRAM takes up more area on the chip and costs much more per stored bit. The engineering solution was to place a small, very fast memory between the CPU and the DRAM: the CPU cache.

Principles of Locality

#

The efficiency of the cache depends on an observable behavior of real programs called locality of reference. Two complementary principles describe this behavior:

The cache exploits both: on a miss, it loads a whole block of contiguous cells (spatial locality) and keeps that block in its slots for as long as possible (temporal locality). For most programs, this means that the vast majority of subsequent accesses result in a hit, with no need to search the DRAM. But how exactly does the CPU decide whether the data is in the cache or whether it has to “go down” to main memory?

How the Cache Works

#

The rule of computer architecture is: the CPU always tries to fetch instructions and data from the cache first. On each access, the hardware checks whether the desired block is already present in it:

graph TD
    A["CPU requests instruction or data"]
    B{"Block present
in the cache?"}
    H["HIT
Data transferred cache→CPU
at high speed"]
    M["MISS
Whole block transferred MM→cache
then word→CPU"]
    F["Data delivered to the CPU"]

    A --> B
    B -->|"Yes"| H --> F
    B -->|"No"| M --> F

Block transfer on a miss exploits spatial locality: if a word was needed now, there is a good chance that neighboring words will be accessed next too.

What a Hit Rate Is Worth

#

The fraction of accesses that result in a hit is called the hit rate, and is usually represented by \(h\). It is the number that decides whether the cache was worth it, because the average access time seen by the processor is a weighted average of the two possible paths:

where \(T_c\) is the cache access time and \(T_{MM}\) the main memory access time. It is worth putting numbers on this, using the orders of magnitude from the previous article, \(T_c = 1\) ns and \(T_{MM} = 80\) ns:

With a 95% hit rate, the processor sees a 4.95 ns memory, about 16 times faster than plain DRAM, using a cache that holds a tiny fraction of the total. This result is what justifies the existence of the cache.

The same calculation shows why cache design is so sensitive: at a 90% hit rate the average time rises to 8.9 ns, almost double. Every percentage point of hit rate lost is costly, because the term it feeds is the slower of the two.

Cache Types and Levels

#

A useful distinction is this:

• when we talk about cache memory in this article, the main focus is the processor cache, built to reduce the cost of accessing main memory;
• when we talk about speeding up disk access, in current systems the topic is commonly found under names such as file system cache or page cache in RAM, and not necessarily as “disk cache” in the classic sense.

But the general idea is always the same: use a faster layer to cushion the cost of accessing a slower layer.

Split cache: in many architectures, instructions and data are kept in separate caches, which reduces conflicts and improves internal parallelism.

The Four Cache Design Elements

#

Designing a cache memory requires hardware engineers to balance cost, complexity, and performance. This balance involves four elements:

Essential terminology:

• Block: unit of transfer between MM and cache; contains \(K\) contiguous cells
• Line: space in the cache that holds a block
• \(B\) = total number of blocks in MM
• \(Q\) = number of lines in the cache, where \(Q \ll B\)

Mapping Functions

#

Direct Mapping

#

Each block of MM has a single possible cache line, determined by:

The figure below illustrates direct mapping, where MM blocks are mapped to specific cache lines. Note that different blocks can compete for the same line, which can lead to frequent conflicts.

Division of the \(E\)-bit address:

To solve this constant “crushing” problem of direct mapping, engineers proposed the opposite extreme: giving the block total freedom.

Associative Mapping (fully associative)

#

A block can be placed in any cache line.

The figure below shows associative mapping, where MM blocks can be stored in any cache line, completely eliminating block conflicts. However, this requires more complex search logic to locate a specific block.

Division of the address:

To locate a block, the controller compares the tag with all \(Q\) lines simultaneously (parallel hardware).

Since the parallel search across all lines produces very expensive hardware, the industry had to find a middle ground between the rigidity of direct mapping and the high cost of associative mapping.

Set-Associative Mapping (set-associative)

#

A compromise between the two previous ones. The cache is divided into \(C\) sets of \(D\) lines each:

The figure below illustrates set-associative mapping, where the cache is divided into sets, and each MM block is mapped to a specific set, but can occupy any line within that set. This reduces block conflicts compared to direct mapping, while keeping the search complexity more manageable than in fully associative mapping.

Division of the address:

The tag is compared only with the \(D\) lines of the set, not with the whole cache.

graph LR
    B0["MM: Block 0
(0 mod C = 0)"]
    BC["MM: Block C
(C mod C = 0)"]
    B1["MM: Block 1
(1 mod C = 1)"]
    BC1["MM: Block C+1
(C+1 mod C = 1)"]

    subgraph S0["Set 0: D lines"]
        L00["Line 0"]
        L01["Line 1"]
    end

    subgraph S1["Set 1: D lines"]
        L10["Line 0"]
        L11["Line 1"]
    end

    B0 --> L00
    BC --> L01
    B1 --> L10
    BC1 --> L11

Comparison of the Three Techniques

#

The Three Types of Miss

#

With the three mappings on the table, we can classify the misses, and the classification matters, because each type is fought in a different way. The taxonomy is known as the three C’s, made canonical by Mark Hill and Alan Jay Smith in the late 1980s:

The third is the block conflict that appears throughout the direct mapping section, now with a name of its own. And the classification explains the comparison table at once: in fully associative mapping the conflict miss does not exist, because no block is forced to go to a specific place. What remains are the compulsory ones, which nobody avoids, and the capacity ones, which only a larger cache solves.

Let us see how to compute the address fields for each technique in a concrete example:

The interpretation of the fields becomes clearer when we look at what happens on a hit and a miss for a specific address:

Replacement Algorithms

#

When a miss occurs and there is no free line available, the controller has to decide which old block will be removed to make room for the new one.

This decision only exists in cases where a choice is possible, that is, in associative mapping and set-associative mapping. In direct mapping, the new block always replaces the block that already occupies the single line compatible with it.

Write Policies

#

Reading from the cache is simple: just check whether the block is present. Writing is more delicate, because an update made in the cache can leave Main Memory with an outdated copy. The write policies define how this synchronization will be handled.

Write Through

#

• Every write updates the cache and Main Memory at the same time
• Keeps MM always coherent with the cache
• Simple to understand and implement
• Can greatly increase write traffic to MM

Write Back

#

• The write updates only the cache
• The block receives a modification mark (dirty bit)
• MM is only updated when that block is removed from the cache
• Reduces write traffic, but requires additional control

Write Once, Which Is Not a Write Policy

#

Textbooks usually present write once as a third policy, on the same level as the two previous ones. The behavior described is this:

• the first write to a block is done as write through;
• subsequent writes are treated as write back.

But the classification is misleading. Write once was proposed by James Goodman in 1983 as a cache coherence protocol, a different category. The problem it solves is not keeping main memory up to date; it is warning the other caches that that block has changed. The first write goes to MM precisely because it is the bus that the other cores observe: there it works as a signal, not as synchronization.

And it is one of the predecessors of the protocol that dominates current systems, MESI, a name formed from the four states that each cache line can assume: Modified, Exclusive, Shared, and Invalid. That is the term to search for when the subject is coherence, and it is the one that reappears in the last article of the series, when dealing with multiprocessors.

The classic literature, as pointed out in William Stallings’ book, shows that approximately 15% of all memory operations are writes, since the vast majority of accesses consist of reads to fetch instructions and data. This number has been used as an argument that write through would suffice in most cases, but current practice is subtler, and depends on the level of the hierarchy.

Some microarchitectures use write through on the L1 toward the L2, like the data L1 of the AMD Bulldozer: the distance between the two is short, a write buffer absorbs the traffic, and the simplicity pays off. The L2 and L3, on the other hand, are typically write back, for a reason that the memory wall explains well. The scarcest resource in the system is DRAM bandwidth, and writing straight to that level would waste bandwidth on values that will still be overwritten in the cache itself before anyone needs them. Accumulating the writes and paying once, when the line is evicted, is what keeps the memory bus free for what matters.

Physical Organization of Memory

#

The 1D and 2D physical organization is an important memory implementation detail, but here it should be understood as a hardware backdrop for memory chips in general, and not as the core of the logical operation of the cache.

Whether we are talking about Cache or Main Memory, at the lowest hardware level, billions of bits need to be stored in transistors inside silicon chips. The way these circuits are designed so that an address finds its physical cell happens in two main ways:

Type 1D: Linear Selection

#

• The address directly drives one of \(2^E\) decoder outputs
• Conceptually simple
• Scales poorly for large values of \(E\)

Type 2D: Row/Column Matrix

#

• The address is split between row and column
• The cell is selected at the intersection between them
• Drastically reduces the size of the decoders

Example with \(E = 14\) bits:

graph TD
    ADDR["Address: 14 bits"]
    DL["Row Decoder
7 bits → 128 outputs"]
    DC["Column Decoder
7 bits → 128 outputs"]
    CEL["Selected cell
Row × column intersection"]

    ADDR -->|"bits 13 to 7"| DL
    ADDR -->|"bits 6 to 0"| DC
    DL --> CEL
    DC --> CEL

Conclusion and Next Articles

#

The cache is a small, fast, expensive component that, when well placed in the memory hierarchy, multiplies the efficiency of the whole system without requiring changes to the software. Each design decision (type of mapping, replacement algorithm, write policy) is a compromise between performance, cost, and implementation complexity.

For those who want to go deeper, much deeper, the canonical reference on the subject is What Every Programmer Should Know About Memory, by Ulrich Drepper (2007). It is about a hundred open pages that start more or less where this article ends: real measurements, and the effect of each cache decision on real code.

In the next article, we will talk about the CPU. The components that make up the central processing unit, how they are interconnected, and what happens step by step when an instruction is fetched and executed.

See you then.