Arithmetic that fits

Two circuits for one function

With the divisor fixed at 3, every part of a divider that depends on the divisor becomes a constant. The synthesizer removes the constant logic and simplifies what is left. On this flow, 40 cells and 14 levels of logic remain: a function of the eight bits of a.

The multiply-and-shift computes the same function by a longer road. 171 is 128 + 32 + 8 + 2 + 1, so a * 171 is the sum of five shifted copies of a, at least 16 bits wide. Shifting right by 9 keeps the top bits. The synthesizer builds the sums it was given, 150 cells and 19 levels. It does not find the 40-cell circuit for the same function.

What an operator costs on this flow

Every row below is one small module, synthesized on this flow. Read the cells for area and the levels for depth; neither is a delay in nanoseconds.

Three rules follow from the table. Powers of two are free: dividing by 8 drops three bits, and multiplying by 4 adds two zero bits. A constant operand is the synthesizer's job, and here it beat the hand rewrite. A variable operand is where the cost lives: a / b is 202 cells and 70 levels, five times the constant divide.

Prove the rewrite, then measure it

1. Write the obvious operator

   Start from a / 3, the line a reader understands. Synthesize it and read cells and levels.

2. Change the algorithm only if it misses

   When the brief's budget is missed, change the method: a shift when the brief allows a power of two, a small look-up table, or a divider that takes several cycles.

3. Prove it for every input

   An 8-bit input has 256 values, so one bench run can try them all. For wider inputs, compare against a model with random and corner values.

4. Measure it again

   A proven rewrite can still be bigger. Keep it only if the count went down.

The proof matters as much as the count. (a * 85) >> 8 looks like the same trick, since 85 / 256 is also close to 1/3. It is wrong at a = 3, and the bench finds 85 wrong inputs out of 256.

This wrong version synthesizes to 91 cells: smaller than the right one, and still no use. Signed values need their own proof as well. For a signed -3, -3 / 2 is -1, because a divide rounds toward zero; -3 >>> 1 is -2, because an arithmetic shift rounds down.

Run the lab: both forms print 0 wrong of 256. Synthesize: 40 cells, 14 levels of logic on this flow. Change the default of FORM to 1 and synthesize again: 150 cells, 19 levels. Then put 85 and 8 into FORM 1 and run: 85 wrong, the first at a = 3. Last, try a / 8, which reports 0 cells, and a divisor b as a second input port.

Try it

The bench builds the design twice, once with each FORM, and drives both with the same a. The first six lines show the forms agreeing. The last two lines are the proof: each form against a / 3 for all 256 inputs, 0 wrong each.

Synthesize reads the default, FORM = 0: 40 cells, 14 levels. With FORM = 1 it reports 150 cells and 19 levels for the same function. Put 85 and 8 into FORM 1 and the bench prints FORM 1 (multiply-shift): 85 wrong of 256 and FORM 1 first wrong: a=3 q=0 want=1.

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic [7:0] a = 0;
  logic [7:0] q_div, q_mul;                // FORM 0 and FORM 1 of the same design
  int want, bad_div = 0, bad_mul = 0, first_div = -1, first_mul = -1;
  div3 #(.FORM(0)) u_div (.a(a), .q(q_div));
  div3 #(.FORM(1)) u_mul (.a(a), .q(q_mul));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    $display("e%0d a=%0d q_div=%0d q_mul=%0d want=%0d", edge_n, a, q_div, q_mul, a / 3);
  endtask
  initial begin
    // the first six inputs, one per edge, so you can watch the two forms side by side
    for (int i = 0; i < 6; i++) begin a = i; tick(); end
    // the proof: every 8-bit input, each form against a / 3 computed here
    for (int i = 0; i < 256; i++) begin
      a = i; #1;
      want = i / 3;
      if (q_div != want) begin bad_div++; if (first_div < 0) first_div = i; end
      if (q_mul != want) begin bad_mul++; if (first_mul < 0) first_mul = i; end
    end
    $display("FORM 0 (a / 3):         %0d wrong of 256", bad_div);
    $display("FORM 1 (multiply-shift): %0d wrong of 256", bad_mul);
    if (first_div >= 0) begin a = first_div; #1; $display("FORM 0 first wrong: a=%0d q=%0d want=%0d", a, q_div, a / 3); end
    if (first_mul >= 0) begin a = first_mul; #1; $display("FORM 1 first wrong: a=%0d q=%0d want=%0d", a, q_mul, a / 3); end
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

module tb;
  logic signed [7:0] x = -3;
  initial begin
    $display("%0d %0d", x / 2, x >>> 1);
    $finish(0);
  end
endmodule

(a * 171) >> 9

(a * 683) >> 11

(a * 342) >> 10

(a * 86) >> 8