What does a TileLink cache hold instead of M, E, S and I?

A permission on a position in a tree, not a MESI letter. This lesson uses the SiFive TileLink Specification, version 1.8.1 (27 January 2020), chapters 1, 2, 5 and 9. The specification calls the requesting side of a link the master interface and the managing side the slave interface. On the course model, C0 and C1 are masters and H is the slave that manages X.

Three conformance levels

Only TL-C keeps cached copies coherent. A TL-UL device such as a timer never caches, so it needs no B, C or E channel. A TL-C agent talking to a TL-UL device must either avoid the advanced features or sit behind an adapter (section 1.1).

Five channels and a strict priority

Section 2.2 fixes the priority A < B < C < D < E and says it must be strictly enforced. Section 5 turns it into forward-progress rules: an agent must eventually accept a presented beat and eventually answer a received request, unless it has a higher-priority message in flight or unanswered. So an agent may block a lower channel while it waits on a higher one, never the other way round. Section 9.2 adds that higher-priority messages must be able to bypass lower-priority ones in the network, even to the same agent.

This is the request < forward < response rule with one more class. Every response travels on a higher channel than its request: Acquire (A) is answered by Grant (D), Probe (B) by ProbeAck (C), Release (C) by ReleaseAck (D), and Grant (D) by GrantAck (E). A message that an agent receives can therefore only make it wait for messages above it, and E, at the top, waits for nothing.

Why must E be highest? Section 9.2 says the slave should not issue a Probe for a block while a GrantAck for it is pending. So H holds X's next transaction until GrantAck arrives. If GrantAck could queue behind an Acquire for X on a shared buffer, H would wait for GrantAck, GrantAck would wait for the Acquire, and the Acquire would wait for H: a cycle. Putting GrantAck on the top channel means it always sinks.

Permissions: None, Branch, Trunk, Tip

For one address, all caching agents form a tree rooted at the slave. Section 9.1 names each node's position. The table also gives the accesses allowed, from Table 29 and the section 9.1 text, and says where the two disagree.

Three points matter when you read traces. First, Tip covers both E and M: the permission says nothing about dirty data. Exactly as H cannot tell E / 0 from M / 1 in the course (exclusive(C0)), a TileLink home cannot tell a clean Tip from a dirty one until the data comes back. Second, the parameters on a link use only N, B and T. Seen from H across one link, T means the master's subtree holds Trunk-or-Tip: the course's exclusive holder. Third, Trunk appears only in a hierarchy; on the two-cache course model the only caching agents are C0 and C1. A cluster cache inside a two-level directory that has passed exclusive permission up to its core is a Trunk.

Worked snapshots on the course model

Independent settled snapshots, not a sequence. X started at 0; rows with 1 assume C0 stored 1. The last column gives each cache's TileLink permission.

The E and M rows have identical TileLink permissions and identical directory records. The dirty bit lives inside C0's cache, and appears on the wire only when C0 answers a Probe with ProbeAckData or evicts with ReleaseData.

Permission transfers

Every TL-C message carries a parameter naming the transition. Section 9.1.4 (Table 31) defines four groups with these 3-bit encodings:

Table 31 calls the downgrade group Prune; the message sections of 9.3 call the same group Shrink. A Probe uses Cap because the home only states a ceiling. Capping above the current permission is allowed and changes nothing, so a toB Probe to a Branch is answered BtoB. A Grant uses Cap and may exceed what the Acquire asked for: an NtoB Acquire answered with a toT Grant is the MESI E grant.

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

ORDER = "ABCDE"
MSGS = {  # message: (channel, possible responses), TileLink 1.8.1 Table 30
    "AcquireBlock": ("A", ["Grant", "GrantData"]), "AcquirePerm": ("A", ["Grant"]),
    "ProbeBlock": ("B", ["ProbeAck", "ProbeAckData"]), "ProbePerm": ("B", ["ProbeAck"]),
    "ProbeAck": ("C", []), "ProbeAckData": ("C", []),
    "Release": ("C", ["ReleaseAck"]), "ReleaseData": ("C", ["ReleaseAck"]),
    "Grant": ("D", ["GrantAck"]), "GrantData": ("D", ["GrantAck"]),
    "ReleaseAck": ("D", []), "GrantAck": ("E", []),
}

def responses_climb(msgs):
    return all(ORDER.index(msgs[r][0]) > ORDER.index(ch)
               for ch, rs in msgs.values() for r in rs)

assert responses_climb(MSGS)
bad = dict(MSGS, Push=("D", ["PushAck"]), PushAck=("B", []))
assert not responses_climb(bad)   # a response below its request breaks the rule

RANK = {"N": 0, "B": 1, "T": 2}
GROW = {"NtoB": 0, "NtoT": 1, "BtoT": 2}
PRUNE = {"TtoB": 0, "TtoN": 1, "BtoN": 2}
REPORT = {"TtoT": 3, "BtoB": 4, "NtoN": 5}
def delta(name):
    return RANK[name[3]] - RANK[name[0]]
assert all(delta(n) > 0 for n in GROW)
assert all(delta(n) < 0 for n in PRUNE)
assert all(delta(n) == 0 for n in REPORT)
# ProbeAck and Release put Prune or Report in one field: encodings must not collide
assert not set(PRUNE.values()) & set(REPORT.values())
assert set(GROW.values()) & set(PRUNE.values())   # same codes, so the opcode decides

COURSE = {"I": "N", "S": "B", "E": "T", "M": "T"}
assert [s for s in COURSE if COURSE[s] == "T"] == ["E", "M"]   # T cannot say clean or dirty
print("PASS: TileLink responses climb A<B<C<D<E, Prune/Report codes are disjoint, T covers E and M")

Related topics

• Shared course model

• Next: TileLink transactions

• The request < forward < response rule

• Message classes and virtual networks