Deadlock Avoidance

Module 14 · Chapter 14.3 · CHI Flow Control

Project thread — 14.2 made channels independent. 14.3 orders their dependencies so they can't deadlock; 14.4 is backpressure.

1. Learning Outcomes

By the end of this chapter you should be able to:

• Explain that per-channel flow control is necessary but not sufficient to avoid deadlock.
• State that deadlock arises from a cycle in channel dependencies.
• State the rule — responses and data must always be sinkable, without issuing a request.
• Explain why requests may depend on responses, but not the reverse — keeping the graph acyclic.
• Diagnose the fabric-freezing deadlock from gating response acceptance on request issue.
• Implement a representative drain-rule model in SystemVerilog, Verilog-2001, and VHDL.

2. Why Should I Learn This?

Chapter 14.2 gave every channel its own credits, so no buffer overflows. But "no overflow" is not "always makes progress." Independent channels can still reach a state where each is waiting on another to move first — and if those waits form a cycle, nothing ever moves. That is deadlock, and it is worse than a dropped flit: the entire fabric freezes, every transaction hangs, and there is no timeout or retry that fixes it — the system is simply stuck.

The defense is a dependency rule, and it is one directional constraint: responses and data must always be able to drain, regardless of anything on the request channel. A node must sink an incoming response without needing to send a request or hold a request credit. That guarantees the response channel is never part of a wait cycle, which makes the whole channel-dependency graph acyclic — and an acyclic graph cannot deadlock. One conditional edge that violates this — "I'll accept your response once I can issue my request" — recreates the cycle. This chapter is that rule and why it is inviolable.

3. Key Terms

4. Previous Chapter Connection

Chapter 14.2 made the channels independent for flow control — separate buffers, separate credits. This chapter adds the missing piece: independence stops overflow but not deadlock, which is a property of how the channels depend on one another.

The dependency structure has been implicit all along. A request (REQ) triggers a response (RSP) and data (DAT) — request comes first, response follows (Chapter 7.1). CHI turns that natural order into a hard rule: because responses answer requests, responses must be able to complete without waiting on new requests, or the answer could block its own question. This chapter formalizes that as an acyclic dependency and shows the deadlock when a design accidentally makes a response wait on a request — closing a loop the protocol forbids.

5. Core Concept — responses must always drain

Deadlock is a cycle of channel waits; CHI breaks it by requiring responses and data to always be sinkable, so the dependency graph is acyclic.

• Deadlock is a cycle. If channel A waits on B and B waits on A, both stall forever. Per-channel credits (Chapter 14.2) prevent overflow but not this.
• Responses and data must always drain. A node must accept an incoming response or data flit unconditionally — without first issuing a request or holding a request credit.
• Requests may depend on responses, not vice versa. A request can wait for a response to free resources; a response must never wait for a request. The dependency is one-directional.
• One direction means acyclic. With responses independent of requests, the dependency graph has no cycle — and an acyclic graph cannot deadlock.

The synthesis:

Deadlock arises when channel dependencies form a cycle. CHI forbids the cycle with a drain rule: responses and data must always be sinkable, accepted without issuing a request or holding a request credit. Requests may depend on responses draining, but responses must never depend on requests — a one-directional dependency that keeps the channel graph acyclic. Gate response acceptance on request issue and you close the cycle — the fabric deadlocks.

6. Engineering Mental Model — a one-way staircase

Think of two landings connected by stairs, and a rule about which way people may wait.

• People on the upper landing (requests) may wait for the lower landing (responses) to clear before they come down — that is fine, they can always eventually descend once space opens below.
• People on the lower landing (responses) must never wait for the upper landing to clear before they leave — the exit at the bottom is always open. They can always walk out.
• Because the lower landing always empties, space keeps opening, so the upper landing keeps draining too. Traffic flows in one direction of dependency: up-waits-on-down, never down-waits-on-up.
• Now break the rule: tell the lower-landing people "you may only leave once the upper landing has cleared." Now down waits on up, and up waits on down — both landings jam, nobody moves. A deadlock on the stairs.

The bottom exit must stay unconditionally open. Responses and data are the lower landing: they must always be able to leave, or the whole staircase locks.

7. Engineering Diagram — the channel-service order

The two sink states always complete — no edge out of them waits on a credit. Only Issue Request can stall (its self-loop), and that stall lets control still return to sinking. Sinking never depends on issuing; issuing depends on sinking having freed room. One direction, no cycle.

