Pipelining a datapath and the valid pipe

Cut a long path into balanced pipeline stages, read what the cut costs in flops and latency, and carry a valid bit through the same registers as the data.

Lesson: R4.3
Time: 30 min
Runs on: Your browser
Check: 5 questions

An adder tree was cut into two stages to meet a faster clock. The data took the new register, but the valid flag kept its one register from the old design. Valid now arrived one edge before its sum, and the consumer took every stale word as a result: five results, none right.

Two data stages, one valid registerFive inputs with gaps. in is the sum the bench expects for the inputs offered at that edge. out_valid rises one edge too early, every time.

Cycle 2
The first input, sum 10, is taken. out_valid is already 1, but sum still holds 0 from before. The consumer counts 0.
Cycle 3
sum shows 10 now, one edge late. The consumer pairs it with the second input and is wrong again.
Cycle 5
After the gap the same thing: valid marks 100, the previous sum. Each result is the one before it.
Cycle 9
The last input, 20, is counted with the word 1020. Five results, zero right.

Measured on the lab bench, one value per edge. The data went through two registers and valid through one.

Where to put the stage register

Pipelining splits a long combinational path into stages, with a register between each pair. Each stage is shorter, so the clock can be faster. Every stage adds one edge of latency, and one flop per bit that crosses the cut.

The adder tree from [R1.7](R1-7-parameters-generate-and-clog2.html), written out by hand for four inputs, has two levels of adders. Cut between them, and stage 1 holds an 8-bit adder while stage 2 holds a 9-bit one. Measured alone, those adders are 15 and 17 levels of logic on this flow.

Registers	Latency	Cells	Flops	Levels of logic on this flow
after the tree only	1	126	11	21
after each level of adders	2	149	30	17
on the inputs too	3	181	63	17

The tree with its valid pipe, measured with Yosys 0.70. The third register adds 33 flops and no speed: the 9-bit adder is still one stage.

The slowest stage sets the clock, so put the cut where the stages come out even. Here the stages hold adders of 15 and 17 levels, close to even. Registering the inputs as well makes a third stage with no logic in it. The count stays at 17, the stage that holds the 9-bit adder. A register helps only where it cuts the longest path.

Valid travels with the data

Data is half of a pipeline. Each stage also needs a valid bit that says whether its registers hold a real item. Valid goes through the same number of registers as the data, so it comes out on the same edge. That chain of valid registers is the valid pipe.

The two-stage tree with its valid pipeArrows carry data, left to right, one register per column. The bottom row is the valid pipe. The route that skips v1_q is the bug.

port (calls out)

An item enters
Edge k takes the inputs into stage 1 and in_valid into v1_q. Both describe the same item.
Follow the calls, values and waits
1. data sum 100: a, b, c, d → s01_q, s23_q
2. data valid 1: in_valid → v1_q
It moves together
Edge k+1 moves the pair sums into sum and v1_q into out_valid. The consumer sees the item and its valid on the same edge.
Follow the calls, values and waits
1. data sum 100: s01_q, s23_q → sum
2. data valid 1: v1_q → out_valid
A bubble
In a gap, in_valid is 0. The data registers still load whatever is on the inputs, and a valid 0 travels beside it. Nobody reads that word: it is a bubble.
Follow the calls, values and waits
1. data valid 0: in_valid → v1_q
2. data valid 0: v1_q → out_valid
The bug
With valid taking the short route, it reaches the consumer one edge before its sum. Each valid then marks the previous item's word.
Follow the calls, values and waits
1. data valid 1: in_valid → out_valid
2. data valid 1: out_valid → consumer

Read the diagram as text

a, b, c, d: inputs
in_valid: input
s01_q, s23_q: stage 1: a + b, c + d
v1_q: valid of stage 1
sum: stage 2: s01_q + s23_q
out_valid: valid of stage 2
consumer: reads sum when out_valid is 1

a, b, c, d → s01_q, s23_q: edge k
s01_q, s23_q → sum: edge k+1
sum → consumer: sum
in_valid → v1_q: edge k
v1_q → out_valid: edge k+1
out_valid → consumer: valid
in_valid → out_valid: the bug: one register

Anything that belongs to an item (an address, an opcode, a tag) rides in the same pipe, so it comes out beside its data.

Reset clears the valid bits and nothing else. A word under a 0 valid is never read, so the data registers can go without reset. Yosys maps them to $_DFF_P_, a flop with no reset pin. In the lab they start as x, and nothing reads them until valid says so.

The same inputs through the valid pipeWith v1_q added, out_valid follows in_valid by two edges, exactly like the sums.

