Efficient division algorithm?

KJ wrote:

>> A binary search multiply-subtract is possible with dsp blocks.
>>
> That's one that I've always wanted to try just to see how well it
> does, but haven't had the need to do so of late.

Yes, that one's on my white board too.

> One would expect it
> to get high throughput, low logic usage and probably be the best in
> today's world of nearly free DSP block multipliers in FPGAs.

It would be a good use for hardware multipliers
that often left unwired.

> Any benchmark data?

Well it couldn't do any better than log2(quotient) ticks
with one multiplier. Hmmm.. could divide that time 2**m for
m multipliers and parallel searches...

          -- Mike Treseler

KJ wrote:

>> Quartus will infer lpm_divide from from int or signed /.
>>
> Doing so though will result in lpm_divide being parameterized with 0
> latency which will result in the largest logic lump and the slowest
> clock cycle performance.  Depending on the application it might be
> better to instantiate the lpm_divide and not have it inferred from
> "/".

Thanks for the clarifications.
I might also try using "/"
with pipeline registers
and turn on synthesis register retiming.

       -- Mike Treseler

Hi all,

Take a look at http://www.xilinx.com/support/documentation/user_guides/ug073.pdf
On page 61, it describes two different algorithms. I've implement the
first one without DSP block. It can perform a division of N bits in N
cycles. It runs quite fast; on Spartan-3A-5, 100MHz for 32 bits
(200MHz for 8 bits).

Best regards.

On Feb 19, 7:57 am, KJ <kkjenni...@sbcglobal.net> wrote:
> On Feb 19, 9:43 am, Mike Treseler <mike_trese...@comcast.net> wrote:
> > Quartus will infer lpm_divide from from int or signed /.
>
> Doing so though will result in lpm_divide being parameterized with 0
> latency which will result in the largest logic lump and the slowest
> clock cycle performance.  Depending on the application it might be
> better to instantiate the lpm_divide and not have it inferred from
> "/".

It doesn't have to be. If you explicitly delay the result, it will
infer pipeline stages (I haven't tried it for divide, but other lpm
works this way) . Eg.

  res3 <= a / b;
  res2 <= res3;
  res1 <= res2;
  final_result <= res1;

You get the idea.

Tommy

Nial Stewart wrote:
> I'm going to talk to a potential new client about using FPGAs to
> accelerate part of their system.
> 
> As part of what needs done there could be a significant amount of
> division(s) done.
> 
> Previously I've been able to multiply by a reciprocal then scale to
> make division a double clock operation so this can be easily pipelined.
> This is only achieveable if the divisor is pre-known and the
> reciprocal can be pre-calculated.
> 
> With what's coming up I'm not sure that I can do this, I know that
> 
> Are there any clever techniques for streamlining divisions that
> make them deterministic and don't use a big wodge of logic?
> 
> 
> Thanks for any pointers,
> 
> 
> Nial
> 
> 

Nial,

Your reciprocal division is reasonably close to a low latency divider 
I've used many times in the past.  Instead of just one reciprocal, use 
the upper bits of the denominator to address a BRAM containing 
reciprocals, then use the lower bits of the denominator to interpolate 
between the stored reciprocals to obtain a corrected reciprocal for more 
precision.  Use that to multiply the numerator to obtain the quotient. 
It can be pipelined to run at the max clock for the multipliers, and has 
a latency of a BRAM plus two multipliers plus an adder.

For example a divider with 17 bit denominator and numerator and 16 bit 
quotient can use the upper 10 bits of the denominator to address a 1Kx18 
reciprocal ROM to get an approximate reciprocal.  Interpolate using a 
second 1Kx18 ROM (holds the slope at each stored reciprocal) and a 
multiplier to get a correction equal to the product of the 6 LSBs of the 
denominator and the entry from the interpolation rom. That gets added to 
the reciprocal ROM output to get a corrected reciprocal.  Multiply that 
corrected reciprocal by the numerator and round to get the quotient. 
The entire 17 bit divide uses two multipliers, two BRAMs and two adders 
plus registers to match delays to give a low latency divider.  You can 
improve the accuracy further if you can normalize the denominator and 
numerator before the divide and then denormalize by the difference of 
the normalizing shifts afterwards (basically floating point).

Nial Stewart wrote:
> I'm going to talk to a potential new client about using FPGAs to
> accelerate part of their system.
> 
> As part of what needs done there could be a significant amount of
> division(s) done.
> 
> Previously I've been able to multiply by a reciprocal then scale to
> make division a double clock operation so this can be easily pipelined.
> This is only achieveable if the divisor is pre-known and the
> reciprocal can be pre-calculated.
> 
> With what's coming up I'm not sure that I can do this, I know that
> 
> Are there any clever techniques for streamlining divisions that
> make them deterministic and don't use a big wodge of logic?
> 
> 
> Thanks for any pointers,
> 
> 
> Nial
> 
> 
I've heard that the CORDIC can be used for division.  I'm not sure how 
favorably this compares with other methods.
-Kevin

Kevin Neilson wrote:

>>
> I've heard that the CORDIC can be used for division.  I'm not sure how 
> favorably this compares with other methods.
> -Kevin

Cordic division is similar to non-restoring sequential division.  It 
uses a lot of adder-subtractors, which means it is either quite slow or 
it has a large clock latency.

> Nial,
> Your reciprocal division is reasonably close to a low latency divider I've used many times in the 
> past.  Instead of just one reciprocal, use the upper bits of the denominator to address a BRAM 
> containing reciprocals, then use the lower bits of the denominator to interpolate between the 
> stored reciprocals to obtain a corrected reciprocal for more precision.  Use that to multiply the 
> numerator to obtain the quotient. It can be pipelined to run at the max clock for the multipliers, 
> and has a latency of a BRAM plus two multipliers plus an adder.
>
> For example a divider with 17 bit denominator and numerator and 16 bit quotient can use the upper 
> 10 bits of the denominator to address a 1Kx18 reciprocal ROM to get an approximate reciprocal. 
> Interpolate using a second 1Kx18 ROM (holds the slope at each stored reciprocal) and a multiplier 
> to get a correction equal to the product of the 6 LSBs of the denominator and the entry from the 
> interpolation rom. That gets added to the reciprocal ROM output to get a corrected reciprocal. 
> Multiply that corrected reciprocal by the numerator and round to get the quotient. The entire 17 
> bit divide uses two multipliers, two BRAMs and two adders plus registers to match delays to give a 
> low latency divider.  You can improve the accuracy further if you can normalize the denominator 
> and numerator before the divide and then denormalize by the difference of the normalizing shifts 
> afterwards (basically floating point).


Thanks Ray,

This is exactly the sort of technique I was talking about.

This will defenitely be worth a look in I end up having to do multiple
divisions (as I think I might have to).


Nial. 

The NiosII blurb says that it can implement a single instruction
32 bit multiply or divide.

I wonder what sort of architecture they're using?


Nial. 

>The NiosII blurb says that it can implement a single instruction
>32 bit multiply or divide.
>
>I wonder what sort of architecture they're using?

What's unusual about a single instruction multiply or divide?  Surely
it's just a question of writing the microcode to do it.

Mike