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.

Both sides waiting for the otherThe looped version on the lab bench. The source is in SEND from edge 2 and the sink is EMPTY, yet valid and ready stay 0.
0123456clksrcSENDsnkEMPTYvalidready
  1. Cycle 0

    Edge 2: the source enters SEND. valid = send && ready, and ready is 0, so valid stays 0.

  2. Cycle 1

    ready = empty && valid, and valid is 0, so ready stays 0. Each value holds the other at 0.

  3. 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 and the two ways outArrows are combinational paths inside one clock cycle. A flop ends a path; the next cycle starts from it.
The loop and the two ways outArrows are combinational paths inside one clock cycle. A flop ends a path; the next cycle starts from it. flop src state flop: IDLE or SEND logic valid gate send && ready logic ready gate empty && valid flop snk state flop: EMPTY or FULL logic sink takes beat at the edge sendemptyvalidreadybeat
  1. The loop

    valid depends on ready and ready depends on valid in the same cycle. No flop sits on the circle, so its value has no clock to settle on.

  2. Source from state

    Write valid = send. The arrow from ready to the valid gate is gone; the circle is open. The source waits for ready at the edge, as the handshake rule asks.

  3. 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:

Measured. An earlier listing in the same report follows the loop through both modules: the AND in src, line 34, and the AND in snk, line 68.
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.22

Lint (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.

Four beats with valid and ready from stateThe source holds valid from edge 2. The sink is ready every other cycle.
validdatareadySourceSEND: four beatsSinkone-beat buffer

A lit wire carries a 1. A pill is a transfer in that cycle.

012345678clkvalidreadydata12341
  1. Cycle 0

    Cycle e2: both are 1. Beat 1 moves at edge 3.

  2. Cycle 1

    Cycle e3: the sink is FULL, so ready is 0. The source holds valid and data 2.

  3. Cycle 2

    Cycle e4: the consumer emptied the buffer at edge 4. Beat 2 moves at edge 5.

  4. 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 linesBeats on the benchCells (flops)Levels of logic
valid = send && ready, ready = empty && valid0 in 9 cyclesrefused: logic loop
valid = send, ready = empty (shipped)4, e3 to e917 (5)4
valid = send, ready = empty && valid4, e3 to e918 (5)5
valid = send, ready = empty || take, FULL stays FULL on a new beat4, e3 to e616 (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

Design brief
PortDirectionWidthMeaning
clkinput1clock
rst_ninput1reset, asynchronous, active-low
goinput1on go the source sends data 1 to 4
takeinput1the consumer takes a beat
validoutput1source has a beat; a beat moves at an edge where valid and ready are 1
readyoutput1sink can take a beat
dataoutput[7:0]the beat the source sends
gotoutput[7:0]the beat the sink got
Clock
rising edge
Reset
rst_n asynchronous, active-low: source IDLE, sink EMPTY
Corner cases
a consumer that does not take; back-to-back beats. Handshake: valid never depends on ready; 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
  1. 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.

  2. May ready depend on valid?

    The receiver may wait for valid before raising ready, but valid must never wait for ready. Whether ready may follow valid in the same cycle depends on the protocol: AXI forbids any combinational input-to-output path at an interface.

  3. Why does registering ready need a skid buffer?

    A registered ready is decided a cycle before the beat arrives. To keep full rate the sink must accept a beat in the cycle where it is dropping ready, 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".

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: 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 e9

Original 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

Predict the outputThe shipped link, but the consumer does not take any beat until 1 ns after edge 5; from then on it takes every beat. The program counts the beats and the edge where the last one moves. What does it print?
// A source and a sink joined by a valid/ready link. On go, the source sends four beats
// (data 1, 2, 3, 4). The sink holds one beat until its consumer takes it (take = 1).

// src: offers a beat while it is in SEND; the beat moves at an edge where valid and ready are 1.
module src (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       go,
  input  logic       ready,
  output logic       valid,
  output logic [7:0] data
);
  typedef enum logic {IDLE, SEND} state_e;
  state_e     st_q, st_d;
  logic [1:0] n_q;                          // beats already sent

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      st_q <= IDLE; n_q <= '0;
    end else begin
      st_q <= st_d;
      if (valid && ready) n_q <= n_q + 2'd1;
    end

  always_comb begin
    st_d = st_q;
    unique case (st_q)
      IDLE:    if (go) st_d = SEND;
      SEND:    if (valid && ready && n_q == 2'd3) st_d = IDLE;
      default: st_d = IDLE;
    endcase
  end

  assign valid = (st_q == SEND);            // from the state only
  assign data  = 8'(n_q) + 8'd1;
endmodule

// snk: a one-beat buffer. ready says "I have room"; take empties it.
module snk (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       valid,
  input  logic [7:0] data,
  input  logic       take,
  output logic       ready,
  output logic [7:0] got
);
  typedef enum logic {EMPTY, FULL} state_e;
  state_e st_q, st_d;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      st_q <= EMPTY; got <= '0;
    end else begin
      st_q <= st_d;
      if (valid && ready) got <= data;
    end

  always_comb begin
    st_d = st_q;
    unique case (st_q)
      EMPTY:   if (valid && ready) st_d = FULL;
      FULL:    if (take) st_d = EMPTY;
      default: st_d = EMPTY;
    endcase
  end

  assign ready = (st_q == EMPTY);           // from the state only
endmodule

module link (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       go,
  input  logic       take,
  output logic       valid,
  output logic       ready,
  output logic [7:0] data,
  output logic [7:0] got
);
  src u_src (.clk(clk), .rst_n(rst_n), .go(go), .ready(ready), .valid(valid), .data(data));
  snk u_snk (.clk(clk), .rst_n(rst_n), .valid(valid), .data(data), .take(take), .ready(ready), .got(got));
endmodule

`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 = 0;           // the consumer sleeps at first
  logic       valid, ready;
  logic [7:0] data, got;
  int         beats = 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 (valid && ready) begin beats++; last_beat = edge_n + 1; end   // this beat moves at the next edge
  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 (3) tick();                      // edges 3 to 5: take is 0
    take = 1;                               // from 1 ns after edge 5, take every beat
    repeat (8) tick();
    $display("%0d beats, the last at e%0d", beats, last_beat);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule
Spot the bugEach option is the pair of handshake lines of a one-module link: send is the source state, empty the sink state. The bench needs four beats in 13 cycles. Which pair fails?
ConceptWhich rule, kept by one side alone, is enough to make this loop impossible?
ConceptBoth simulators ran the looped design without an error and printed "0 beats". What does this show about combinational loops?
Read the waveformIn the measured trace of the shipped link, at which edge does beat 2 (data 2) move?
The shipped link
012345678validreadydata12341

One value per cycle, cycles e2 to e10 from the left. A beat in cycle k moves at edge k+1.

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 valid reads ready and ready reads valid in 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; drive valid from state. The house style drives ready from state too, which is one way to meet the AXI rule against combinational paths from an input to an output.
  • A ready from state halves the rate of a one-beat buffer; full rate needs a path from the consumer or a skid buffer (R4.4).