Yes. A sparse directory has a tagged entry only for lines that some private cache holds, instead of one entry per memory line. It can run out of address entries even when every sharer set is tiny. Set-associative tracking also has conflicts: several addresses map to one full set while other sets have free ways. Active transaction capacity is a third limit, handled by the pending-entry machinery in Part 4.
Size a sparse directory against what it tracks: the private caches. The coverage ratio is the number of directory entries divided by the total number of lines in all the private caches it covers. As a general guideline, a ratio of 1 is the natural starting point, because when no line is shared every cached line needs its own entry, and designs commonly provision somewhat more (up to about 2) to absorb set conflicts. Sharing lowers the need, since one entry covers every private copy of its line.
Associativity matters as much as the ratio. Private-cache sets do not map one-to-one onto directory sets, so a low-associativity directory has hot sets even at a ratio above 1. The measurable cost is directory-induced invalidations: Invs or Fwd-GetMs that H sends only to free an entry, and the misses they cause when the victim's holders touch the line again. Compare candidate ratios and associativities by that count, per thousand instructions or as a fraction of all misses, on the target workloads.
Limit | Example | Standard response |
|---|---|---|
Sharers per entry | One line has more readers than pointer slots | An overflow rule from the previous lesson. |
Address entries | X and Y both need tracking but only one entry fits | Evict a victim entry: invalidate or recover its holders first, then reuse it. |
Set conflict | X and Y map to the same full set | Same eviction, despite free entries in another set. Raise associativity. |
Pending resources | An entry needs more active work than can be accepted | Backpressure or a defined retry, never an overwrite. |
Extend the two-core model with a second line Y in the same directory set as X, Y = 0 in memory and uncached, and assume that set has one way. From X = 0, C0 read X with no other holder, so MESI gave it E: C0 holds X E / 0, H's one entry in the set is exclusive(C0), memory = 0 for both lines. Now C1 sends GetS(Y). Y needs an entry, the set is full, and H must free X's entry first; GetS(Y) waits.
The victim is exclusive(C0). In MESI, C0 may have moved from E to M with a silent store, and H cannot tell, so it must take the dirty path rather than send a bare Inv. The message sequence is the dirty table of Filter Eviction and Back-Invalidation: H sends Fwd-GetM(X) to C0 on its own behalf, C0 returns Data and goes to I, H writes memory, and only then frees the entry. Here C0 was still E, so the Data carries 0 and the memory write leaves X = 0. Had C0 stored 1 silently, the same messages would deliver 1 to memory. Then H admits GetS(Y): it reads memory, Y = 0, and sends C1 Data(0) with E, so the set's one entry becomes exclusive(C1) for Y.
C0 lost X although it never chose to evict it: one directory-induced invalidation, and C0's next access to X misses. A cycle of such evictions in a hot set can cause misses even when the private working set fits. Increasing pointer slots would not help, because the shortage is entries, not sharers.
For progress, eviction needs response storage that always drains, eventual delivery, fair service and a victim policy that eventually picks an entry it can free. A full entry array alone does not prove deadlock. If an eviction waits on a response that needs the blocked allocation resource, investigate that resource cycle rather than adding entries as the only remedy.
In MESI an E holder may store without telling H, so C0 may be M with the only copy of the newest value. A bare Inv-Ack carries no data, so H forwards the request to recover the line and writes memory before freeing the entry.