Miss Status Holding Registers and Memory-Level Parallelism

A blocking cache handles one miss at a time: the miss takes the cache, the core stalls, the fill returns, the core resumes. A non-blocking cache accepts further requests while a miss is outstanding, which requires somewhere to record them. The structure that records them is the miss status holding register file, and its size — typically a handful to a few dozen entries — sets a hard ceiling on how much memory latency a core can hide.

The register is a line, not a request

The naive design gives each outstanding miss its own slot, records the requesting instruction, and wakes that instruction when the data arrives. A 64-byte line fill serves up to eight 8-byte loads, and a loop that walks an array issues exactly that pattern: several loads to the same line, all missing simultaneously. Recording them separately would consume eight slots for one transfer and would issue eight memory requests for one line.

The standard design therefore allocates one entry per outstanding line, not per request. The entry holds the line address, the destination way once the line is placed, and a list of the requests that are waiting on it, each tagged with the offset within the line and the destination register or store buffer slot. A request that arrives while an entry for its line exists attaches to that entry and does not generate a new transaction. This is merging, and it is why the effective parallelism is measured in distinct lines in flight rather than in instructions in flight.

/* One MSHR: a pending line fill and the requests waiting on it. */
struct mshr {
    unsigned long line_addr;
    unsigned      busy;
    int           dest_way;
    unsigned      n_waiters;
    struct waiter {
        unsigned offset;        /* byte offset within the line */
        unsigned reg;           /* destination register, or store slot */
    } waiters[MAX_WAITERS];
};

/* A load that misses either allocates an MSHR or merges into an existing one. */
struct mshr *reserve(struct mshr_file *f, unsigned long line)
{
    for (int i = 0; i < f->n; i++)
        if (f->slot[i].busy && f->slot[i].line_addr == line)
            return &f->slot[i];                  /* merge: no new transaction */
    for (int i = 0; i < f->n; i++)
        if (!f->slot[i].busy) {
            f->slot[i] = (struct mshr){ .line_addr = line, .busy = 1 };
            return &f->slot[i];                  /* allocate: new fill */
        }
    return NULL;                                 /* file full: the miss blocks */
}

The merge case is not merely an optimisation. Without it, a streaming read of a large array would exhaust any plausible MSHR file with requests to the same few lines, and the core would stall on the ninth load even though only two lines were outstanding.

Primary and secondary misses

A miss that allocates an entry is a primary miss. A miss that merges into an existing entry is a secondary miss. The distinction matters for the tag array and for the replacement policy. The primary miss must reserve a way in the set, because the fill has to be placed somewhere; that reservation prevents another miss to the same set from evicting the way before the data arrives. The secondary miss needs no way, because the line is already on its way, and it consumes only a waiter slot.

The waiter list has a finite depth, and a request that finds it full is a third kind of stall: the line is coming, but there is no room to record the dependency. Practical designs therefore size the waiter list generously relative to the number of MSHRs — a line fill that serves eight loads needs eight waiters for the pathological case — or they allow a request to stall in the load queue without attaching, which is functionally equivalent and costs a replay.

The set of lines in flight is what the memory system actually sees. A core with 16 MSHRs and a 250-cycle latency can sustain at most 16 line fills per 250 cycles, which is one every 15.6 cycles, or roughly 4 bytes per cycle of delivered bandwidth for 64-byte lines. If the workload’s demand rate exceeds that, the core stalls on MSHR availability rather than on latency, and adding more cache capacity does not help. This is the quantitative reason MSHR counts grew from a handful in early out-of-order designs to several dozen in current ones, and the reason prefetching is valuable beyond its hit-rate effect: a prefetch consumes an MSHR too, but it does so without occupying a load-queue entry and without stalling an instruction.

Little’s law and where the ceiling binds

The relationship between outstanding requests and achieved throughput is Little’s law: the number of requests in flight equals the arrival rate times the time each spends in the system. Rearranged, the achievable rate is N / L for N outstanding requests and latency L. Doubling the MSHR count doubles the achievable rate only while the memory system can service the additional requests; beyond that point the queue moves from the core to the memory controller and the added entries only increase contention.

