Snooping vs Directory Coherence

A coherence protocol says what must happen to each copy of a cache line, but something has to find those copies. There are two approaches. In snooping, every request is broadcast and every cache watches for it. In a directory scheme, a table records who holds each line, and messages go only to those caches. Snooping is simple and fast at small scale; a directory scales to hundreds of cores. This article explains how each works, what each costs, and how real designs mix the two.

12 min read | Intermediate

What You'll Learn

• Describe how a snooping system keeps caches coherent
• Describe how a directory tracks sharers and sends messages
• Compare the two in traffic, latency and storage
• Calculate directory storage overhead

The Question

Cache Coherence Protocols explained that a core about to write a line must invalidate all other copies. How does it know where they are? Either the core tells everyone, or something keeps track.

Snooping

In a snooping system, all caches share a broadcast medium, classically a bus. Each cache has a controller that watches, or snoops, every transaction. When core 0 wants to write a line, it places a request on the bus. Every other cache checks its tags for that line. If a cache has it, it invalidates its copy, or, if it holds the line in Modified state, supplies the data.

A bus has one great property: it puts all requests in a single order. Everyone sees the same sequence, so two cores cannot both believe they won a race. This makes the protocol simple. To answer quickly, a cache needs a way of checking tags without disturbing the core's own accesses, so tags are often duplicated, or have an extra port.

Here is the step-by-step sequence for a read of a line in another core's cache, in Modified state:

1. Core 1 misses and places a read request on the bus.
2. All the caches snoop the request. Core 0 finds the line in M.
3. Core 0 signals that it will supply the data, and stops memory from answering.
4. Core 0 sends the line, and both go to S (or O under MOESI).

Where Snooping Runs Out

A broadcast scales badly. Each cache must examine every request from every other core. If n cores each make r misses per second, then each cache sees n x r snoops, and total traffic grows with n. Most of the snoops find nothing, wasting bandwidth and energy. A physical bus also gets slow and hard to build as more things connect to it. Bus-based systems rarely go past about 8 to 16 cores.

Replacing the bus with a ring or another point-to-point network helps, but a broadcast is still a broadcast. Some processors use rings with snooping for moderate core counts.

Directories

A directory keeps, for each cache line, a record of who holds it. Requests go to the directory, usually located with the memory or the shared cache for that address, and the directory sends messages only where needed.

A simple entry might hold a state plus a presence vector, with one bit per core. For a line in Shared state held by cores 1 and 3, with 4 cores in total, it would be:

state: S     presence: 0 1 0 1

Now look at a write by core 2 to that line:

1. Core 2 sends a request for exclusive ownership to the directory.
2. The directory sees the line shared by cores 1 and 3, and sends each an invalidate.
3. Cores 1 and 3 drop their copies and send acknowledgments.
4. When all the acknowledgments are in, core 2 has the line in M, and the directory records that.

Nobody else was disturbed, and core 0 saw no traffic at all. Messages grow with the number of real sharers, and lines are usually held by few of them.

The price is an extra step. A read that must get data from another cache takes three hops: to the directory, from the directory to the owner, and from the owner to the requester. A snoop on a fast bus can answer in two. There is also more protocol work: because there is no single shared order of messages, acknowledgments must be counted, and races must be solved at the directory, which acts as the ordering point for each line.

Directory Storage

A presence vector needs one bit per core, for each line. With 64-byte lines (512 bits), a full-map directory uses:

overhead = (cores + state bits) / line bits

 16 cores:  (16 + 2) / 512  =  3.5 percent
 64 cores:  (64 + 2) / 512  = 12.9 percent
256 cores: (256 + 2) / 512  = 50.4 percent

For a directory that covers all of memory, this is too much, so designs reduce it in a few ways.

• Limited pointers store only a few core numbers per line, since most lines have few sharers. If more cores share it, the entry falls back to a broadcast.
• Coarse vectors keep one bit per group of cores, so that a message goes to the whole group.
• Sparse directories track only lines that are actually in a cache, rather than all of memory, like a cache of directory entries. Since caches hold far less than memory, this saves a lot. But evicting a directory entry forces the matching lines out of the core caches.

Snoop Filters and Hybrids

Real designs often combine the ideas. A snoop filter is a small directory that sits at the shared cache. It records which private caches may hold each line, and it blocks snoops that would find nothing. An inclusive last-level cache, as described in Multi-Level Caches and Prefetching, can do this for free, since its tags already say what lies above. A common arrangement in a chip with dozens of cores is a mesh network, with the shared cache sliced across it, and each slice acting as the directory for the addresses it owns.

Across many sockets of a server, another layer of directory or snoop filter tracks which socket holds what, because each hop off the chip is expensive. In a large system, coherence can stretch over several levels, each with its own protocol, joined at the boundaries.

Where the Directory Lives

A directory entry for an address has a fixed home, called its home node, usually found by hashing the address. Spreading addresses over many home nodes balances the load, so that no single directory becomes a bottleneck. In a chip with a sliced last-level cache, each slice is the home for its own addresses, and the directory state sits next to the cache tags. A core that misses must first find the home, which may be across the chip, even if the data turns out to be in a neighbor's cache. This is why placing related threads close to each other helps on large chips.

Keeping the Network Safe

Message-passing protocols bring a new danger: deadlock. A cache may be waiting to send a response, while the network is full of requests waiting for that same response to clear. If nothing can move, the whole chip stops. The standard fix is to keep message types apart, using separate virtual channels for requests, forwarded requests and responses. These share the wires but have their own buffers, and a rule says that responses can always make progress. Bugs in this area show up only under very heavy traffic, so these networks are usually checked with formal tools as well as simulation.

Scaling also raises the cost of each sharing event. On a mesh with dozens of stops, a cache-to-cache transfer can take well over a hundred cycles, which is many times longer than on a small cluster. So even with a perfect directory, a program that shares data heavily will scale worse than one that doesn't. The hardware can make sharing correct and reasonably efficient, but it can't make it free.

Comparing the Two

The trade-off is familiar: a simple design that suits small systems, and a more complex one with more state that lets the system scale.

Interconnect Choices

The physical network shapes all this. A bus suits a handful of cores. A ring gives a simple ordering, and works up to a few dozen stops. A mesh, a grid of routers, gives high bandwidth to many cores, with a latency that depends on distance. Distance then matters, so that access time depends on which cache slice holds the line. Some chips let software see this and place threads near their data. Buses and Transactions explains how such bus transactions are built up.

Some systems avoid hardware coherence altogether for part of memory. GPUs and accelerators often rely on software coherence, in which the driver flushes caches at agreed points, because tracking huge buffers in hardware would cost more than it saves.

Common Mistakes