Which hop are we counting?

Here a hop is one sender-to-receiver message leg, not one router crossing. We count the legs on the requester's critical path: the messages that must happen, one after another, before C1 can use the line.

Both traces start from the same checkpoint: X started at 0, C0 acquired M and stored 1. Now C0 M / 1, C1 I / -, H exclusive(C0), memory = 0. The protocol is MSI. C1 wants to write, so C0 must give up exclusive permission and its newest value.

Three hops: C0 sends Data straight to C1

In this variant no message tells H that C1 received Data. As on the course-model page, the model simply assumes H can tell, and H starts no conflicting transaction for X until then. A real protocol needs either a completion message from C1 (off C1's critical path, so C1 still uses the line after three legs) or a rule that C1 holds an early Fwd or Inv until its Data arrives (Part 4).

Four hops: Data goes through H

In both routes C0 stops writing before C1's grant is usable, and the value 1 is always in exactly one place. Memory stays stale in both, which is legal: C1 is now the dirty holder. The three-hop route is faster because the completion leg, when a real protocol adds one, is off C1's critical path: C1 uses the line after three legs, and only H waits for the fourth message.

When does the direct route win?

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

def lat(legs, d):
    return sum(d[l] for l in legs)

DIRECT = ["c1h", "hc0", "c0c1"]
BUFFERED = ["c1h", "hc0", "c0h", "hc1"]
LEGS = ["c1h", "hc0", "c0c1", "c0h", "hc1"]

equal = {l: 1 for l in LEGS}
assert len(DIRECT) == 3 and len(BUFFERED) == 4
assert lat(DIRECT, equal) < lat(BUFFERED, equal)

for c0c1 in range(1, 10):
    for c0h in range(1, 5):
        for hc1 in range(1, 5):
            d = {"c1h": 2, "hc0": 2, "c0c1": c0c1, "c0h": c0h, "hc1": hc1}
            direct_wins = lat(DIRECT, d) < lat(BUFFERED, d)
            assert direct_wins == (c0c1 < c0h + hc1)

congested = {"c1h": 2, "hc0": 2, "c0c1": 7, "c0h": 2, "hc1": 2}
assert lat(DIRECT, congested) > lat(BUFFERED, congested)

def c1_ready(legs, d):
    k = legs.index("c0c1") if "c0c1" in legs else legs.index("hc1")
    return lat(legs[:k + 1], d)

with_done = DIRECT + ["c1h_done"]
d_done = dict(equal, c1h_done=1)
assert len(DIRECT) == 3 and len(with_done) == 4
assert c1_ready(with_done, d_done) == c1_ready(DIRECT, equal) == 3
assert lat(with_done, d_done) == 4
print("PASS: direct wins iff d_c0c1 < d_c0h + d_hc1, completion is off C1's path")

Fewer legs usually wins: with similar delays on every leg, the direct route saves one leg on C1's critical path, and adding a completion message does not take that saving away. The direct route loses only when the C0-to-C1 leg is slower than the two legs through H, as in the congested case. Its real costs are elsewhere: H must track completion, and C1 must handle races such as a Fwd or Inv that arrives before its Data.

Related topics

• Shared course model

• Choose the source before the route