Source

Index

# Signed Integer Divider (Truncating Long Division)

Computes the signed Quotient and Remainder of the signed Numerator and Denominator, using truncating long division, which matches the behaviour of most programming languages and manual long division. For example, here are the expected values:

• 22 / 7 = 3 rem 1
• -22 / 7 = -3 rem -1
• 22 / -7 = -3 rem 1
• -22 / -7 = 3 rem -1
• 7 / 22 = 0 rem 7
• -7 / -22 = 0 rem -7
• -7 / 22 = 0 rem -7
• 7 / -22 = 0 rem 7
• 0 / 0 = -1 rem 0 (raises div_by_zero)
• 22 / 0 = -1 rem 22 (raises div_by_zero)
• -22 / 0 = 1 rem 22 (raises div_by_zero)

## Interface and Latency

Supports c-slowing to meet timing. This means the inputs and outputs contain multiple words: C_SLOW_RATIO words of WORD_WIDTH width. All inputs and outputs are concatenated vectors, in the same order. Note that outputs will change wildly during calculation and cannot be used until the outputs are signalled as valid.

Takes one cycle to load the inputs, plus C_SLOW_RATIO * WORD_WIDTH cycles to compute the results, but requires no multiplication or variable bit shifts or double-length registers, so scales better to large WORD_WIDTH. The inputs and outputs each use a conventional ready/valid handshake, and accept/give out one set of results per division.

## General Theory of Operation

Think of the numerator and denominator along a number line. Depending on their initial signs, the divider will add or subtract the denominator to/from the numerator as necessary to bring the numerator towards zero, and then increment or decrement the quotient (initially at zero) to reflect that change in the numerator and produce a quotient with the correct sign. No calculations of absolute values or sign corrections after the fact are necessary, which saves a lot of hardware.

The implementation refines this approach by subtracting multiples of the denominator, as in manual long division. Imagine aligning the LSB of the denominator to the MSB of the numerator and performing the addition or subtraction. If the operation result has the opposite sign, then the denominator is too big, so we shift the numerator right by 1 bit and try again. Thus, it takes WORD_WIDTH steps to try all possible denominator multiples.

In hardware, we do this by shifting the numerator bit-by-bit, MSB-first, into the remainder then adding/subtracting the denominator from the remainder, and storing back the new remainder result if the sign did not flip (meaning the shifted bits of the numerator were large enough). Whatever is left at the end is the remainder, with the correct sign.

Similarly, if the denominator could be added/subtracted from the remainder without a sign flip, we add or subtract the equivalent multiple of 1 to the quotient, else we add zero. So the quotient bits are computed MSB-first.

The remainder storage cannot be retimed into the calc_new_remainder logic, and so that adder carry-chain becomes a major part of the worst-case delay. The output of that adder and the new/old remainder sign comparison logic has a high fanout and forms the next major part of the critical path. There's nothing to optimize here, it's just placment/routing.

There is no problem meeting a 150 MHz timing constraint up to about 96 bits WORD_WIDTH. Past that, it's hard. Use the following settings:

• Synthesis: default, with retiming enabled, no_lc, no_srlextract, and resource_sharing off.
• Implementation: Use Performance_RefinePlacement strategy.

This has just barely met timing at 104 bits of WORD_WIDTH at 150 MHz, with a C_SLOW_RATIO of 3. Since the remainder logic can't retime, the C_SLOW_RATIO likely has little impact on cycle time, but it does allow simple multiplexing of the divider.

Last ditch option: pipeline the connections from the remainder logic to the quotient logic, including the "calculating" signal from the FSM. Then delay the output valid signal the same. This would break the high fanout path after the remainder adder, at the cost of some complication and a few extra cycles of computation while the quotient calculations complete.

