The scheme names come from the directory literature: Dir_i B and Dir_i NB from Agarwal, Simoni, Hennessy and Horowitz, "An Evaluation of Directory Schemes for Cache Coherence" (ISCA 1988), and the coarse vector from Gupta, Weber and Mowry, "Reducing Memory and Traffic Requirements for Scalable Directory-Based Cache Coherence Schemes" (ICPP 1990).
A K-pointer entry (written Dir_i with i = K) names up to K sharers exactly. When reader K + 1 arrives, H must apply one of three standard rules. It may never drop the new reader's id and keep treating the pointer list as complete: that reader would keep its S copy through a later GetM and read stale data after another cache stores.
Scheme | When reader K + 1 arrives | On a later GetM | Cost and clearing rule |
|---|---|---|---|
Dir_i B (broadcast) | Keep the K pointers, set the overflow bit, grant the read. | Inv to all N - 1 other caches, wait for N - 1 Inv-Acks. Caches that never held X ack from I. | Overflow clears only when the entry becomes exclusive(requester) after that full invalidation. PutS cannot clear it: H no longer knows which caches hold X, so it cannot tell which pointer to remove or whether other sharers remain. |
Dir_i NB (no broadcast) | No overflow bit. H invalidates one existing sharer (Inv, waits for its Inv-Ack) and gives its pointer to the new reader. | Inv only to the at most K pointed caches. | Never more than K copies. Pathological for widely read data (a lock word, a flag, code): readers keep invalidating each other and missing again. |
Dir_i CV_r (coarse vector) | The pointer bits are reinterpreted as group bits, one per group of r caches. The groups of the existing sharers and the new reader are set. | Inv to every member of every set group, each must ack, including members that never held X. | Uses the pointer storage only. Extra Invs only inside set groups. Exact pointers return when the entry becomes exclusive(requester). |
The two-core course model cannot show the cost. With N = 2 and K = 1 the case is degenerate: C0 and C1 both reading overflows the entry, but "all caches" is exactly {C0, C1}, so the broadcast reaches no one who did not hold X. For this lesson only, extend the model to four caches C0, C1, C2, C3 with a Dir_1 B entry (one pointer plus an overflow bit). The H directory column writes the entry as state, pointer, overflow.
From X = 0, C0 reads (pointer C0), then C1 reads. One pointer cannot name both, so H sets the overflow bit and grants C1 S. Now C3 sends GetM. H cannot tell which caches beyond C0 hold X, so it sends Inv to all three others and waits for three Inv-Acks (collected at H, as in the course model).
Step | C0 state / value | C1 state / value | C2 state / value | C3 state / value | H directory | Memory | Newest data |
|---|---|---|---|---|---|---|---|
(assumed) warm-up, C0 then C1 read from X = 0 | S / 0 | S / 0 | I / - | I / - | S, pointer C0, overflow | 0 | memory, C0, C1: 0 |
1 GetM(X) from C3 at H | S / 0 | S / 0 | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 0/3 | 0 | memory, C0, C1: 0 |
2 Inv at C0 | I / - | S / 0 | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 0/3 | 0 | memory, C1: 0 |
3 Inv at C1 | I / - | I / - | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 0/3 | 0 | memory: 0 |
4 Inv at C2, already I | I / - | I / - | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 0/3 | 0 | memory: 0 |
5 Inv-Ack from C0 at H | I / - | I / - | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 1/3 | 0 | memory: 0 |
6 Inv-Ack from C2 at H (wasted) | I / - | I / - | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 2/3 | 0 | memory: 0 |
7 Inv-Ack from C1 at H | I / - | I / - | I / - | IM^D / - | S, pointer C0, overflow, pend GetM C3, acks 3/3 | 0 | memory: 0 |
8 Data(0) at C3 | I / - | I / - | I / - | M / 0 | S, pointer C0, overflow, pend GetM C3, acks 3/3 | 0 | memory, C3: 0 |
(assumed) grant delivered | I / - | I / - | I / - | M / 0 | exclusive(C3), overflow cleared | 0 | memory, C3: 0 |
Messages 4 and 6 are the wasted work: an exact full vector would have sent two Invs and collected two acks. With N caches the overflowed GetM costs N - 1 Invs and N - 1 acks however few sharers really exist, which is why Dir_i B suits systems where overflow is rare. The overflow bit clears when C3's grant is delivered, the row after step 8, and nowhere else: only a completed full invalidation proves that no cache outside the new pointer holds X. Each Inv-Ack must be matched to the GetM that sent its Inv, so an ack left over from an earlier invalidation round cannot complete this one, as in ack counting and late data.
The same reads under the other schemes. Dir_1 NB: C1's GetS first makes H send Inv to C0 and wait for its Inv-Ack, then the pointer names C1, and C3's GetM sends one Inv, to C1. Every new reader of a widely read line costs a sharer its copy. Dir_1 CV_2: the 2-bit pointer becomes two group bits, {C0, C1} and {C2, C3}. C0 and C1 set only the first group, so C3's GetM sends Inv to C0 and C1 and nothing is wasted. Had C2 been the second reader instead of C1, both groups would be set, and C3's GetM would invalidate C0, C1 and C2, with C1 acking from I.
A set group bit does not mean every member holds data, much less the newest data. An exclusive entry still names one holder exactly, and a GetS for X is forwarded to that holder, as in every other lesson. Group size r trades storage against extra Invs: evaluate the workload's actual number of sharers per line, not its maximum core count.
The pointer names only C0. H cannot tell whether C1 was the only reader beyond C0 or one of several, so it cannot know that the pointer list is now complete. Overflow clears only when a GetM's full invalidation completes.