A fabric has been proven deadlock-free: separate classes for requests and responses, deadlock-free routing, no cycles anywhere. Then a new accelerator is connected. It issues reads, and when its internal buffer is full, it stops accepting read data until its own output drains, through the same fabric. Under load, the response channel backs up into every router, and the "proven" fabric hangs. The proof had an assumption, and the accelerator broke it.
What must every endpoint promise for a fabric to be deadlock-free?
The obvious view is that a deadlock-free fabric is deadlock-free whatever is attached. But every argument in lesson 9.4 rested on one line: the last message in each chain, the response, is always consumed. A fabric can keep responses moving only if their destinations eventually take them. An endpoint that refuses responses until something else happens adds a new edge to the dependency graph (response waits for that something), and if that something depends on the fabric, the cycle is back.
Consumption assumption: every endpoint eventually accepts every response (and every other end-of-chain message) delivered to it, without needing any other message to make progress first. With it, responses always drain, so requests always complete, so everything else follows.
Technique | How |
|---|---|
Reserve space at request time | Allocate a buffer slot for each response before issuing the request; then every response has somewhere to go (lesson 6.6) |
Limit outstanding requests to buffer space | Never have more requests outstanding than responses you can hold |
Drain responses independently | Never make accepting a response depend on sending anything |
Bounded processing | If responses must be processed before buffer space frees, the processing must not need the fabric |
The first technique is the cleanest: if the endpoint only asks for what it has room to receive, the assumption holds by construction.
Protocol | The requirement |
|---|---|
PCI Express | Endpoints must advertise infinite completion credits: they may never refuse a completion for lack of buffer space. A device must therefore reserve space for every completion before issuing the read. |
AXI | A manager may delay RREADY or BREADY, but must eventually accept every response; interconnect deadlock-freedom arguments assume it. |
On-chip networks | Network interfaces sink responses unconditionally, usually into space reserved when the request was sent. |
The opening accelerator (illustrative) issued reads without reserving space for their data, and paused read-data acceptance whenever its output buffer filled. The fix was to issue a read only when a slot for its data was free, so its read data was always accepted, and to handle back-pressure on its output separately. The fabric needed no change: its proof had been right, given the assumption.
Responses may be refused while the fabric is congested by its own writes: a cycle through the fabric and a possible deadlock. It should issue reads only when response space is reserved.
It reserves space for every completion before sending the request, so it can always accept whatever comes back.
Deadlock-freedom arguments assume every endpoint eventually accepts every response it asked for.
An endpoint that refuses responses until it can send something else can reintroduce a cycle through the fabric.
Reserve response space at request time, and state the assumption as a checked requirement.