`default_nettype none

module Divider_Integer_Signed
#(
parameter WORD_WIDTH    = 0,
parameter C_SLOW_RATIO  = 1, // Must be 1 or greater

// Don't set at instantiation, except in Vivado IPI
parameter TOTAL_WIDTH   = WORD_WIDTH * C_SLOW_RATIO
)
(
input  wire                             clock,

input  wire                             in_valid,
input  wire signed [TOTAL_WIDTH-1:0]    numerator,
input  wire signed [TOTAL_WIDTH-1:0]    denominator,

output reg                              out_valid,
output wire signed [TOTAL_WIDTH-1:0]    quotient,
output reg  signed [TOTAL_WIDTH-1:0]    remainder,
output reg         [C_SLOW_RATIO-1:0]   div_by_zero
);

`include "clog2_function.vh"

localparam WORD_ZERO    = {WORD_WIDTH{1'b0}};
localparam TOTAL_ZERO   = {TOTAL_WIDTH{1'b0}};
localparam C_SLOW_ZERO  = {C_SLOW_RATIO{1'b0}};

Begin with handshake ports idle, and locally computed outputs invalid.

initial begin
out_valid   = 1'b0;
remainder   = TOTAL_ZERO;
div_by_zero = C_SLOW_ZERO;
end

Common iteration counter used in multiple places

integer i;

Each division takes WORD_WIDTH steps (for each of the C_SLOW_RATIO inputs), from WORD_WIDTH-1 to 0, plus one step to initially load the numerator and denominator. Thus, we need some state bits later on to signal we can start stepping.

localparam STEPS_WIDTH      = clog2(WORD_WIDTH);
localparam STEPS_INITIAL    = WORD_WIDTH - 1;
localparam STEPS_ZERO       = {STEPS_WIDTH{1'b0}};
localparam STEPS_ONE        = {{STEPS_WIDTH-1{1'b0}},1'b1};

We also need to control the calculation step counter with a secondary c-slow counter so we step the calculation step counter only once all the c-slowed steps have happenned for each calculation step.

This approach consumes less hardware than c-slowing the step counter directly, and avoid the need to OR-reduce all the c-slowed step counter values to detect that all calculations have completed. We can also do it this way since all the c-slowed calculations have the exact same number of calculation steps.

This counter divides the total number of calculation steps by C_SLOW_RATIO, so we have to init with a value one greater, then reload the expected value so the count is done when equal to zero.

localparam C_SLOW_STEPS_WIDTH   = clog2(C_SLOW_RATIO) + 1;
localparam C_SLOW_STEPS_LOAD    = C_SLOW_RATIO - 1;
localparam C_SLOW_STEPS_INITIAL = C_SLOW_RATIO;
localparam C_SLOW_STEPS_ZERO    = {C_SLOW_STEPS_WIDTH{1'b0}};
localparam C_SLOW_STEPS_ONE     = {{C_SLOW_STEPS_WIDTH-1{1'b0}},1'b1};

We need one extra bit in the remainder since the shift left always happens, so the final result is shifted by one and we don't want to lose the MSB. The right subsets of this wider register are extracted further down.

localparam REMAINDER_WIDTH          = WORD_WIDTH + 1;
localparam REMAINDER_ZERO           = {REMAINDER_WIDTH{1'b0}};
localparam REMAINDER_ONES           = {REMAINDER_WIDTH{1'b1}};
localparam TOTAL_REMAINDER_WIDTH    = REMAINDER_WIDTH * C_SLOW_RATIO;
localparam TOTAL_REMAINDER_ZERO     = {TOTAL_REMAINDER_WIDTH{1'b0}};

The quotient is incremented/decremented by a power of 2, starting with the most significant bit, because we process the numerator MSB first, which makes the division proceed in steps of the largest possible multiple of the divisor at that point.

localparam QUOTIENT_INCREMENT_INITIAL       = {1'b1,{WORD_WIDTH-1{1'b0}}};
localparam TOTAL_QUOTIENT_INCREMENT_INITIAL = {C_SLOW_RATIO{QUOTIENT_INCREMENT_INITIAL}};

localparam SUB              = 1'b1;

localparam POSITIVE         = 1'b0;
localparam NEGATIVE         = 1'b1;

We denote state as two bits, with the following transitions:

INIT -> CALC -> DONE -> INIT

We don't handle the fourth, impossible case.

localparam                      STATE_WIDTH     = 2;
localparam [STATE_WIDTH-1:0]    STATE_INIT      = 'b00;
localparam [STATE_WIDTH-1:0]    STATE_CALC      = 'b10;
localparam [STATE_WIDTH-1:0]    STATE_DONE      = 'b11;
localparam [STATE_WIDTH-1:0]    STATE_ERROR     = 'b01; // Never reached

The running state bits, from which we derive the control outputs and the internal control signals.

reg  [STATE_WIDTH-1:0]  next_running_state  = STATE_INIT;
wire [STATE_WIDTH-1:0]  running_state;

Register
#(
.WORD_WIDTH     (STATE_WIDTH),
.RESET_VALUE    (STATE_INIT)
)
running_state_storage
(
.clock          (clock),
.clock_enable   (1'b1),
.clear          (1'b0),
.data_in        (next_running_state),
.data_out       (running_state)
);

Count down WORD_WIDTH calculation steps for the entire division. Ends up at (2**WORD_WIDTH)-1 (all ones) when done, but we don't test for that value, we just clear it back to the start value at the next calculation.

reg                     clear_calculation_step  = 1'b0;
reg                     do_calculation_step     = 1'b0;
wire [STEPS_WIDTH-1:0]  current_calculation_step;

Counter_Binary
#(
.WORD_WIDTH     (STEPS_WIDTH),
.INCREMENT      (STEPS_ONE),
.INITIAL_COUNT  (STEPS_INITIAL[STEPS_WIDTH-1:0])
)
calculation_steps
(
.clock          (clock),
.clear          (clear_calculation_step),
.up_down        (1'b1),         // 0/1 -> up/down
.run            (do_calculation_step),
.carry_in       (1'b0),
// verilator lint_off PINCONNECTEMPTY
.carry_out      (),
// verilator lint_on  PINCONNECTEMPTY
.count          (current_calculation_step)
);

Count down C_SLOW_RATIO steps for each calculation step for the entire division.

reg                     clear_c_slow_step  = 1'b0;
reg                     do_c_slow_step     = 1'b0;
wire [C_SLOW_STEPS_WIDTH-1:0]  current_c_slow_step;

Counter_Binary
#(
.WORD_WIDTH     (C_SLOW_STEPS_WIDTH),
.INCREMENT      (C_SLOW_STEPS_ONE),
.INITIAL_COUNT  (C_SLOW_STEPS_INITIAL[C_SLOW_STEPS_WIDTH-1:0])
)
c_slow_steps
(
.clock          (clock),
.clear          (clear_c_slow_step),
.up_down        (1'b1),         // 0/1 -> up/down
.run            (do_c_slow_step),
.carry_in       (1'b0),
// verilator lint_off PINCONNECTEMPTY
.carry_out      (),
// verilator lint_on  PINCONNECTEMPTY
.count          (current_c_slow_step)
);

Store the denominator. Never changes during division, so it simply loops around itself to output each c-slowed value in turn.

reg                     enable_denominator  = 1'b0;
wire [TOTAL_WIDTH-1:0]  all_denominators;

Register_Pipeline
#(
.WORD_WIDTH     (WORD_WIDTH),
.PIPE_DEPTH     (C_SLOW_RATIO),
// concatenation of each stage initial/reset value
.RESET_VALUES   (TOTAL_ZERO)
)
denominator_storage
(
.clock          (clock),
.clock_enable   (enable_denominator),
.clear          (1'b0),
.parallel_in    (denominator),
.parallel_out   (all_denominators),
);

Report if we tried to divide by zero for each denominator.

always @(*) begin
for (i=0; i < C_SLOW_RATIO; i=i+1) begin: per_denominator_div_by_zero
div_by_zero[i] = (all_denominators[WORD_WIDTH*i +: WORD_WIDTH] == WORD_ZERO);
end
end

Extract the initial sign of all the denominators. Many run-time decisions are based on it. No need for separate storage since the denominator never changes.

reg denominator_sign;

always @(*) begin
end

Store and left-shift-out the numerator (into the remainder). We load the numerator value shifted left by 1 during the load cycle as the next cycle is the first cycle of calculation, and we need all the data ready.

reg  enable_numerator = 1'b0;
wire [WORD_WIDTH-1:0] numerator_reg;
reg  numerator_msb    = 1'b0;

Register_Pipeline
#(
.WORD_WIDTH     (WORD_WIDTH),
.PIPE_DEPTH     (C_SLOW_RATIO),
.RESET_VALUES   (TOTAL_ZERO)
)
numerator_storage
(
.clock          (clock),
.clock_enable   (enable_numerator),
.clear          (1'b0),
.parallel_in    (numerator << 1),
// verilator lint_off PINCONNECTEMPTY
.parallel_out   (),
// verilator lint_on  PINCONNECTEMPTY
.pipe_in        (numerator_reg << 1),
.pipe_out       (numerator_reg)
);

always @(*) begin
numerator_msb = numerator_reg[WORD_WIDTH-1];
end

Store the initial sign of the numerators. Many run-time decisions are based on it. We also need the numerator signs at load time to properly initialize the remainders.

reg                     enable_numerator_sign   = 1'b0;
wire                    numerator_sign;

Extract the sign bit (last bit) from each numerator

always @(*) begin
for (i=0; i < C_SLOW_RATIO; i=i+1) begin: per_numerator_sign_bits
end
end

Register_Pipeline
#(
.WORD_WIDTH     (1),
.PIPE_DEPTH     (C_SLOW_RATIO),
// concatenation of each stage initial/reset value
.RESET_VALUES   (C_SLOW_ZERO)
)
numerator_sign_storage
(
.clock          (clock),
.clock_enable   (enable_numerator_sign),
.clear          (1'b0),
// verilator lint_off PINCONNECTEMPTY
.parallel_out   (),
// verilator lint_on  PINCONNECTEMPTY
.pipe_in        (numerator_sign),
.pipe_out       (numerator_sign)
);

Store the remainders. Initialized with a zero or -1 (to sign-extend the numerator) and the first MSB of the numerator (pre-shifted out at numerator load above). At each calculation step, gets loaded with either the new remainder or the existing remainder, both left-shifted by 1 with the LSB filled-in with the MSB of the numerator.

Must be 1 bit wider than the numerator, since the shift always happens and we don't want to lose the MSB on the last step. This means we use the last WORD_WIDTH bits as the remainder output, and the first WORD_WIDTH bits for the new remainder calculations.

reg                         enable_remainder    = 1'b0;
reg  [REMAINDER_WIDTH-1:0]  remainder_updated   = REMAINDER_ZERO;
// Since we get the output remainders from another port, the
// most-significant bit of this port is never used.
// verilator lint_off UNUSED
wire [REMAINDER_WIDTH-1:0]  remainder_now;
// verilator lint_on  UNUSED
reg  [TOTAL_REMAINDER_WIDTH-1:0] all_initial_remainders = TOTAL_REMAINDER_ZERO;
wire [TOTAL_REMAINDER_WIDTH-1:0] all_remainders;

Register_Pipeline
#(
.WORD_WIDTH     (REMAINDER_WIDTH),
.PIPE_DEPTH     (C_SLOW_RATIO),
.RESET_VALUES   (TOTAL_REMAINDER_ZERO)
)
remainder_storage
(
.clock          (clock),
.clock_enable   (enable_remainder),
.clear          (1'b0),
.parallel_in    (all_initial_remainders),
.parallel_out   (all_remainders),
.pipe_in        (remainder_updated),
.pipe_out       (remainder_now)
);

Split out the remainders for output (last WORD_WIDTH bits) and for calculation (first WORD_WIDTH bits). The output remainder is picked from each c-slowed copy.

reg [WORD_WIDTH-1:0] current_remainder = WORD_ZERO;

always @(*) begin
current_remainder = remainder_now[REMAINDER_WIDTH-2:0];

for (i=0; i < C_SLOW_RATIO; i=i+1) begin: per_remainder
remainder[WORD_WIDTH*i +: WORD_WIDTH] = all_remainders[(REMAINDER_WIDTH*i)+1 +: WORD_WIDTH];
end
end

Compute the new remainder: new_remainder = current_remainder +/- denominator_loaded, depending on the initial signs of the numerator and denominator.

wire [WORD_WIDTH-1:0]   new_remainder;

#(
.WORD_WIDTH     (WORD_WIDTH)
)
calc_new_remainder
(
.carry_in   (1'b0),
.A_in       (current_remainder),
.sum_out    (new_remainder),
// verilator lint_off PINCONNECTEMPTY
.carry_out      ()
// verilator lint_on  PINCONNECTEMPTY
);

We will need the signs of the current and new remainders. They affect what we add/sub into the quotient at each calculation step.

reg current_remainder_sign  = 1'b0;
reg new_remainder_sign      = 1'b0;

always @(*) begin
current_remainder_sign  = current_remainder[WORD_WIDTH-1];
new_remainder_sign      = new_remainder[WORD_WIDTH-1];
end

Store the quotient. Gets a multiple of 1 or zero added or subtracted to/from it at each step, depending on the sign of the result of the addition/subtraction of the denominator to/from the remainder, the current sign of the remainder, and the initial signs of the numerator and denominator. That logic is worked out further down.

reg                     enable_quotient     = 1'b0;
reg                     clear_quotient      = 1'b0;
wire [WORD_WIDTH-1:0]   new_quotient;
wire [WORD_WIDTH-1:0]   current_quotient;

Register_Pipeline
#(
.WORD_WIDTH     (WORD_WIDTH),
.PIPE_DEPTH     (C_SLOW_RATIO),
.RESET_VALUES   (TOTAL_ZERO)
)
quotient_storage
(
.clock          (clock),
.clock_enable   (enable_quotient),
.clear          (clear_quotient),
.parallel_in    (TOTAL_ZERO),
.parallel_out   (quotient),
.pipe_in        (new_quotient),
.pipe_out       (current_quotient)
);

Store the quotient increment which is added/subtracted to/from the quotient each time we could remove the denominator from the remainder. Shift it right by 1 each calculation step.

reg                     enable_quotient_increment   = 1'b0;
reg                     clear_quotient_increment    = 1'b0;
wire [WORD_WIDTH-1:0]   quotient_increment;

Register_Pipeline
#(
.WORD_WIDTH     (WORD_WIDTH),
.PIPE_DEPTH     (C_SLOW_RATIO),
.RESET_VALUES   (TOTAL_QUOTIENT_INCREMENT_INITIAL)
)
quotient_increment_storage
(
.clock          (clock),
.clock_enable   (enable_quotient_increment),
.clear          (clear_quotient_increment),
.parallel_in    (TOTAL_ZERO),
// verilator lint_off PINCONNECTEMPTY
.parallel_out   (),
// verilator lint_on  PINCONNECTEMPTY
.pipe_in        (quotient_increment >> 1),
.pipe_out       (quotient_increment)
);

Add/subtract to/from the quotient each time the denominator is successfully removed or added to from the current remainder without changing its sign.

reg  [WORD_WIDTH-1:0]   quotient_step           = WORD_ZERO;

#(
.WORD_WIDTH     (WORD_WIDTH)
)
calc_new_quotient
(
.carry_in   (1'b0),
.A_in       (current_quotient),
.B_in       (quotient_step),
.sum_out    (new_quotient),
// verilator lint_off PINCONNECTEMPTY
.carry_out  ()
// verilator lint_on  PINCONNECTEMPTY
);

Now let's do the control and steering logic

First, the input and output handshakes. To avoid long combination paths, ready and valid should not depend directly on eachother.

Accept inputs when empty (after results are read out) or frehsly reset/cleared). Declare outputs valid when calculation is done.

always @(*) begin
out_valid   = (running_state == STATE_DONE);

// Use this instead to allow starting a new calculation without first
// reading out the results. You can then use a Pipeline Half-Buffer to
// implement backpressure, based on it's input ready signal. (if not
// ready, then it's full, and if the divider also has valid results, then
// accept nothing into the divider)
// in_ready    = (running_state == STATE_INIT) || (running_state == STATE_DONE);
end

Then, define the basic interactions with and transformations within this module. Past this point, we should not refer directly to the FSM states, but to these events which are combinations of states and signals.

reg load_inputs       = 1'b0; // All of the above.
reg calculating       = 1'b0; // High while performing the division steps.
reg last_calculation  = 1'b0; // High during the last calculation step.
reg calculation_done  = 1'b0; // High after all the calculations

always @(*) begin
calculating       = (running_state == STATE_CALC);
last_calculation  = (running_state == STATE_CALC) && (current_calculation_step == STEPS_ZERO) && (current_c_slow_step == C_SLOW_STEPS_ZERO);
calculation_done  = (running_state == STATE_DONE);
end

Define the running state machine transitions. There is no handling of erroneous states.

always @(*) begin
next_running_state  = (load_inputs       == 1'b1) ? STATE_CALC : running_state;
next_running_state  = (last_calculation  == 1'b1) ? STATE_DONE : next_running_state;
next_running_state  = (read_outputs == 1'b1)      ? STATE_INIT : next_running_state;
end

Control the C_SLOW_RATIO step counter (one step per calculating cycle). We step the C_SLOW_RATIO step counter at load since loading the inputs also performs the first shifts of the numerator and remainder and computes the first new remainder and quotient stored at the next clock edge.

reg c_slow_step_last = 1'b0;

always @(*) begin
c_slow_step_last    = (current_c_slow_step == C_SLOW_STEPS_ZERO);
clear_c_slow_step   = (calculation_done    == 1'b1);
do_c_slow_step      = (load_inputs         == 1'b1) || (calculating == 1'b1);
end

Control the calculation step counter (one step for one cycle of C_SLOW_RATIO steps)

always @(*) begin
clear_calculation_step  = (calculation_done == 1'b1);
do_calculation_step     = (c_slow_step_last == 1'b1);
end

Control the denominator. They are both loaded just once at the start of the calculation steps, then cycled to output a new c-slowed value at each calculation step.

always @(*) begin
enable_denominator      = (calculating == 1'b1) || (load_denominator == 1'b1);
end

Control the numerator and its sign. The sign is loaded once at calculation start. The numerator gets loaded once at the start, then shifted left by 1 at each calculation step. Enable without load is a shift left. See Register_Pipeline.

always @(*) begin
enable_numerator      = (calculating == 1'b1) || (load_numerator == 1'b1);

enable_numerator_sign = (enable_numerator == 1'b1);
end

Control the remainder and select what to load into it. Load input once at start, then select new remainder at each calculations step.

always @(*) begin
enable_remainder = (load_remainder == 1'b1) || (calculating == 1'b1);
end

reg [REMAINDER_WIDTH-1:0] remainder_with_removal = REMAINDER_ZERO;
reg [REMAINDER_WIDTH-1:0] remainder_unchanged    = REMAINDER_ZERO;

always @(*) begin
remainder_with_removal = {new_remainder,     numerator_msb};
remainder_unchanged    = {current_remainder, numerator_msb};
remainder_updated      = (new_remainder_sign == current_remainder_sign) ? remainder_with_removal : remainder_unchanged;

for (i=0; i < C_SLOW_RATIO; i=i+1) begin: per_initial_remainder
all_initial_remainders[REMAINDER_WIDTH*i +: REMAINDER_WIDTH] = (numerator_signs_at_load[i] == POSITIVE) ? REMAINDER_ZERO : REMAINDER_ONES;
end
end

always @(*) begin
end

Control the quotient and what we add or subtract to/from it. Always zero at start of calculations.

always @(*) begin
enable_quotient             = (calculating == 1'b1);

clear_quotient_increment    = (clear_quotient  == 1'b1);
enable_quotient_increment   = (enable_quotient == 1'b1);
end

always @(*) begin