8. Which Dependencies Are Allowed

The permitted and forbidden dependency directions.

The rule to carry: dependencies may point from requests toward responses/data, never back. A request stalling is safe because responses keep draining and eventually free what the request needs. A response stalling on a request is fatal because the request may itself be stalled on that very response draining — the cycle. The asymmetry is the whole design: the channel that answers (response/data) must be unconditionally free, so the channel that asks (request) always has a way forward.

9. Why Acyclic Means Deadlock-Free

The formal backbone, stated plainly.

• Deadlock requires a cycle. A set of agents can deadlock only if their wait-for relation contains a cycle — each waiting on the next, around to the first. No cycle, no deadlock.
• The drain rule removes the back-edge. By forbidding "response waits on request," CHI removes the one edge that could close a cycle between the ask channel and the answer channel.
• So the graph is acyclic. Requests depend on responses/data; responses/data depend on nothing on the request side. The dependency graph is a one-way relation — acyclic by construction.
• Progress is guaranteed. In an acyclic graph, some channel always has no unmet dependency and can move; its progress frees the next, and so on. The fabric never fully stalls.

The point to carry:

Deadlock freedom is not achieved by making stalls rare — it is achieved by making a fatal stall impossible. A congested fabric will stall channels; that is normal backpressure (Chapter 14.4). The design question is whether a stall can ever become permanent, and the answer depends entirely on the shape of the dependency graph, not on how much buffering you throw at it. More buffers delay a deadlock; they do not prevent it, because a cycle with big buffers still deadlocks once the buffers fill. The only cure is topological: forbid the back-edge so no cycle can exist. This is why the drain rule is absolute rather than best-effort — a single node that sometimes gates response acceptance on request issue reintroduces the back-edge, and one back-edge anywhere in the fabric is enough to make deadlock reachable. Correctness here is a property of the graph, and graphs do not have "mostly acyclic."

10. A Congested Fabric — draining vs deadlocking

The same congestion, resolved two ways.

1. Congestion hits. The request channel is backed up — request credits are scarce because downstream resources are full.
2. Correct: responses keep draining. Each node sinks incoming responses unconditionally. Sinking a response frees a resource, which returns a request credit, which lets a stalled request proceed. Congestion clears.
3. The request that was stalled now moves. With a returned credit, the waiting request issues. Forward progress resumes; the stall was temporary (backpressure, Chapter 14.4).
4. Broken: a node gates response sinking on issuing a request. This node holds an incoming response until it can send its own request — but it needs a request credit to do so.
5. The cycle closes. The credit it needs is freed only when the downstream sinks responses — which is stalled waiting on this node to sink its responses. Both wait forever. Deadlock — the fabric freezes.

The difference is one conditional edge. In step 2 responses drain unconditionally; in step 4 they drain only if a request can issue — and that "only if" is the back-edge that deadlocks everything.

11. RTL / Hardware View — the drain rule

Response and data acceptance depend only on their own pre-allocated buffer space — never on a request credit. Requests may stall. Representative.

// Representative channel drain-rule model (educational).
// The rule: sinking a RESPONSE or DATA flit depends ONLY on that channel's own
// pre-allocated buffer space -- NEVER on a request credit or request issue. Requests
// may stall on a credit. This keeps the dependency graph acyclic (deadlock-free).
module chi_drain_rule (
  input  logic  resp_valid,       // a response flit is offered
  input  logic  resp_buf_space,   // this node's response sink buffer has room (pre-allocated)
  input  logic  data_valid,       // a data flit is offered
  input  logic  data_buf_space,   // this node's data sink buffer has room (pre-allocated)
  input  logic  req_want,         // this node wants to issue a request
  input  logic  req_credit,       // a request credit is available
  output logic  sink_resp,        // accept the response (must NOT depend on req_credit)
  output logic  sink_data,        // accept the data     (must NOT depend on req_credit)
  output logic  issue_req         // issue a request (MAY stall on credit)
);
  // Sinking depends ONLY on the channel's own buffer -- unconditional w.r.t. requests.
  assign sink_resp = resp_valid && resp_buf_space;
  assign sink_data = data_valid && data_buf_space;
  // Issuing a request may stall on a credit -- but this never gates the sinks above.
  assign issue_req = req_want && req_credit;
endmodule

The same behavior in Verilog-2001:

