A block that needs three times its budget

The peak-sum block adds the largest of eight 16-bit lanes to a running 24-bit total, every cycle. Its first version has a longest path of 119 logic levels. The budget for this example is 38 levels, so the path is more than three times too long.

Four steps bring it inside the budget. Each one was measured, each one costs something, and the last one exists because the third ran into a feedback loop.

Read the top chart against the dashed line; read the bottom chart as the bill for each step.

• Step 2 removes 46 levels and costs no flops: it is the same function in a different shape.

• Step 3 halves the path again but adds 16 flops and one cycle of latency.

• Step 4 gains only 3 levels, yet it is the one that crosses the line. It adds 17 flops and another cycle.

How depth is measured here

There is no timing library in this experiment, so the measure is logic levels: the number of generic gates (AND, OR, XOR, MUX, NOT) on the longest path between two flops. Each version is synthesised and the longest path is reported by Yosys:

$ yosys -p "read_verilog -sv design.sv; synth -flatten -noabc -top peak_v1; abc -g AND,OR,XOR,MUX; opt_clean; stat; ltp -noff"
...
     1122 cells
      360   $_AND_
      152   $_DFF_PN0_
...
Longest topological path in peak_v1 (length=119):
    0: \x_q [26]
    1: $abc$2518$new_n220 (via $abc$2518$auto$blifparse.cc:397:parse_blif$2562)
...
  119: $auto$alumacc.cc:548:replace_alu$143.Y [23] (via $abc$2518$auto$blifparse.cc:397:parse_blif$3462)
   ff: \acc [23] (via $auto$ff.cc:337:slice$505)

• length=119 is the depth: 119 gates in series.

• 0: \x_q [26] is where the path starts: bit 26 of the input register, which is lane 1.

• ff: \acc [23] is where it ends: the top bit of the total. The path runs through the compare chain and then the whole carry of the adder.

• $_DFF_PN0_ counts the flops: 128 for the lanes plus 24 for the total.

Logic levels are not nanoseconds. To connect them to timing, this lesson uses one assumption throughout: 0.05 ns per generic level, including wire (an assumption for this example, not a library figure). The clock is 2.5 ns, with 0.4 ns clock-to-Q and 0.2 ns setup, which leaves 1.9 ns, or 38 levels.

Step 1 and 2: a tree instead of a chain

The baseline finds the maximum the way a loop in software does: compare lane 1 with lane 0, then lane 2 with that result, and so on. Each compare waits for the one before it.

1
2
3
4

// snippet: step 1, from peak_v1 below
for (genvar i = 1; i < 8; i++) begin : g_chain
  assign c[i] = (x_q[i*16 +: 16] > c[i-1]) ? x_q[i*16 +: 16] : c[i-1];
end

The tree compares pairs instead: four compares at once, then two, then one. Maximum is associative, so the result is the same; only the shape changes.

1
2
3
4
5

// snippet: step 2, the max8_tree module below
for (genvar i = 0; i < 4; i++) begin : g_l1   // level 1: four pairs
  assign l1[i] = (x[(2*i+1)*16 +: 16] > x[(2*i)*16 +: 16]) ? x[(2*i+1)*16 +: 16] : x[(2*i)*16 +: 16];
end
// level 2: two pairs, level 3: one

Read each drawing from the lanes on the left to the total on the right.

• The chain puts seven compare-selects in series; the tree puts three.

• Measured, the depth falls from 119 to 73 levels. The tree has 1046 gates against 970 for the chain (cells minus flops): a little more logic for much less depth.

• The adder is still in the same cycle, so the path in step 2 is the tree plus the full carry of a 24-bit add.

Step 3: a register at the right cut

The natural cut is between the tree and the adder: one 16-bit register, m_q. The tree and the adder now sit in different cycles.

// snippet: step 3, from peak_v3 below
else begin x_q <= x;  m_q <= m;  acc <= acc + m_q; end

Longest topological path in peak_v3 (length=39):
    0: \acc [1]
...
   ff: \acc [23] (via $auto$ff.cc:337:slice$399)

The path now starts and ends at acc. It is the accumulator loop: the total goes through the adder and back into its own register. The tree stage, measured on its own, is 35 levels. The cut cost 16 flops and one cycle, and the block still misses by one level.

Adding another register does not help here. A register can split the tree stage, but the loop is acc <= acc + m_q: one adder and one register, and any register added inside it changes what the block computes (see Common mistakes). Retiming cannot move a register out of the loop either; see retiming mechanism.

Step 4: change the loop, not the pipeline

The fix is to make the loop itself shorter. Split the 24-bit total into two 12-bit halves. The low half adds the low 12 bits of m_q and puts its carry into a flop, c_q. The high half adds that carry one cycle later, together with the high bits of m_q, which wait one cycle in mh_q.

1
2
3
4
5
6

// snippet: step 4, from peak_v4 below
{c_q, lo} <= lo + m_q[11:0];               // low loop: carry out goes to a flop
mh_q <= m_q[15:12];                        // high bits of m wait one cycle for that carry
hi <= hi + 12'(mh_q) + 12'(c_q);           // high loop: carry in from the flop
lo_q <= lo;                                // line the low half up with the high half
assign acc = {hi, lo_q};

