Difficulty: Hard · Puzzle 6 of 6 · Topic: FIFO, Arbitration and Credit Puzzles
Nodes A and B each have a queue that starts full of packets addressed to the other node. A packet may leave its queue only if the other node has a free slot at the start of the cycle; once moved, the destination consumes it immediately. (a) With queue depth 1 and with depth 2 and no reserved slot, how many packets are delivered? (b) Does doubling the depth fix it? (c) With one reserved slot per node that only incoming packets may use, what happens?
`timescale 1ns/1ns
// Two nodes, A and B. Each queue starts full of packets addressed to the other node.
// A packet leaves its queue only if the destination has a free slot at the start of the cycle
// (RESERVE = extra slots at the destination that only incoming packets of this kind may use).
// Once a packet is moved the destination consumes it immediately.
module node_pair #(parameter int DEPTH = 2, parameter int RESERVE = 0) (input bit clk);
int qa = DEPTH, qb = DEPTH;
int delivered = 0, stuck = 0, free_a, free_b, mv_ab, mv_ba;
bit reported = 0;
always @(posedge clk) begin
free_a = DEPTH - qa + RESERVE;
free_b = DEPTH - qb + RESERVE;
mv_ab = (qa > 0 && free_b > 0) ? 1 : 0;
mv_ba = (qb > 0 && free_a > 0) ? 1 : 0;
qa -= mv_ab;
qb -= mv_ba;
delivered += mv_ab + mv_ba;
if (mv_ab + mv_ba == 0 && (qa > 0 || qb > 0)) stuck++; else stuck = 0;
if (stuck == 3 && !reported) begin
reported = 1;
$display("DEADLOCK DEPTH=%0d RESERVE=%0d: queues hold %0d and %0d packets, nothing moves", DEPTH, RESERVE, qa, qb);
end
end
endmodule
module tb;
bit clk = 0;
always #5 clk = ~clk;
node_pair #(.DEPTH(1), .RESERVE(0)) d1(clk);
node_pair #(.DEPTH(2), .RESERVE(0)) d2(clk);
node_pair #(.DEPTH(1), .RESERVE(1)) e1(clk);
node_pair #(.DEPTH(2), .RESERVE(1)) e2(clk);
initial begin
#(10*10);
$display("DEPTH=1 RESERVE=0 : delivered=%0d", d1.delivered);
$display("DEPTH=2 RESERVE=0 : delivered=%0d", d2.delivered);
$display("DEPTH=1 RESERVE=1 : delivered=%0d", e1.delivered);
$display("DEPTH=2 RESERVE=1 : delivered=%0d", e2.delivered);
$finish;
end
endmoduleCheck what each node waits for, and whether anything can ever free a slot first.
1) A can move only if B has a free slot; B can move only if A has a free slot. Both queues are full, so both wait: circular wait, nothing moves.
2) Depth 1 and depth 2 behave the same: whatever the depth, both queues start full, so delivered=0 forever. More buffering only changes how many packets are stuck.
3) With a reserved slot per node, each node always has a place to put an incoming packet, so both move every cycle: all 2 x DEPTH packets are delivered (2 for depth 1, 4 for depth 2).
4) The reserved slot breaks the cycle: it is a resource that never depends on the other node's queue.Answer: (a) 0 delivered in both cases, (b) no, doubling the depth does not help, (c) with a reserved slot every packet gets through (2 for depth 1, 4 for depth 2).
Checked by running the code in Verilator 5; the printed output supports the answer above. The model with full queues deadlocks at any depth; a reserved slot lets every packet through.
'Make the buffers bigger' is the usual proposal and it fails: any finite buffer can be filled when the traffic pattern is cyclic. The deadlock also looks like silence in simulation (no assertion fires), and a random test that rarely fills both queues at once will not hit it.
Name two standard ways to remove this deadlock. Model answer: (1) Separate request and response queues (virtual channels) so a response can always drain, or give each side a reserved escape slot; (2) reserve space before sending (credits), so a packet is sent only when the destination has already promised room; (3) enforce an order in which resources are acquired so the dependency graph has no cycle. Any two of these answers it.