Handshakes as FSMs
Code both sides of a valid/ready handshake as state machines, recognize the combinational loop that forms when each side waits for the other, and break it with state.
- Lesson
- R3.3
- Time
- 25 min
- Runs on
- Your browser
- Check
- 5 questions
A source offered a beat only when it saw ready, and its sink raised ready only when it saw valid. Each block passed its own tests. Joined, they formed a loop of logic with no flop in it: the simulation moved no beat at all, and the synthesizer refused the design.
- Cycle 0
Edge 2: the source enters SEND.
valid = send && ready, andreadyis 0, sovalidstays 0. - Cycle 1
ready = empty && valid, andvalidis 0, soreadystays 0. Each value holds the other at 0. - Cycle 6
After seven cycles nothing has moved. The run ends with "0 beats in 9 cycles".
Measured with Icarus, cycles e2 to e8. Verilator printed the same 0 beats.
A loop with no flop in it
A valid/ready handshake moves one beat at each rising edge where valid and ready are both 1. The source holds valid and the data until then; the sink raises ready when it can take a beat. Each side is a small state machine, and each side's handshake output is an output of its machine.
A combinational loop is a path of gates that leaves a signal and comes back to it with no flop on the way. Here valid feeds the AND that makes ready, and ready feeds the AND that makes valid. A loop with no inversion holds whatever it starts with, like a latch; with an inversion it oscillates. After reset this one started at 0, so it stayed at 0.
- The loop
validdepends onreadyandreadydepends onvalidin the same cycle. No flop sits on the circle, so its value has no clock to settle on. - Source from state
Write
valid = send. The arrow fromreadyto the valid gate is gone; the circle is open. The source waits forreadyat the edge, as the handshake rule asks. - Sink from state
Write
ready = empty. The sink promises room before it sees a beat. This is the shipped lab: both outputs come from flops.
Read the diagram as text
- src state: flop: IDLE or SEND
- valid gate: send && ready
- ready gate: empty && valid
- snk state: flop: EMPTY or FULL
- sink takes beat: at the edge
- src state → valid gate: send
- snk state → ready gate: empty
- valid gate → ready gate: valid
- ready gate → valid gate: ready
- valid gate → sink takes beat: beat
Opening either arrow breaks the loop. The house style opens both.
Each side waits for the other
// src
assign valid = (st_q == SEND) && ready;
// snk
assign ready = (st_q == EMPTY) && valid;
A loop: no beat moves, Lint warns, Synthesize refuses.
Both from state
// src
assign valid = (st_q == SEND);
// snk
assign ready = (st_q == EMPTY);
No loop: four beats move, one every two cycles.
What the tools say about the loop
Synthesize refuses the looped version. The check pass of Yosys 0.70 lists the gates and wires on the circle, after mapping:
found logic loop in module link:
cell $abc$187$blif$187$8 ($_ANDNOT_)
A[0] --> Y[0]
wire \ready source: main.sv:77.22
cell $abc$187$blif$187$7 ($_AND_)
B[0] --> Y[0]
wire \valid source: main.sv:76.22Lint (Verilator 5.052) warns on the same circle, by signal name: %Warning-UNOPTFLAT: main.sv:76:22: Signal unoptimizable: Circular combinational logic: 'valid'. Verilator checks whole signals, so it can also flag a circle that is not real bit by bit. The synthesizer's check follows single bits, so its loop is a real one.
The protocol rule prevents the loop by forbidding one arrow. The source's valid must not depend on the sink's ready; the sink may wait for valid before raising ready. The AXI specification goes further: no combinational path from any input of an interface to any output. An AXI sink that waits for valid raises ready a cycle later, from a flop.
What a ready from a flop costs
The shipped sink raises ready only when its buffer is empty. After it takes a beat it is FULL for one cycle, even though the consumer empties it at the very next edge. So the link moves one beat every two cycles.
A lit wire carries a 1. A pill is a transfer in that cycle.
- Cycle 0
Cycle e2: both are 1. Beat 1 moves at edge 3.
- Cycle 1
Cycle e3: the sink is FULL, so
readyis 0. The source holdsvalidand data 2. - Cycle 2
Cycle e4: the consumer emptied the buffer at edge 4. Beat 2 moves at edge 5.
- Cycle 6
Beat 4 moves at edge 9 and the source returns to IDLE.
Measured on the lab bench: "4 beats, e3 to e9".
| Handshake lines | Beats on the bench | Cells (flops) | Levels of logic |
|---|---|---|---|
valid = send && ready, ready = empty && valid | 0 in 9 cycles | refused: logic loop | |
valid = send, ready = empty (shipped) | 4, e3 to e9 | 17 (5) | 4 |
valid = send, ready = empty && valid | 4, e3 to e9 | 18 (5) | 5 |
valid = send, ready = empty || take, FULL stays FULL on a new beat | 4, e3 to e6 | 16 (5) | 4 |
Measured with Yosys 0.70 on this flow and on the lab bench. The last row reaches full rate through a path from take to ready.
The last row runs at one beat per cycle, but its ready now waits for the consumer's take in the same cycle. Chain a few such blocks and that path grows through all of them. The usual answer is a second buffer entry that catches the beat sent while ready falls: the skid buffer of R4.4.
The lab
| Port | Direction | Width | Meaning |
|---|---|---|---|
| clk | input | 1 | clock |
| rst_n | input | 1 | reset, asynchronous, active-low |
| go | input | 1 | on go the source sends data 1 to 4 |
| take | input | 1 | the consumer takes a beat |
| valid | output | 1 | source has a beat; a beat moves at an edge where valid and ready are 1 |
| ready | output | 1 | sink can take a beat |
| data | output | [7:0] | the beat the source sends |
| got | output | [7:0] | the beat the sink got |
- Clock
- rising edge
- Reset
rst_nasynchronous, active-low: source IDLE, sink EMPTY- Corner cases
- a consumer that does not take; back-to-back beats. Handshake:
validnever depends onready; both outputs come from state
Run the lab: four beats, at edges 3, 5, 7 and 9. Now paste the looped lines from the compare block into src and snk. Run: "0 beats in 9 cycles". Lint names valid; Synthesize refuses with the loop above. Put the source line back to valid = (st_q == SEND) and keep the looped sink line: the beats move again at the same edges.
Asked in interviews
What is a combinational loop, and how do tools find it?
A path of gates from a signal back to itself with no flop. Synthesis checks find it by walking the netlist bit by bit (Yosys
check); lint tools warn per signal (Verilator UNOPTFLAT). Timing analysis cannot time a path that has no end.May ready depend on valid?
The receiver may wait for
validbefore raisingready, butvalidmust never wait forready. Whetherreadymay followvalidin the same cycle depends on the protocol: AXI forbids any combinational input-to-output path at an interface.Why does registering ready need a skid buffer?
A registered
readyis decided a cycle before the beat arrives. To keep full rate the sink must accept a beat in the cycle where it is droppingready, so it needs a second entry to catch it. With one entry, the rate halves.
Try it
Each line shows a cycle after the edge it names. In every cycle where valid and ready are both 1 the line says when the beat moves. The sink alternates EMPTY and FULL, so beats move at every other edge.
With the looped lines both states still advance: the source enters SEND and the sink stays EMPTY. But valid and ready stay 0 in every cycle and the summary reads "0 beats in 9 cycles".
Synthesize the design to measure its cells and inspect the mapped gates.
e2 src=SEND snk=EMPTY valid=1 ready=1 data=1 beat moves at e3 e3 src=SEND snk=FULL valid=1 ready=0 data=2 e4 src=SEND snk=EMPTY valid=1 ready=1 data=2 beat moves at e5 e5 src=SEND snk=FULL valid=1 ready=0 data=3 e6 src=SEND snk=EMPTY valid=1 ready=1 data=3 beat moves at e7 e7 src=SEND snk=FULL valid=1 ready=0 data=4 e8 src=SEND snk=EMPTY valid=1 ready=1 data=4 beat moves at e9 e9 src=IDLE snk=FULL valid=0 ready=0 data=1 e10 src=IDLE snk=EMPTY valid=0 ready=1 data=1 4 beats, e3 to e9Original design · 17 cells · 5 flip-flops · 0 latches · 4 logic levels. Synthesis uses Yosys; counts depend on the toolchain.
Read included file: tb.sv
`timescale 1ns/1ps
module tb;
logic clk = 0;
always #5 clk = ~clk; // rising edges at 5, 15, 25, ...
logic rst_n = 1; // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
int edge_n = -1;
always @(posedge clk) edge_n = edge_n + 1;
logic go = 0, take = 1; // the consumer takes a held beat in every cycle
logic valid, ready;
logic [7:0] data, got;
int beats = 0, first = 0, last_beat = 0;
link dut (.clk(clk), .rst_n(rst_n), .go(go), .take(take), .valid(valid), .ready(ready), .data(data), .got(got));
// Advance to the next rising edge, wait for the design to settle, then print one line.
task automatic tick();
@(posedge clk); #1;
if (edge_n >= 2) begin
if (valid === 1'b1 && ready === 1'b1) begin // the beat moves at the next edge
beats++; last_beat = edge_n + 1;
if (first == 0) first = edge_n + 1;
$display("e%0d src=%s snk=%s valid=%b ready=%b data=%0d beat moves at e%0d", edge_n, dut.u_src.st_q ? "SEND" : "IDLE", dut.u_snk.st_q ? "FULL " : "EMPTY", valid, ready, data, edge_n + 1);
end else
$display("e%0d src=%s snk=%s valid=%b ready=%b data=%0d", edge_n, dut.u_src.st_q ? "SEND" : "IDLE", dut.u_snk.st_q ? "FULL " : "EMPTY", valid, ready, data);
end
endtask
initial begin
#1 rst_n = 0; tick(); tick(); rst_n = 1; // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
go = 1; tick(); go = 0; // go is sampled at edge 2
repeat (8) tick();
if (beats == 4) $display("4 beats, e%0d to e%0d", first, last_beat);
else $display("%0d beats in 9 cycles", beats);
$finish(0); // quiet: no "$finish called" line
end
endmodule
Check yourself
Remember
- A valid/ready beat moves at an edge where both are 1; each side is a state machine whose handshake output is one of its outputs.
- If
validreadsreadyandreadyreadsvalidin the same cycle, the two form a combinational loop: here a silent deadlock in simulation and a refused synthesis. - The source must never wait for
ready; drivevalidfrom state. The house style drivesreadyfrom state too, which is one way to meet the AXI rule against combinational paths from an input to an output. - A
readyfrom state halves the rate of a one-beat buffer; full rate needs a path from the consumer or a skid buffer (R4.4).