// Representative channel drain-rule model (Verilog-2001).
module chi_drain_rule (
  input  wire resp_valid, resp_buf_space, data_valid, data_buf_space,
  input  wire req_want, req_credit,
  output wire sink_resp, sink_data, issue_req
);
  // Sinks depend only on their own buffers -- never on req_credit.
  assign sink_resp = resp_valid & resp_buf_space;
  assign sink_data = data_valid & data_buf_space;
  assign issue_req = req_want   & req_credit;   // requests may stall
endmodule

And in VHDL:

-- Representative channel drain-rule model (VHDL).
library ieee;
use ieee.std_logic_1164.all;
 
entity chi_drain_rule is
  port (
    resp_valid, resp_buf_space : in  std_logic;
    data_valid, data_buf_space : in  std_logic;
    req_want, req_credit       : in  std_logic;
    sink_resp, sink_data       : out std_logic;
    issue_req                  : out std_logic
  );
end entity;
 
architecture rtl of chi_drain_rule is
begin
  -- Sinks depend ONLY on their own pre-allocated buffer -- never on req_credit.
  sink_resp <= resp_valid and resp_buf_space;
  sink_data <= data_valid and data_buf_space;
  issue_req <= req_want   and req_credit;    -- requests may stall
end architecture;

In all three, sink_resp and sink_data reference only their own buffer space — req_credit appears only in issue_req. Sinking is unconditional w.r.t. requests; the dependency stays one-way. The DebugLab adds req_credit into sink_resp.

12. Verification View — sinks never depend on request credit

The properties that keep the graph acyclic: response/data sinking is independent of request state.

// Bind to chi_drain_rule.
// 1. Response sinking depends only on its own buffer -- never on req_credit.
property p_resp_sink_independent;
  @(*) (resp_valid && resp_buf_space) |-> sink_resp;
endproperty
// (and: sink_resp must be insensitive to req_credit -- proven by structural check)
 
// 2. Data sinking is likewise independent of request state.
property p_data_sink_independent;
  @(*) (data_valid && data_buf_space) |-> sink_data;
endproperty
 
// 3. A stalled request (no credit) does NOT prevent sinking.
property p_stall_does_not_block_sink;
  @(*) (!req_credit && resp_valid && resp_buf_space) |-> sink_resp;
endproperty

The system point, beyond the checks:

The decisive property is structural, not behavioral: sink_resp must be a function of resp_valid and resp_buf_space only — req_credit must not appear in its cone of logic at all. This is stronger than any simulation can show, because simulation can only demonstrate that sinking happened to work in the cases exercised; it cannot prove sinking is independent of request state in every case. So deadlock freedom is best verified by construction and inspection — proving the dependency edge does not exist in the netlist — rather than by chasing the deadlock in simulation, which requires hitting the exact congestion corner that closes the cycle and may pass a million random tests before failing in the field. The lesson generalizes: liveness properties like deadlock freedom are established by reasoning about the shape of the dependency graph, and the most reliable check is to confirm the forbidden edge is structurally absent, not to hunt for the deadlock it would cause.

• What it proves: response/data sinking is independent of request credit — no back-edge.
• What it does not prove: the sink buffers are truly pre-allocated at the system level — a design obligation.
• Bug signature: req_credit in the logic cone of sink_resp/sink_data — the cycle-closing edge.

13. Testbench — a stalled request must not block response sinking

Stalls the request channel and checks responses still sink.

