A core updates a shared counter 16 times in a loop while three other cores hold copies of it. One protocol sends the new value to all three after every increment: 16 messages, and the other cores did not look at any of the intermediate values. Another protocol removes the three copies after the first increment and lets the other cores fetch the line again if and when they want it. Which is cheaper depends entirely on the pattern of writes and reads.
When a shared line is written, should the other copies be removed or updated?
The obvious answer is to update: the other caches keep valid copies, so their next read hits, and nobody waits for a miss. But every write then costs a message to every sharer, whether or not anyone reads the value before it changes again. Writes tend to come in runs (a loop, a structure being filled), so update protocols often send many values nobody reads.
Policy | On a write to a shared line | Cost | Good for |
|---|---|---|---|
Invalidate | Remove every other copy once; later writes are local | One message per run of writes, then a miss for each reader | Runs of writes before anyone reads |
Update | Send the new value to every sharer on every write | One message per write; readers always hit | One write, then many reads, repeated |
Each round, the producer writes one line K times, then each of three consumers reads it once. The model counts bus transactions per round for both policies (a broadcast counts once).
"""Invalidate or update: bus transactions for a producer and three consumers.
One cache line. Each round the producer writes it K times, then each of the three
consumers reads it once. Every bus request counts as one transaction (a broadcast
invalidation or update reaches all caches in one transaction).
invalidate: the producer's first write in a round invalidates the sharers; later
writes in the round hit its now-exclusive copy. Each consumer then misses
and fetches the line.
update: every write broadcasts the new value to the sharers; consumers always hit.
"""
ROUNDS, CONSUMERS = 1000, 3
def simulate(protocol, k):
# state of each consumer's copy: True = valid; producer starts as a sharer too
valid = [True] * CONSUMERS
producer_exclusive = False
bus = 0
for _ in range(ROUNDS):
for _ in range(k): # producer writes K times
if protocol == "invalidate":
if not producer_exclusive:
bus += 1 # one invalidation broadcast
valid = [False] * CONSUMERS
producer_exclusive = True
else:
bus += 1 # one update broadcast per write
for c in range(CONSUMERS): # each consumer reads once
if not valid[c]:
bus += 1 # read miss: fetch the line
valid[c] = True
producer_exclusive = False # the producer's copy is shared again
return bus / ROUNDS
ks = [1, 2, 3, 4, 8, 16]
inv = [simulate("invalidate", k) for k in ks]
upd = [simulate("update", k) for k in ks]
print("writes per round: " + " ".join(f"{k:5d}" for k in ks))
print("invalidate, bus/round: " + " ".join(f"{v:5.1f}" for v in inv))
print("update, bus/round: " + " ".join(f"{v:5.1f}" for v in upd))
assert inv == [1 + CONSUMERS] * len(ks) and upd == [float(k) for k in ks]
cross = next(k for k, i, u in zip(ks, inv, upd) if u >= i)
print(f"PASS: update costs less only while a round has fewer than {cross} writes (equal at {cross}); beyond that invalidation's cost stays flat at {1 + CONSUMERS}")It prints:
writes per round: 1 2 3 4 8 16
invalidate, bus/round: 4.0 4.0 4.0 4.0 4.0 4.0
update, bus/round: 1.0 2.0 3.0 4.0 8.0 16.0
PASS: update costs less only while a round has fewer than 4 writes (equal at 4); beyond that invalidation's cost stays flat at 4Invalidation's cost per round is fixed: one invalidation plus one miss per consumer. Update's cost grows with every write. With one write per round, update is four times cheaper; with sixteen, four times dearer. Real workloads contain plenty of runs of writes, and an invalidation-based protocol also needs no bandwidth for lines that one core uses privately.
Protocol family | Policy |
|---|---|
MSI, MESI, MOESI, MESIF (almost all processors) | Invalidate (fact T23) |
AMBA ACE and CHI | Invalidation-based (fact A23) |
Some early multiprocessors (the Dragon and Firefly protocols) | Update, for workloads dominated by producer-consumer sharing |
A design (illustrative) used update coherence for a shared statistics block that one core wrote thousands of times per second and others read once a second. Almost all bus bandwidth went to delivering values nobody read. Switching to invalidation cut that traffic by orders of magnitude; the readers paid one miss per second each.
Invalidate costs 1 + 5 = 6 per round, update costs K: they tie at K = 6.
Their next read hits, with no miss latency, because their copy was kept current.
On a write to a shared line, invalidate the other copies or update them.
Invalidation costs once per run of writes plus a miss per reader; update costs a message per write.
Runs of writes are common, so almost every real protocol invalidates.