Pipelining a Wide Adder

Module 5 introduced the general pipelining pattern: a register between combinational stages, trading latency for throughput. This article is the specific case where you actually need it most often, a 64-bit adder whose carry chain cannot settle inside one clock period at the frequency you are targeting.

You know from Module 2 why this happens. The carry ripples, or at best resolves through a lookahead tree, and either way there is real gate delay between the inputs and a trustworthy output. The fix this time is not a faster adder architecture. It is breaking the one adder into two half-width adders separated by a pipeline register, so the timing tool only has to close half the carry chain per cycle.

The wrong way to split an adder

A first instinct is to register the operands halfway and run two 32-bit adds:

// WRONG: this does not add the two halves correctly across cycles
always @(posedge clk) begin
    a_hi_reg <= a[63:32];
    b_hi_reg <= b[63:32];
    sum_lo   <= a[31:0] + b[31:0];   // lower half computed this cycle
end

always @(posedge clk) begin
    sum_hi <= a_hi_reg + b_hi_reg;   // upper half computed next cycle, but where is the carry?
end

The upper half needs the carry-out of the lower half. That carry is produced at the end of the first stage, and by the time the second stage runs it has to be sitting in a register, ready to be the carry-in of the upper adder. The code above never captures it. This “pipelined” adder produces the wrong sum on every input where the lower half carries out.

The correct split: register the carry, not only the operands

`timescale 1ns / 1ps
`default_nettype none

module pipelined_adder_64 (
    input  wire        clk,
    input  wire [63:0] a, b,
    output reg  [63:0] sum,
    output reg         cout
);
    // Stage 1: compute the lower 32 bits AND capture the carry it produces
    reg [31:0] sum_lo_reg;
    reg        carry_reg;
    reg [63:32] a_hi_reg, b_hi_reg;

    always @(posedge clk) begin
        {carry_reg, sum_lo_reg} <= a[31:0] + b[31:0];
        a_hi_reg <= a[63:32];
        b_hi_reg <= b[63:32];
    end

    // Stage 2: add the upper 32 bits, using the REGISTERED carry from stage 1
    always @(posedge clk) begin
        {cout, sum[63:32]} <= a_hi_reg + b_hi_reg + carry_reg;
        sum[31:0] <= sum_lo_reg;   // the lower sum rides along unchanged, to stay aligned
    end
endmodule

Two things do the real work. carry_reg is captured in the same pipeline register as sum_lo_reg: the carry out of the lower half is a piece of data that has to cross the boundary like the sum bits do. And sum_lo_reg rides through the second stage unchanged, purely to stay time-aligned with sum[63:32], which is ready one cycle later. Miss that and you assemble a sum whose two halves came from different additions.

Why this buys speed

Each stage now only has to close timing on a 32-bit carry chain instead of a 64-bit one. If the chain’s delay scales roughly with width (true for ripple, and true in a softer sense for lookahead structures once wiring and fan-out are counted), halving the width comes close to halving the worst-case delay in the stage. That is the headroom that lets you raise the clock, at the cost of the result arriving one cycle later than an unpipelined add would deliver it.

This is the throughput-versus-latency trade from Module 5 applied to one common piece of hardware. Any adder wide enough for its carry chain to be the critical path is a candidate for this split, and nothing stops you splitting it further: a 64-bit adder can become four pipelined 16-bit stages, each carry captured and passed forward the same way. Server-class ALUs do exactly this, typically with a prefix adder inside each stage rather than the plain ripple shown here.

Practice Exercise

Extend the pipelined adder from a 2-stage, 32+32 split into a 4-stage, 16+16+16+16 split. Write a testbench that applies an addition whose carry has to propagate from bit 0 to bit 63, and confirm the correct sum appears exactly 4 cycles after the inputs.

`timescale 1ns / 1ps
`default_nettype none

module pipelined_adder_64_4stage (
    input  wire        clk,
    input  wire [63:0] a, b,
    output reg  [63:0] sum,
    output reg         cout
);
    // Stage 1 registers
    reg [15:0] s1_sum0;            reg s1_c;
    reg [47:0] s1_a_rest, s1_b_rest;
    // Stage 2 registers
    reg [31:0] s2_sum;             reg s2_c;
    reg [31:0] s2_a_rest, s2_b_rest;
    // Stage 3 registers
    reg [47:0] s3_sum;             reg s3_c;
    reg [15:0] s3_a_rest, s3_b_rest;

    always @(posedge clk) begin
        // Stage 1: bits [15:0]
        {s1_c, s1_sum0} <= a[15:0] + b[15:0];
        s1_a_rest <= a[63:16]; s1_b_rest <= b[63:16];

        // Stage 2: bits [31:16]
        {s2_c, s2_sum[31:16]} <= s1_a_rest[15:0] + s1_b_rest[15:0] + s1_c;
        s2_sum[15:0] <= s1_sum0;
        s2_a_rest <= s1_a_rest[47:16]; s2_b_rest <= s1_b_rest[47:16];

        // Stage 3: bits [47:32]
        {s3_c, s3_sum[47:32]} <= s2_a_rest[15:0] + s2_b_rest[15:0] + s2_c;
        s3_sum[31:0] <= s2_sum;
        s3_a_rest <= s2_a_rest[31:16]; s3_b_rest <= s2_b_rest[31:16];

        // Stage 4: bits [63:48]
        {cout, sum[63:48]} <= s3_a_rest + s3_b_rest + s3_c;
        sum[47:0] <= s3_sum;
    end
endmodule

Pipelining a wide adder is more than registering the operands at the midpoint. The carry out of the earlier stage must be captured and fed forward as the carry in of the later one, and every already-computed sum bit must ride along so the halves stay aligned. Get the carry wrong and the adder is right on most inputs and wrong on exactly the ones that carry across the cut. In the next article we apply the same discipline to something with a much longer critical path to begin with, a multiplier.