• Each loop still has one register. lo feeds lo, and hi feeds hi, so neither total changes meaning. The carry flop sits between the loops, not inside one.

• Every carry is counted once, one cycle late. That is why the high half and lo_q show the total one cycle after step 3.

• Measured: the split loop is 23 levels deep. The longest path is now the tree stage at 36, inside the budget.

• Cost: 17 flops (1 carry, 4 for mh_q, 12 for lo_q) and one more cycle of latency.

The bench below runs all four versions on 4000 cycles of directed and random lanes, and checks step 3 one cycle late and step 4 two cycles late against step 1.

The order to try fixes

Read it top to bottom; each step costs more than the one above it. Restructuring is free in latency, a register is not, and a loop change also changes how the result is presented. The patterns lesson has more restructurings, and the retiming decision guide covers when to let the tool move registers.

Common mistakes

Testbench

All versions plus a self-checking bench. To repeat the depth measurements, save the modules before tb_peak as design.sv and run the Yosys command above with each top.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

// Peak-sum block: each cycle, add the largest of eight 16-bit lanes to a 24-bit total.
// Every version registers its inputs in x_q, so each measured path starts and ends at a flop.

// Shared by steps 2 to 4: a balanced tree of compare-selects, 3 comparators deep.
module max8_tree (input logic [8*16-1:0] x, output logic [15:0] m);
  logic [3:0][15:0] l1;
  logic [1:0][15:0] l2;
  for (genvar i = 0; i < 4; i++) begin : g_l1   // level 1: four pairs
    assign l1[i] = (x[(2*i+1)*16 +: 16] > x[(2*i)*16 +: 16]) ? x[(2*i+1)*16 +: 16] : x[(2*i)*16 +: 16];
  end
  for (genvar i = 0; i < 2; i++) begin : g_l2   // level 2: two pairs
    assign l2[i] = (l1[2*i+1] > l1[2*i]) ? l1[2*i+1] : l1[2*i];
  end
  assign m = (l2[1] > l2[0]) ? l2[1] : l2[0];   // level 3
endmodule

// Step 1 (baseline): a chain of 7 compare-selects, then the accumulator add, in one cycle.
module peak_v1 (input logic clk, rst_n, input logic [8*16-1:0] x, output logic [23:0] acc);
  logic [8*16-1:0] x_q;
  logic [7:0][15:0] c;                          // c[i] = largest of lanes 0 to i
  assign c[0] = x_q[15:0];
  for (genvar i = 1; i < 8; i++) begin : g_chain
    assign c[i] = (x_q[i*16 +: 16] > c[i-1]) ? x_q[i*16 +: 16] : c[i-1];
  end
  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 + c[7]; end
endmodule

// Step 2: the same function with the tree. Same latency, same flops.
module peak_v2 (input logic clk, rst_n, input logic [8*16-1:0] x, output logic [23:0] acc);
  logic [8*16-1:0] x_q;
  logic [15:0] m;
  max8_tree u_max (.x(x_q), .m);
  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 + m; end
endmodule

// Step 3: a register between the tree and the accumulator. One more cycle of latency.
module peak_v3 (input logic clk, rst_n, input logic [8*16-1:0] x, output logic [23:0] acc);
  logic [8*16-1:0] x_q;
  logic [15:0] m, m_q;
  max8_tree u_max (.x(x_q), .m);
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin x_q <= '0; m_q <= '0; acc <= '0; end
    else        begin x_q <= x;  m_q <= m;  acc <= acc + m_q; end
endmodule

// Step 4: split the accumulator loop into two 12-bit loops joined by a registered carry.
// Each loop still has exactly one register; the total appears one cycle later than in step 3.
module peak_v4 (input logic clk, rst_n, input logic [8*16-1:0] x, output logic [23:0] acc);
  logic [8*16-1:0] x_q;
  logic [15:0] m, m_q;
  logic [11:0] lo, lo_q, hi;
  logic [3:0]  mh_q;
  logic        c_q;
  max8_tree u_max (.x(x_q), .m);
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      x_q <= '0; m_q <= '0; lo <= '0; c_q <= 1'b0; mh_q <= '0; hi <= '0; lo_q <= '0;
    end else begin
      x_q <= x;
      m_q <= m;
      {c_q, lo} <= lo + m_q[11:0];   // low loop: carry out goes to a flop
      mh_q <= m_q[15:12];            // high bits of m wait one cycle for that carry
      hi <= hi + 12'(mh_q) + 12'(c_q);   // high loop: carry in from the flop
      lo_q <= lo;                    // delay the low half to line up with the high half
    end
  assign acc = {hi, lo_q};
endmodule

// The mistake: a "pipeline" register inside the accumulator loop. Two registers now sit
// around the loop, so it keeps two interleaved totals instead of one.
module peak_bad (input logic clk, rst_n, input logic [8*16-1:0] x, output logic [23:0] acc);
  logic [8*16-1:0] x_q;
  logic [15:0] m, m_q;
  logic [23:0] s_q;
  max8_tree u_max (.x(x_q), .m);
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin x_q <= '0; m_q <= '0; s_q <= '0; acc <= '0; end
    else        begin x_q <= x;  m_q <= m;  s_q <= acc + m_q; acc <= s_q; end
endmodule

Related topics

• Mini project: close timing on a FIR filter

• Why RTL architecture dominates

• Throughput and latency