Multipliers, MACs and the long path

What a multiplier costs

A multiplier forms one partial product per bit of b: a copy of a, shifted, kept only where that bit of b is 1. Rows of adders then sum the partial products. An 8 x 8 multiplier has eight rows, and a 16 x 16 has sixteen rows of twice the width.

Two things stand out. The cells grow with the square of the width, because rows and row width both double. And on this flow an adder is nearly as deep as a multiplier of the same output width: a 16-bit adder is 30 levels, the 8 x 8 multiplier 30 too. The carry has to reach the top bit either way.

Sign is the other trap. A multiply is signed only when both operands are signed; one unsigned operand makes the whole operation unsigned. Then -3 is read as 253, and the upper half of the product comes out wrong.

Where the long path of a MAC runs

A multiply-accumulate unit (MAC) adds each product into a running sum, the accumulator. Its output feeds its own adder, so the adder and the accumulator form a loop. The question is which part of the circuit sets the levels. Ask the tool: Yosys's ltp names the cells on the longest path, and the Gates tab shows its length.

Why are 30 and 35 not 65? The low bits of the product are ready early, and the adder starts its carry on them while the high bits are still forming. Yosys builds the multiply and the add as one array, so the two depths overlap. Levels of a chain are measured, never added.

The lab: cut the MAC and measure

acc_valid <= in_valid;
if (in_valid)
  acc <= acc + AW'(a * b);

prod_q     <= a * b;
prod_valid <= in_valid;
acc_valid  <= prod_valid;
if (prod_valid)
  acc <= acc + AW'(prod_q);

Run the starter: five pairs, none wrong, final acc 65223, latency 1. Synthesize: 39 levels. Add prod_q and prod_valid as in the right panel and run again. The sums stay the same, the latency becomes 2, and the levels drop to 35. Measured: forget the valid pipe and four of the five sums are wrong.

Then set W to 16 and Synthesize both versions: 1696 cells and 69 levels in one stage, 1734 cells and 64 levels with the cut. The wider accumulator's loop again sets the count.

Try it

Each pair is multiplied and added at the edge that takes it: 12 at edge 2, 12 + 30 = 42 at edge 3, and 65123 after 255 x 255. The gap at edge 4 leaves the sum alone.

With the product register the same lines appear one edge later, the last line reads latency 2, and Synthesize reports 35 levels instead of 39.

`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;
  logic [19:0] acc;
  logic        acc_valid;
  logic [19:0] sum = 0;                   // the model: the running sum, 20 bits like acc
  logic [19:0] want[$];                   // the sum the design should show for each pair taken
  int          took[$];                   // the edge that took each pair
  int pairs = 0, wrong = 0, latency = 0;
  task automatic send(input logic [7:0] x, input logic [7:0] y);
    in_valid = 1; a = x; b = y; tick();
  endtask
  task automatic idle();
    in_valid = 0; a = 0; b = 0; tick();
  endtask
  mac dut (.clk(clk), .rst_n(rst_n), .in_valid(in_valid), .a(a), .b(b), .acc(acc), .acc_valid(acc_valid));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (in_valid) begin sum = sum + a * b; want.push_back(sum); took.push_back(edge_n); end
    if (acc_valid) begin
      latency = edge_n - took.pop_front() + 1;
      if (acc !== want.pop_front()) wrong++;
      pairs++;
    end
    $display("e%0d in_valid=%b a=%0d b=%0d acc=%0d acc_valid=%b", edge_n, in_valid, a, b, acc, acc_valid);
  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
    send(3, 4); send(5, 6); idle(); send(7, 8); send(255, 255); send(10, 10);
    idle(); idle(); idle();
    $display("%0d pairs, %0d wrong, final acc=%0d, latency %0d", pairs, wrong, acc, latency);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

// mac: a multiply-accumulate unit. Each valid pair (a, b) adds a * b into acc.
module mac #(
  parameter int W  = 8,
  parameter int AW = 2*W + 4
) (
  input  logic          clk,
  input  logic          rst_n,
  input  logic          in_valid,
  input  logic [W-1:0]  a, b,
  output logic [AW-1:0] acc,
  output logic          acc_valid
);
  logic [2*W-1:0] prod_q;                // stage 1: the product, registered
  logic           prod_valid;            // ... and the valid bit that travels with it
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      prod_q     <= '0;
      prod_valid <= 1'b0;
      acc        <= '0;
      acc_valid  <= 1'b0;
    end else begin
      prod_q     <= a * b;                 // stage 1: multiply
      prod_valid <= in_valid;
      acc_valid  <= prod_valid;            // stage 2: accumulate
      if (prod_valid) acc <= acc + AW'(prod_q);
    end
endmodule
module tb;
  logic clk = 0, rst_n = 1, in_valid = 0;
  logic [7:0] a = 0, b = 0;
  logic [19:0] acc;
  logic acc_valid;
  mac dut (.clk(clk), .rst_n(rst_n), .in_valid(in_valid), .a(a), .b(b), .acc(acc), .acc_valid(acc_valid));
  task automatic step(); #1 clk = 1; #1 clk = 0; endtask
  initial begin
    #1 rst_n = 0;                 // reset pulse: acc = 0
    #1 rst_n = 1;
    in_valid = 1;
    a = 2; b = 3; step();     // edge 1 captures (2, 3)
    a = 4; b = 5; step();     // edge 2 captures (4, 5)
    a = 6; b = 7; step();     // edge 3 captures (6, 7)
    $display("acc=%0d", acc);
    $finish(0);
  end
endmodule

logic signed [7:0] sa, sb;
assign sa = a;
assign sb = b;
assign p = sa * sb;

assign p = {{8{a[7]}}, a} * {{8{b[7]}}, b};

assign p = $signed(a) * b;

assign p = $signed(a) * $signed(b);