FPGA Division

[kevin.key]

Hey,

After looking around the forums and NI's website, I've found a few discussions on the different ways to implement division using LabView FPGA. I'm not sure that the pros and cons of each method are fully described.

As far as I'm aware there are these methods:

Fixed-Point math

Quotient Remainder block

While Loop Subtraction method

Scaling method

I think I've understood correctly that the scaling method requires knowing the divisor before compilation and the While Loop Subtraction method is slow (too slow for my application, I've tried). But I'm curious about the comparison between doing Fixed-Point math and the Quotient-Remainder block.

Any help would be greatly appreciated,

Kevin

[RyanB]

Hi Kevin,

Can you provide more detail about your application?

Which LV FPGA target are you using?  What are the data types and data rates?  Does it need to run in the Single-Cycle Timed Loop?  Any other requirements?

[kevin.key]

PXI-7854 or a PXI-7842

Data type is U32 / U32, and the rate is about once every 100ms but the divide needs to complete in under 2ms

I was using the While Loop subtract method, but I noticed odd behavior at range of values and I figured out the divide was 465957888 / 16000. I found the other methods and switched out the While Loop subtract method with the Quotient Remainder block the problem went away. I also tried the Fixed-Point math method and it worked too. So now I was just wondering how does the Fixed-Point math and Quotient-Remainder block method compare?

Thanks,
Kevin

[T-REX$]

Hi Kevin,

The best bet in this situation is to use the high-throughput divide function.It will take about 34 cycles, but I am pretty sure it's as fast as you can get for division with U32. Depending on your clock speed, this should be quick enough. Something like this:

[kevin.key]

Thanks, I'm curious how does the Quotient-Remainder block implement it's divide?

[T-REX$]

Kevin,

I'm actually not sure. I know there are a couple methods for implementing integer division in digital logic, but I have no way of knowing which algorithm we actually implement. I would have to guess that the algorithm is either Goldschmidt Division or Barrett Reduction, but I really have no way of knowing.

[T-REX$]

Kevin,

Actually, I just checked the resource usage page, and it looks like the Quotient and Remainder block uses a rather large number of lookup tables. This suggests that it is the SRT algorithm.

[kevin.key]

OK, thanks for the info. I think I'm going with the quotient remainder block, because the fixed-point math consumes more DSP blocks.