Is there a way to implement division by variables other than 2 in single clock with XST ?
in [FPGA]
|
Prev: Which is the most beautiful and memorable hardware structure in a ?CPU?
Next: Is there a way to implement division by variables other than 2 in ?single clock with XST ?
From: glen herrmannsfeldt on 3 Apr 2010 16:21 PureSine <Green.Tech.Coder(a)gmail.com> wrote: > Hello, I need to do some DSP operations preferably with Spartan 3. I > need to divide output of a fast DDS by a variable but XST says it can > only implement a divider with constants of power of 2. > One way would be to recursively subtract divisor from dividend but that > needs many cycles which is not suitable for me. I prefer to do this > digitally within FPGA. Is there any digital solution preferably with > Spatan ? Pipeline it, one stage per quotient bit. In software terms, unroll the divide loop with a register between each cycle. Not having actually tried to implement one recently, my thought is for separate comparator and subtractor, possibly with a separate pipeline stage for each. It will still take a lot of cycles, but once the pipeline is full you get one result per cycle. -- glen
From: John_H on 3 Apr 2010 16:44 On Apr 3, 4:21 pm, glen herrmannsfeldt <g...(a)ugcs.caltech.edu> wrote: > > Pipeline it, one stage per quotient bit. In software terms, unroll > the divide loop with a register between each cycle. > > Not having actually tried to implement one recently, my thought > is for separate comparator and subtractor, possibly with a > separate pipeline stage for each. It will still take a lot > of cycles, but once the pipeline is full you get one result > per cycle. > > -- glen Great advice. You can also perform several stages of the division per clock cycle reducing a 16-bit division to 4 clock cycles, for instance. There are better ways to perform pipelined division but you'll need to consider this approach regardless. Another possibility is to multiply rather than add. If your variable isn't available until the clock cycle (right before) you need it, you'll have to decide how many significant bits are needed for a lookup or two to determine a close approximation of the reciprocal. If your variable is available a few clock cycles ahead of time, you can provide the reciprocal to high precision when it's needed. If your "variable" is provided by software, have software provide the reciprocal directly. Dedicated multipliers make reciprocal multiplication much simpler than division though, perhaps, a tiny bit less "precise" depending on your needs. To understand a faster way to divide compared to "determining whether you can subtract the divisor for each stage of the pipeline then subtracting from or passing the previous value" you can instead *always* subtract from a positive value and *always* add from a negative value, simply appending a little arithmetic to the signs from the intermediate stages to get the final result. Try doing some binary long division by hand with the two approaches and you may see how you can come up with the same results with better optimized hardware.
From: Brian Drummond on 3 Apr 2010 17:03 On Sun, 04 Apr 2010 00:33:59 +0430, PureSine <Green.Tech.Coder(a)gmail.com> wrote: >Hello, I need to do some DSP operations preferably with Spartan 3. I >need to divide output of a fast DDS by a variable but XST says it can >only implement a divider with constants of power of 2. >One way would be to recursively subtract divisor from dividend but that >needs many cycles which is not suitable for me. I prefer to do this >digitally within FPGA. Is there any digital solution preferably with >Spatan ? If the divisor is a constant, or a small set of constants, simply multiply by the reciprocal. - Brian
From: KJ on 3 Apr 2010 18:30 On Apr 3, 4:03 pm, PureSine <Green.Tech.Co...(a)gmail.com> wrote: > Hello, I need to do some DSP operations preferably with Spartan 3. I > need to divide output of a fast DDS by a variable but XST says it can > only implement a divider with constants of power of 2. > One way would be to recursively subtract divisor from dividend but that > needs many cycles which is not suitable for me. I prefer to do this > digitally within FPGA. Is there any digital solution preferably with > Spatan ? > Google for LPM_DIVIDE and 220model.vhd http://www.google.com/webhp?sourceid=navclient&ie=UTF-8#hl=en&safe=off&q=lpm_divide+220model.vhd&aq=f&aqi=&aql=&oq=&gs_rfai=&fp=43dd59e47af515fb One link for a source file is... http://himac02.nbi.dk:8888/cgi-bin/viewvc.cgi/fmdd_bc/lpm/220model.vhd?view=markup&root=cvs&sortdir=down LPM functions, while promoted by Altera, are also synthesizable (once you get the source files) for any device, not just Altera. For documentation on how to use lpm_divide, the Altera docs will help. Lpm_Divide will perform a pipeline divide, no constraints on powers of 2 and can compute a new output on every clock cycle. Kevin Jennings
From: Nico Coesel on 4 Apr 2010 07:18
PureSine <Green.Tech.Coder(a)gmail.com> wrote: >Hello, I need to do some DSP operations preferably with Spartan 3. I >need to divide output of a fast DDS by a variable but XST says it can >only implement a divider with constants of power of 2. >One way would be to recursively subtract divisor from dividend but that >needs many cycles which is not suitable for me. I prefer to do this >digitally within FPGA. Is there any digital solution preferably with >Spatan ? You can use a multiplier and fixed point arithmetics. If you define 1 as 0x8000 then a multiplying by 0x3000 means dividing by 2.667. Ofcourse you'll need to divide the output of the multiplier by 0x8000 but that is a matter of wiring the output of the multiplier so it skips the first 15 bits. -- Failure does not prove something is impossible, failure simply indicates you are not using the right tools... nico(a)nctdevpuntnl (punt=.) -------------------------------------------------------------- |