Cycle 3
The input of edge 2 comes out with its valid: sum 10.
Cycle 5
The gap at edge 4 arrives as a bubble: out_valid 0 while sum holds a stale 100.
Cycle 10
The last input, 20, comes out at edge 10. Five results, five right.

Measured on the lab bench with the fix. The data lines are the same as before; only out_valid moved.

Build the valid pipe

Valid with one register

always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) out_valid <= 1'b0;
  else        out_valid <= in_valid;

One edge ahead of a two-stage sum. 5 results, 0 right.

Valid through every stage

logic v1_q;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) begin v1_q <= 1'b0; out_valid <= 1'b0; end
  else begin
    v1_q      <= in_valid;   // stage 1
    out_valid <= v1_q;       // stage 2
  end

Two registers, like the data. 5 results, 5 right; one more flop (30).

Design brief

Port	Direction	Width	Meaning
clk	input	1	clock
rst_n	input	1	reset, asynchronous, active-low
in_valid	input	1	a, b, c and d are taken this cycle
a, b, c, d	input	[7:0]	the operands
out_valid	output	1	marks each result
sum	output	[9:0]	for every input taken with in_valid = 1, one result sum = a + b + c + d, in order

Reset: clears the valid pipe only; data registers have no reset
Latency: two edges: stage 1 the pair sums, stage 2 the final sum
Corner cases: gaps of one and two cycles; back-to-back inputs; every input at 255

The lab ships the two-stage tree with the single valid register. Run it: 5 results, 0 right. Add v1_q as in the right panel and run again: 5 results, 5 right. Synthesize: 149 cells, 30 flops, 17 levels. Then try a third stage that registers the inputs: 63 flops and still 17 levels.

Asked in interviews

What does pipelining buy, and what does it cost?
It shortens the longest path, so the clock can be faster, and keeps one result per cycle. It costs one edge of latency per stage and a flop for every bit that crosses each cut. The slowest stage sets the clock, so the cuts should balance the stages.
Why does valid travel with the data?
Valid says whether the word in a stage is a real item. If it goes through a different number of registers, it marks the wrong word. Anything that describes the item, such as a tag or an address, rides in the same pipe.
What does reset need to clear in a pipeline?
The valid bits. A word under a 0 valid is never read, so the data registers may go without reset. The control state must be reset; the data can wait for its first real item.

Try it

Each line shows the input offered at that edge (in, the sum it should produce) and the output right after the edge. out_valid copies in_valid with one edge of delay, while sum takes two. So every valid word is the sum of the item before: 0, 10, 100, 400, 1020.

Add v1_q and run again. Now out_valid is 1 at e3, e4, e6, e9 and e10, the sums there are 10, 100, 400, 1020 and 20, and the last line reads 5 results, 5 right.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service

Edit the design, then Run, Lint or Synthesize

Expected: e0 in_valid=0 in=0 out_valid=0 sum=x e1 in_valid=0 in=0 out_valid=0 sum=0 e2 in_valid=1 in=10 out_valid=1 sum=0 e3 in_valid=1 in=100 out_valid=1 sum=10 e4 in_valid=0 in=100 out_valid=0 sum=100 e5 in_valid=1 in=400 out_valid=1 sum=100 e6 in_valid=0 in=400 out_valid=0 sum=400 e7 in_valid=0 in=400 out_valid=0 sum=400 e8 in_valid=1 in=1020 out_valid=1 sum=400 e9 in_valid=1 in=20 out_valid=1 sum=1020 e10 in_valid=0 in=20 out_valid=0 sum=20 e11 in_valid=0 in=20 out_valid=0 sum=20 e12 in_valid=0 in=20 out_valid=0 sum=20 5 inputs, 5 results, 0 right

Original design · 148 cells · 29 flip-flops · 0 latches · 17 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Original example source

// add4_pipe: the four-input adder tree in two stages, with a valid flag.
module add4_pipe (
  input  logic       clk,
  input  logic       rst_n,
  input  logic       in_valid,
  input  logic [7:0] a, b, c, d,
  output logic       out_valid,
  output logic [9:0] sum
);
  // Data: two stages. No reset: a word is read only when its valid is 1.
  logic [8:0] s01_q, s23_q;
  always_ff @(posedge clk) begin
    s01_q <= a + b;                    // stage 1: two pair sums
    s23_q <= c + d;
    sum   <= s01_q + s23_q;            // stage 2: the final sum
  end
  // Valid: still the single register of the one-stage design.
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) out_valid <= 1'b0;
    else        out_valid <= in_valid;
