Where the register goes: retiming by hand

Moving a register across logic

Retiming moves registers through combinational logic without changing what the circuit computes. Move a register backward across an operator, and it becomes one register on each input of that operator. Move registers on every input of an operator forward, and they merge into one register on its output.

The test is simple: every path from an input to the output must cross the same number of registers as before. In the chain, a, b and c each pass through two registers. When the cut moves back across the final add, c needs its own register, c_q. Measured: leave c_q out of cut B and the bench finds no latency that matches.

The best cut balances the two stages. It rarely falls between two operators, because operators differ in depth. Here it sits inside the multiply, where the constant 11 splits into 8 and 3. Cut D costs 14 flops more than cut A and takes 8 levels off.

A loop cannot be cut

An accumulator adds each input into its own register, so the adder and the register form a loop. A register before the adder is legal: the input path crosses one more register, so latency grows by one. A register inside the loop changes the function. The sum then takes two edges to come round, so the circuit keeps two sums that take turns.

x_q <= x;
acc <= acc + x_q;

s_q <= acc + x;
acc <= s_q;

So a loop sets a floor that pipelining cannot lower. In R4.5 the MAC stopped at 35 levels, its accumulator's adder. To go lower you change the loop itself: a narrower accumulator, or a different way of adding.

The lab: move the cut

1. Run and measure the starter

   Run prints 202 cases at latency 2. Synthesize reports 26 flops and 29 levels.

2. Move the cut back after a + b

   Register s and c, then compute y from s_q and c_q. Run again: same lines, latency 2. Synthesize: 30 flops, 23 levels.

3. Try the cut after the multiply

   Register m and c instead. Still latency 2, but 26 levels: stage 1 is now the heavy one.

4. Split the multiply

   Register s, 3s and c; compute y as 8 times s_q plus t_q plus c_q. 40 flops, 21 levels.

Try it

Edge 2 takes (1, 2, 3) and y shows (1 + 2) * 11 + 3 = 36 one edge later, at edge 3. Each result appears on the line after its inputs: two registers.

Every legal cut prints these same lines. Only the flops, the cells and the levels in the Gates tab change.

`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 [7:0]  a = 0, b = 0, c = 0;
  logic [13:0] y;
  logic [13:0] want[1:4];                 // want[k]: the result for the inputs taken k - 1 edges ago
  bit   [4:1]  match = '1;                // match[k]: y has equaled want[k] at every edge so far
  int cases = 0, latency = 0;
  int unsigned seed = 7;
  bit quiet = 0;
  chain dut (.clk(clk), .rst_n(rst_n), .a(a), .b(b), .c(c), .y(y));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    for (int k = 4; k > 1; k--) want[k] = want[k-1];
    want[1] = (a + b) * 11 + c;             // the inputs this edge took
    if (edge_n >= 5) begin                  // compare once four edges of inputs are known
      cases++;
      for (int k = 1; k <= 4; k++) if (y !== want[k]) match[k] = 0;
    end
    if (!quiet) $display("e%0d a=%0d b=%0d c=%0d y=%0d", edge_n, a, b, c, y);
  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
    a = 1;   b = 2;   c = 3;   tick();
    a = 255; b = 255; c = 255; tick();
    a = 10;  b = 20;  c = 30;  tick();
    a = 0;   b = 0;   c = 0;   tick();
    tick();
    quiet = 1;                              // 200 more inputs from a fixed seed, checked but not printed
    for (int i = 0; i < 200; i++) begin
      seed = seed * 1103515245 + 12345;
      {a, b, c} = seed[31:8];
      tick();
    end
    for (int k = 4; k >= 1; k--) if (match[k]) latency = k;
    if (latency) $display("%0d cases, y matches the model at latency %0d", cases, latency);
    else         $display("%0d cases, y matches the model at no latency from 1 to 4", cases);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

module chain3 (input logic clk, rst_n, input logic [7:0] a, b, c, output logic [13:0] y);
  logic [8:0]  s_q;
  logic [7:0]  c_q;
  logic [13:0] r_q;
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin s_q <= '0; c_q <= '0; r_q <= '0; y <= '0; end
    else begin
      s_q <= 9'(a) + 9'(b);            // stage 1: the add
      c_q <= c;
      r_q <= 14'(s_q * 4'd11 + c_q);   // stage 2: the multiply and the second add
      y   <= r_q;                      // stage 3: a register added at the output
    end
endmodule
module tb;
  logic clk = 0, rst_n = 1;
  logic [7:0] a = 0, b = 0, c = 0;
  logic [13:0] y;
  int n = 0;
  chain3 dut (.clk(clk), .rst_n(rst_n), .a(a), .b(b), .c(c), .y(y));
  task automatic step(); #1 clk = 1; #1 clk = 0; n++; endtask
  initial begin
    #1 rst_n = 0; #1 rst_n = 1;
    a = 1; b = 2; c = 3; step();       // edge 1 takes the only nonzero input
    a = 0; b = 0; c = 0;
    while (y == 0) step();
    $display("y=%0d after edge %0d", y, n);
    $finish(0);
  end
endmodule

logic [7:0]  x_q;
logic [15:0] acc;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) begin x_q <= 0; acc <= 0; end
  else begin x_q <= x; acc <= acc + x_q; end
assign sum = acc;

logic [15:0] acc;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) begin acc <= 0; sum <= 0; end
  else begin acc <= acc + x; sum <= acc; end

logic [15:0] acc, s_q;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) begin s_q <= 0; acc <= 0; end
  else begin s_q <= acc + x; acc <= s_q; end
assign sum = acc;

logic [15:0] acc;
always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) acc <= 0;
  else        acc <= acc + x;
assign sum = acc;