Three ceilings exist in sequence. The first is the MSHR count: the core cannot have more lines in flight than it has entries. The second is the number of outstanding requests the interconnect and memory controller support per core, which is usually larger than the MSHR count but not unlimited. The third is DRAM bandwidth, which is a property of the channels and the access pattern. A workload that raises its parallelism from 8 to 16 outstanding lines sees a benefit only if the first ceiling was the binding one; if the controller was already saturated, the change does nothing.

The interaction with the replacement policy is a common source of confusion. A non-blocking cache must not evict a line that has an MSHR outstanding, because the fill would then arrive with nowhere to go. Designs handle this by marking the reserved way as in-flight, so the replacement logic skips it. The consequence is that a set with several lines in flight has fewer eviction candidates, and a pathological access pattern that maps many misses to one set can stall on reservation even with free MSHRs elsewhere. This is a real limit on associativity’s benefit: a high-associativity set tolerates more in-flight fills, so the two parameters are chosen together.

/* A set with k ways in flight has only (W - k) eviction candidates. */
int pick_victim(struct set *s, int ways)
{
    for (int w = 0; w < ways; w++)
        if (!s->line[w].in_flight && !s->line[w].reserved)
            if (is_victim(s, w))                 /* policy-specific test */
                return w;
    return -1;                                   /* nothing evictable: stall */
}

Fill ordering and the wakeup path

When a fill returns, the cache must place the line and wake every waiter. The wakeup is a broadcast within the core: each waiter’s destination register or store slot is marked ready, and the scheduler is notified. Doing this for every waiter individually is a fan-out proportional to the merge depth, which is why some designs implement the wakeup as a single signal that the load queue scans.

The ordering constraint is the subtle part. A load that missed and merged into an MSHR has already been issued and has a position in the load queue; when the fill arrives, that load must complete in program order with respect to other loads. Out-of-order cores handle this by marking the load’s destination as pending and letting the reorder buffer retire it in order, which means a merged load that is behind an older, unresolved load still waits even though its data is available. The MSHR removes the memory latency, not the ordering latency.

Stores complicate the accounting further. A store that misses may allocate an MSHR to fetch the line for merging, which is a read-for-ownership rather than a plain fill, and the store’s data must be buffered until the line arrives. A store buffer entry therefore participates in the MSHR’s waiter list just as a load does, and a store that finds the MSHR file full blocks the store pipeline, which is one of the less obvious reasons a store-heavy loop can be slower than its instruction count suggests.

Failure modes specific to the mechanism

The first is deadlock by exhaustion. If every MSHR is occupied by a fill that cannot complete because the interconnect is waiting on a resource the core holds, the core cannot make progress. Designs avoid this by ensuring that a fill never depends on a request the core has not yet issued, which is a protocol-level obligation rather than a cache-level one.

The second is the livelock of a repeatedly evicted in-flight line. If the replacement policy evicts a reserved way despite the reservation — a bug, but one that occurs when the reservation and the policy disagree about which ways are candidates — the fill arrives for a line that is no longer wanted, and the requests attached to it must be replayed. Replays are correct but expensive, and they show up as a miss count higher than the number of distinct lines touched.

The third is a mismatch between the merge granularity and the coherence granularity. In a multiprocessor, a fill may be satisfied from another core’s cache rather than from memory, and that transfer may deliver a line in a state other than the one requested — Shared when Exclusive was wanted, for instance. The MSHR must therefore record the requested state and handle a response that grants less, which is the point where the miss-handling logic meets the coherence protocol and where a secondary miss that wanted to write cannot simply merge into a read fill.

A final practical note: the MSHR count is not visible to software, and no portable interface reports it. A program can only infer the ceiling by measuring how throughput scales as independent misses are added, which is the same experiment used to find the memory-level parallelism a loop actually exposes. The relevant software lever is therefore not the MSHR count but the loop structure that determines how many independent misses can be outstanding at once, as discussed under stride prefetching.