endmodule

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       in_valid = 0;
  logic [7:0] a = 0, b = 0, c = 0, d = 0;
  logic       out_valid;
  logic [9:0] sum;
  int want[$];                            // the model: sums of the valid inputs, oldest first
  int results = 0, right = 0;
  // Offer one input set with in_valid = 1 before the next edge.
  task automatic item(input int w, input int x, input int y, input int z);
    in_valid = 1; a = w; b = x; c = y; d = z;
    want.push_back(w + x + y + z);
    tick();
    in_valid = 0;                         // the inputs keep their old values in a gap
  endtask
  add4_pipe dut (.clk(clk), .rst_n(rst_n), .in_valid(in_valid), .a(a), .b(b), .c(c), .d(d),
                 .out_valid(out_valid), .sum(sum));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (out_valid) begin                  // the consumer counts every word marked valid
      results++;
      if (want.size() > 0 && sum === want[0]) right++;
      if (want.size() > 0) void'(want.pop_front());
    end
    $display("e%0d in_valid=%b in=%0d out_valid=%b sum=%0d", edge_n, in_valid, int'(a) + b + c + d, out_valid, sum);
  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
    item(1, 2, 3, 4);                     // e2
    item(10, 20, 30, 40);                 // e3
    tick();                               // e4: a gap
    item(100, 100, 100, 100);             // e5
    repeat (2) tick();                    // e6, e7: a gap
    item(255, 255, 255, 255);             // e8
    item(5, 5, 5, 5);                     // e9
    repeat (3) tick();                    // e10-e12: let the pipe drain
    $display("5 inputs, %0d results, %0d right", results, right);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

Predict the outputvpipe is a valid pipe of two registers. The bench sets in_valid before each of edges 1 to 6 from the pattern 1, 1, 0, 1, 0, 0, and prints the edges after which out_valid is 1. What is the output line?

module vpipe (input logic clk, rst_n, in_valid, output logic out_valid);
  logic v1_q;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin v1_q <= 1'b0; out_valid <= 1'b0; end
    else        begin v1_q <= in_valid; out_valid <= v1_q; end
endmodule
module tb;
  logic clk = 0, rst_n = 1, in_valid = 0, out_valid;
  logic [1:6] pattern = 6'b110100;               // in_valid before edges 1 to 6, left to right
  vpipe dut (.clk(clk), .rst_n(rst_n), .in_valid(in_valid), .out_valid(out_valid));
  initial begin
    #1 rst_n = 0; #1 rst_n = 1;
    $write("out_valid at");
    for (int e = 1; e <= 6; e++) begin
      in_valid = pattern[e];
      #1 clk = 1; #1 clk = 0;                      // edge e
      if (out_valid) $write(" e%0d", e);
    end
    $display("");
    $finish(0);
  end
endmodule

Spot the bugEach option is the valid logic of the two-stage adder tree. The bench sends five inputs with gaps and checks that each valid word is the right sum. Which option fails?

logic [1:0] vp;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) vp <= '0;
  else        vp <= {vp[0], in_valid};
assign out_valid = vp[1];

logic v1_q;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) begin v1_q <= 1'b0; out_valid <= 1'b0; end
  else        begin v1_q <= in_valid; out_valid <= v1_q; end

always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) out_valid <= 1'b0;
  else        out_valid <= in_valid;

logic v1_q;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) v1_q <= 1'b0; else v1_q <= in_valid;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) out_valid <= 1'b0; else out_valid <= v1_q;

ConceptA path has 30 levels of logic between two registers, and you may add one register inside it. Where should it go?

Right before the second register, so the result is stored soonerAnywhere: each register on the path takes the same number of levels offRight after the first register, so the new value starts earlyWhere the levels on its two sides come out about equal

ConceptIn a pipeline whose stages each have a valid bit, which registers must reset clear?

The valid bits; data under a 0 valid is never readOnly the last stage, because only it drives the outputsNone: the first real input flushes the pipe within a few edgesEvery register, data and valid, so the outputs start at 0

Read the waveformThis is the fixed pipeline. At edge 5, out_valid is 0 and sum is 100. What does that cycle show?

The two-stage tree with its valid pipe

One value per edge from edge 0, printed after each edge settles.

A reset: out_valid was cleared and sum kept its value from the edge beforeA bubble: the gap at edge 4 has reached the output, and the stale 100 is ignoredA stall: the pipe holds 100 because the consumer was not ready at this edgeA lost result: the sum 100 should have been counted a second time by the consumer

Remember

Pipelining puts registers inside a long path: shorter stages and a faster clock, at one edge of latency per stage and one flop per bit per cut.
The slowest stage sets the clock, so cut where the stages balance; a register that does not cut the longest path buys nothing (63 flops, still 17 levels).
Valid goes through the same registers as the data, and so does anything else that describes the item.
Reset clears the valid bits; data registers can go without reset, because a word under a 0 valid is never read.