Depth, not effort

A path's delay is set mostly by how many logic levels the RTL puts between two registers. Synthesis resizes gates, buffers nets and re-maps logic, but it rarely changes the algorithm behind the RTL. So when a datapath misses timing, change its structure, not the tool effort.

Two forms of 32-bit addition show it. One uses the plain a + b operator; the other is a 5-level Kogge-Stone prefix adder. Both have registered inputs and outputs and are mapped with the same generic flow.

The prefix adder has about 40 % fewer levels and about 46 % more gates. It buys depth with area: that is the usual trade.

Plain + specifies the sum, not a ripple architecture. Synthesis can infer and restructure carry logic. An explicit prefix network expresses a candidate structure, but mapping can rewrite that too; compare both under the same target before replacing portable arithmetic.

Levers that shorten a path

Several levers shorten slow paths. The table lists each with its effect.

Kogge-Stone in five minutes

For one bit, g = a & b, p = a ^ b, and carry_out = g | (p & carry_in). For a high group H above a low group L, substitute the low carry equation into the high one: G = G_H | (P_H & G_L) and P = P_H & P_L. Group order matters: carry flows from low to high.

A prefix adder applies that combine step to all bits at once, doubling the reach each stage: distance 1, then 2, then 4. Trace a=0111 and b=0001 with carry-in 0. Each box holds the values after that stage. In the two distance rows, solid boxes are combine cells and dashed grey boxes just pass a value down.

Read the figure top to bottom: each row combines a column with the column one or two places to its right.

• Distance 1 combines neighbours: G[2:1]=0, P[2:1]=1 and G[1:0]=1.

• Distance 2 reuses those results: G[2:0]=G[2:1]|(P[2:1]&G[0])=0|(1&1)=1.

• Bit 0 reaches every carry through at most two combine cells, so the path to c4 is two cells deep, not three ripple stages.

• The sum row is p XOR the carry from the column to the right: 0110 XOR 1110 = 1000.

For 32 bits, distances 1,2,4,8,16 cover all lower bits: five stages instead of a 31-stage ripple.

Five prefix stages are not five mapped gate levels: each stage contains generate/propagate Boolean logic, followed by sum logic and mapping choices. The 38-level result counts the mapped graph, not abstract prefix stages. A timing-driven library flow may favor either implementation once routing and fanout are included.

Common mistakes

Testbench

The two adders, matching measurement tops, and a sampled functional checker. For the depth experiment, save only the design modules before tb_ks as design.sv; keep the testbench in a separate simulation source. Only the selected measurement top is synthesized. Simulation requires SystemVerilog with 1 ns / 1 ps timing.

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

`timescale 1ns/1ps
// The historical name is retained; '+' does not require ripple mapping.
module add32_ripple (input logic [31:0] a, b, output logic [32:0] y);
  assign y = a + b;
endmodule

// Kogge-Stone parallel-prefix adder: log2(32) = 5 prefix levels
module add32_ks (input logic [31:0] a, b, output logic [32:0] y);
  logic [31:0] g [6], p [6];
  assign g[0] = a & b;
  assign p[0] = a ^ b;
  for (genvar l = 0; l < 5; l++) begin : lvl
    localparam int D = 1 << l;
    for (genvar i = 0; i < 32; i++) begin : bit_i
      if (i >= D) begin : comb
        assign g[l+1][i] = g[l][i] | (p[l][i] & g[l][i-D]);
        assign p[l+1][i] = p[l][i] & p[l][i-D];
      end else begin : pass
        assign g[l+1][i] = g[l][i];
        assign p[l+1][i] = p[l][i];
      end
    end
  end
  logic [31:0] carry_in;
  assign carry_in = {g[5][30:0], 1'b0};            // carry into bit i = group generate of bits [i-1:0]
  assign y = {g[5][31], p[0] ^ carry_in};
endmodule

module reg32 (input logic clk, input logic [31:0] a, b, output logic [32:0] y);
  logic [32:0] r; logic [31:0] ra, rb;
  logic [32:0] s;
  add32_ks u (.a(ra), .b(rb), .y(s));
  always_ff @(posedge clk) begin ra <= a; rb <= b; r <= s; end
  assign y = r;
endmodule

module measure_plain (input logic clk, input logic [31:0] a, b, output logic [32:0] y);
  logic [31:0] ra, rb;
  logic [32:0] s;
  add32_ripple u (.a(ra), .b(rb), .y(s));
  always_ff @(posedge clk) begin ra <= a; rb <= b; y <= s; end
endmodule

module measure_prefix (input logic clk, input logic [31:0] a, b, output logic [32:0] y);
  reg32 u (.clk, .a, .b, .y);
endmodule

Related topics

• Setup and hold fundamentals

• Pipelining