Where did the cycles go?

A store can miss write permission while its data is already cached. Use MSI and the existing upgrade trace and state/value table: C0 and C1 both hold S / 0 after reading X, which started uncached with memory = 0. C0 upgrades and C1 is invalidated. C0's SM^D copy can serve loads but stalls stores. The grant carries permission with no refill payload. Here we add timing to that trace rather than redraw it.

Measure from C0's request-ready time to grant delivery at C0, not to instruction retirement. Choose illustrative cycles: four in C0's request queue, three for each of the four serial message legs, two for H's directory lookup, one for C1 to handle the Inv, and one for H to construct the grant. No memory read is needed for this upgrade. C0's own tag lookup, which finds S without write permission (illustrative 1 cycle), happens before request-ready, so it is excluded from this window: add it if you measure from the store's issue. Assume all other queues are empty and each leg duration already includes its routing and serialization delay.

Overlapping invalidations

Extend the example to two sharers by adding a third core, C2, also in S / 0, so H records S{C0,C1,C2}. H sends both Invs together and grants only after the last Inv-Ack. C2 is farther away: 5 cycles per leg. The Inv wave costs as much as the slowest sharer's round trip, 11 cycles, not the 18 that summing both round trips would give, so the upgrade takes 24 cycles, not 31.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# Illustrative cycle counts, not measurements.
def timeline(parts):
    now, ends = 0, {}
    for label, duration in parts:
        now += duration
        ends[label] = now
    return now, ends

def upgrade(wave, queue=4):
    # C0 queue, GetM leg, H lookup, Inv wave, grant work, Data leg to C0
    return [("queue", queue), ("GetM leg", 3), ("H lookup", 2),
            ("Inv wave", wave), ("grant work", 1), ("Data leg", 3)]

# One sharer: the linked trace, C1 handles the Inv.
one = [("queue", 4), ("GetM leg", 3), ("H lookup", 2),
       ("Inv leg", 3), ("Inv handling at C1", 1), ("Inv-Ack leg", 3),
       ("grant work", 1), ("Data leg", 3)]
total, ends = timeline(one)
assert total == 20
assert [ends[k] for k in ("GetM leg", "H lookup", "Inv leg",
        "Inv handling at C1", "Inv-Ack leg", "grant work",
        "Data leg")] == [7, 9, 12, 13, 16, 17, 20]
assert sum(d for label, d in one if label.endswith(" leg")) == 12
assert timeline(upgrade(3 + 1 + 3))[0] == total
assert timeline(upgrade(3 + 1 + 3, queue=14))[0] == 30

# Two sharers (C2 added as a third core): the Invs overlap.
inv = {"C1": 3 + 1 + 3, "C2": 5 + 1 + 5}
wave = max(inv.values())
wrong = sum(inv.values())
assert wave == 11 and wrong == 18 and wave < wrong
two = timeline(upgrade(wave))[0]
assert two == 24 and timeline(upgrade(wrong))[0] == 31

# Sensitivity: removing the 1-cycle Inv handling saves exactly 1.
assert timeline(upgrade(3 + 0 + 3))[0] == total - 1
assert timeline(upgrade(max(3 + 0 + 3, 5 + 0 + 5)))[0] == two - 1

# Comparison rows: queue 4, lookup 2, legs 3 each.
cold_gets = 4 + 2 * 3 + 2 + 30 + 1
three_hop = 4 + 3 * 3 + 2 + 1
four_hop = 4 + 4 * 3 + 2 + 1 + 1
assert (cold_gets, three_hop, four_hop) == (43, 16, 20)
assert three_hop < four_hop < cold_gets
print("PASS: serial upgrade 20, overlapped two-sharer wave 24 not 31, comparisons")

The overlap matters only when the sharers' round trips run in parallel. H still needs every Inv-Ack before it grants, so the slowest sharer sets the wave. Removing one cycle of Inv handling at every sharer saves exactly one cycle, because each round trip shrinks by one and so does their maximum.

Other transactions get their own timelines

A cold data miss or a dirty intervention does different work, so do not transplant the 20 into them. Use the same illustrative costs (4 cycles of request queueing, 3 per leg, 2 for H's lookup, 1 for each handling or grant-construction step) and the leg counts from Part 3. Roles follow each linked trace: in the hop comparison, C1 requests and C0 is the dirty holder.

The four-hop intervention also totals 20 because it has the same shape as the upgrade: four legs, one peer handling step and one grant construction. In the cold GetS the memory read, not the leg count, dominates. The 30-cycle memory read is as illustrative as every other number here.

Related topics

• Shared course model

• The permission-only upgrade