module tb_chi_drain_rule;
  logic resp_valid, resp_buf_space, data_valid, data_buf_space;
  logic req_want, req_credit;
  logic sink_resp, sink_data, issue_req;
  int errors = 0;
 
  chi_drain_rule dut (.*);
 
  task check(input string nm, input logic exp_sink_resp);
    begin
      #1;
      if (sink_resp !== exp_sink_resp) begin errors++; $display("FAIL %s: sink_resp=%0b exp=%0b", nm, sink_resp, exp_sink_resp); end
      else $display("PASS %s: sink_resp=%0b (issue_req=%0b)", nm, sink_resp, issue_req);
    end
  endtask
 
  initial begin
    // A response is offered and there is buffer room, but NO request credit (request stalled).
    resp_valid = 1; resp_buf_space = 1; data_valid = 0; data_buf_space = 1;
    req_want = 1; req_credit = 0;   // request cannot issue
    check("stalled request, response offered", 1'b1);   // must STILL sink
 
    // Request credit returns; request can now issue -- sinking unaffected.
    req_credit = 1;
    check("request now issues", 1'b1);
    #1;
    if (!issue_req) begin errors++; $display("FAIL request did not issue with credit"); end
    else $display("PASS request issued once credit available");
 
    // No buffer room -> response cannot sink (its OWN buffer, not request-related).
    resp_buf_space = 0;
    check("response buffer full", 1'b0);
 
    if (errors == 0) $display("ALL TESTS PASSED");
    else             $display("%0d FAILURE(S)", errors);
    $finish;
  end
endmodule

Expected output:

PASS stalled request, response offered: sink_resp=1 (issue_req=0)
PASS request now issues: sink_resp=1 (issue_req=1)
PASS request issued once credit available
PASS response buffer full: sink_resp=0
ALL TESTS PASSED

14. DebugLab — gating response acceptance on request issue

node logic: sink_resp = resp_valid && resp_buf_space && req_credit   // <-- req_credit!
under congestion: req_credit = 0 (downstream resources full)
  -> this node will NOT sink responses (waits for req_credit)
  -> downstream needs this node to sink responses to free a resource
  -> ... which would return the req_credit this node is waiting for
  => cycle: sink_resp -> req_credit -> downstream sink -> sink_resp
both sides wait forever -> DEADLOCK
correct: sink_resp = resp_valid && resp_buf_space   // no req_credit term

15. Common Mistakes

• Gating response sinking on a request. Assumption: batching is efficient. Bug: deadlock (the DebugLab). Prevention: sink responses unconditionally.
• Sharing a buffer between sink and issue. Assumption: one buffer saves area. Bug: coupling that closes a cycle. Prevention: pre-allocated sink buffers.
• Assuming more buffering prevents deadlock. Assumption: big queues are safe. Bug: cycle still deadlocks when full. Prevention: fix the graph, not the size.
• Letting data wait on request credit. Assumption: data is like a request. Bug: back-edge. Prevention: data drains unconditionally.
• Relying on timeouts to recover. Assumption: a stuck fabric recovers. Bug: true deadlock has no recovery. Prevention: make it unreachable.
• Testing only light load. Assumption: it passed simulation. Bug: deadlock hides in congestion corners. Prevention: verify the graph structurally.

16. Engineering Checklist

• Sink responses and data unconditionally — no request-credit dependency.
• Pre-allocate response/data receive buffers so acceptance is guaranteed.
• Allow requests to depend on responses draining — but never the reverse.
• Confirm req_credit is absent from the logic cone of sink_resp/sink_data.
• Verify a stalled request does not block sinking.
• Establish deadlock freedom by the acyclic dependency graph, not buffer size.

17. Key Takeaways

• Per-channel flow control prevents overflow but not deadlock.
• Deadlock is a cycle in channel dependencies.
• Responses and data must always be sinkable — without issuing a request.
• Requests may depend on responses; responses must never depend on requests.
• This one-directional rule keeps the graph acyclic — and acyclic cannot deadlock.
• Gating response acceptance on request issue freezes the fabric; the model is representative.

18. Quick Revision

Deadlock avoidance. Per-channel flow control (Chapter 14.2) stops any buffer overflowing but not the channels freezing together. Deadlock is a cycle of waits — channel A waits on B, B waits on A — and no buffering prevents it; only an acyclic dependency graph does. CHI keeps the graph acyclic with the drain rule: responses and data must always be sinkable — a node must accept an incoming response/data flit unconditionally, from a pre-allocated buffer, without issuing a request or holding a request credit. Requests may depend on responses draining (that wait resolves, because responses always drain), but a response must never depend on a request — a one-directional dependency with no back-edge, hence no cycle. The failure to avoid: gating response acceptance on request issue (e.g. sink_resp depends on req_credit). That adds the forbidden response→request edge, so under congestion the request and response channels wait on each other forever and the whole fabric deadlocks — unrecoverable, no timeout, only reset. Deadlock freedom is a property of the graph's shape: verify the forbidden edge is structurally absent, and never let a sink stall on a request. Representative model; 14.4 covers backpressure.

Coming Next

Chapter 14.4 — Backpressure. Deadlock avoidance keeps the fabric moving; backpressure is how it slows down gracefully when a node is busy. Chapter 14.4 covers backpressure — how a congested home node throttles upstream request nodes simply by withholding credit returns, why this stalls senders instead of dropping flits, and why a sender must wait under backpressure rather than drop or aggressively retry.