Message Sequence Diagrams
The following scenarios illustrate canonical PicoLink transactions. Requests
and demands use solid arrows (->>); responses and acknowledgments use
dashed arrows (-->>). Transaction identifiers shown as small numbers
(1–16) are core-pool IDs; identifiers ≥ 20 are CM-pool IDs (see
Transaction identifier rules).
These diagrams show the reference behavior. Where the specification
permits alternatives (e.g. GrantS instead of GrantE, or overlapping
the memory fetch with invalidation — see Coherency Manager (CM) Behavior), a note
says so.
Read miss, line uncached
Core 0 reads an address not cached anywhere. The CM applies the
exclusive-grant optimization (PL-CHAN-06) and responds GrantE.
sequenceDiagram
participant Core0
participant CM
participant Memory
Core0->>CM: ReadShared [addr=X, txn=1]
CM->>Memory: Fetch addr X
Memory-->>CM: Data for X
CM-->>Core0: GrantE [addr=X, txn=1, data=...]
Result: Core 0: I → E. Directory: state=E, owner=Core0.
Read miss, another core holds E
Core 1 reads address X; Core 0 holds it in E. PicoLink has no
downgrade, so the CM must fully invalidate Core 0 (Invalidate is the
only demand message).
sequenceDiagram
participant Core0
participant Core1
participant CM
participant Memory
Core1->>CM: ReadShared [addr=X, txn=6]
CM->>Core0: Invalidate [addr=X, txn=20]
Core0-->>CM: InvAck [addr=X, txn=20]
CM->>Memory: Fetch addr X
Memory-->>CM: Data for X
CM-->>Core1: GrantE [addr=X, txn=6, data=...]
Result: Core 0: E → I. Core 1: I → E (sole holder, so
GrantE is recommended). Directory: state=E, owner=Core1.
Note
The directory recorded Core 0 in E, but Core 0 may have silently
written the line (E → M). The CM must therefore be prepared to
receive a WriteBack instead of the InvAck shown here
(PL-CM-01); that variant proceeds as in
Read while another core is Modified: forced WriteBack below.
Write miss, line uncached
Core 0 writes to an address not cached anywhere. Note the response is
GrantE, never GrantM (PL-CHAN-07): the store then performs the
silent E → M transition.
sequenceDiagram
participant Core0
participant CM
participant Memory
Core0->>CM: ReadExclusive [addr=X, txn=2]
CM->>Memory: Fetch addr X
Memory-->>CM: Data for X
CM-->>Core0: GrantE [addr=X, txn=2, data=...]
Note over Core0: Store performs<br/>silent E → M
Result: Core 0: I → E → M (silently). Directory:
state=E, owner=Core0 — the CM cannot observe the silent transition and
treats the entry as E-or-M (PL-CM-01). This is safe: Core 0 has
exclusive access either way.
Read while another core is Modified: forced WriteBack
Core 1 reads address X; Core 0 holds it in M (dirty). The
Invalidate forces Core 0’s WriteBack, which serves as the implicit
InvAck (PL-CHAN-05). The dirty data is committed to memory before
being granted (PL-CM-08) — memory is the only data source.
sequenceDiagram
participant Core0
participant Core1
participant CM
participant Memory
Core1->>CM: ReadShared [addr=X, txn=7]
CM->>Core0: Invalidate [addr=X, txn=30]
Core0-->>CM: WriteBack [addr=X, txn=30, data=dirty_line]
Note over Core0,CM: WriteBack echoes txn 30:<br/>implicit InvAck (PL-TXN-04)
CM-->>Core0: WriteBackAck [addr=X, txn=30]
CM->>Memory: Commit dirty data
CM->>Memory: Fetch addr X (now clean)
Memory-->>CM: Data for X
CM-->>Core1: GrantS [addr=X, txn=7, data=...]
Result: Core 0: M → I. Core 1: I → S. Directory:
state=S, sharers={Core1}.
Note
Core 1 is the sole holder here, so this CM could equally respond
GrantE (recommended by PL-CHAN-06); GrantS is always legal.
Voluntary WriteBack: cache eviction
Core 0 evicts a dirty line for capacity. The txn_id is core-allocated
(PL-TXN-01); the CM classifies the WriteBack as voluntary because no
Invalidate is outstanding (PL-TXN-05).
sequenceDiagram
participant Core0
participant CM
participant Memory
Core0->>CM: WriteBack [addr=X, txn=4, data=dirty_line]
CM->>Memory: Commit dirty data
CM-->>Core0: WriteBackAck [addr=X, txn=4]
Result: Core 0: M → I. Directory: Core 0 removed → state=I.
Race 1: dual Upgrade
Cores 0 and 1 both hold the line in S and write concurrently. The CM
arbitrates (lower index wins, PL-CM-05) and sends the loser its
Invalidate strictly before its Nack (PL-CM-07).
sequenceDiagram
participant Core0
participant Core1
participant CM
Core0->>CM: Upgrade [addr=X, txn=10]
Core1->>CM: Upgrade [addr=X, txn=15]
Note over CM: Arbitration (PL-CM-05):<br/>Core0 wins
CM->>Core1: Invalidate [addr=X, txn=22]
Core1-->>CM: InvAck [addr=X, txn=22]
Note over Core1: Pending Upgrade marked<br/>failed (PL-RACE-03)
CM-->>Core1: Nack [addr=X, txn=15]
CM-->>Core0: GrantM [addr=X, txn=10]
Core1->>CM: ReadExclusive [addr=X, txn=16] (retry)
Result: Core 0: S → M. Core 1: S → I, its Upgrade denied;
it retries with ReadExclusive (which cannot be denied — PL-PROG-01)
and will eventually force Core 0’s writeback and obtain the line.
Race 3: Invalidate crosses Upgrade
Core 1 (in S) issues Upgrade at the same moment the CM — serving
Core 0’s ReadExclusive — sends Core 1 an Invalidate. The messages
cross in flight (PL-ORD-02).
sequenceDiagram
participant Core0
participant Core1
participant CM
Core0->>CM: ReadExclusive [addr=X, txn=9]
par messages cross
Core1->>CM: Upgrade [addr=X, txn=12]
CM->>Core1: Invalidate [addr=X, txn=25]
end
Note over Core1: Invalidate hits pending Upgrade:<br/>mark failed (PL-RACE-03)
Core1-->>CM: InvAck [addr=X, txn=25]
CM-->>Core0: GrantE [addr=X, txn=9, data=...]
Note over CM: Upgrade from non-holder:<br/>stale (PL-RACE-03)
CM-->>Core1: Nack [addr=X, txn=12]
Core1->>CM: ReadExclusive [addr=X, txn=13] (retry)
Result: Core 0: I → E. Core 1: S → I, retries with
ReadExclusive.
Race 4: voluntary WriteBack crosses Invalidate
Core 0 evicts an M line just as the CM — serving Core 1’s
ReadShared — sends it an Invalidate. Core 0, now in I, answers
the Invalidate with InvAck (PL-RACE-04); the CM classifies the
in-flight WriteBack as forced on arrival (an Invalidate is
outstanding, PL-TXN-05) and treats it as the implicit acknowledgment;
the trailing InvAck is discarded as a duplicate.
sequenceDiagram
participant Core0
participant Core1
participant CM
participant Memory
Core1->>CM: ReadShared [addr=X, txn=14]
par messages cross
Core0->>CM: WriteBack [addr=X, txn=6, data=dirty_line]
CM->>Core0: Invalidate [addr=X, txn=26]
end
Note over Core0: Line already relinquished:<br/>answer InvAck (PL-RACE-04)
CM->>Memory: Commit dirty data
CM-->>Core0: WriteBackAck [addr=X, txn=6]
Core0-->>CM: InvAck [addr=X, txn=26]
Note over CM: Duplicate ack for txn 26:<br/>discarded (PL-RACE-04)
CM->>Memory: Fetch addr X (now clean)
Memory-->>CM: Data for X
CM-->>Core1: GrantS [addr=X, txn=14, data=...]
Result: Core 0: M → I (via its own eviction). Core 1: I → S.
Exactly one dirty payload reached memory (PL-MESI-03).