Pipelining of double precision floating point division and square root operations

ABSTRACT

Space applications rely increasingly on high data rate DSP algorithms. These algorithms use double precision floating point arithmetic operations. While most DSP applications can be compiled on DSP processors, high data rate DSP computations require novel implementation technologies to support their high throughputs. Only recently, gate densities in FPGAs have reached a level which makes them attractive platforms to implement compute-intensive DSP applications. In this context, this paper presents the sequential and pipelined designs of a double precision floating point divider and square root unit on FPGAs. Contrary to pipelined parallel implementations, the pipelining of these units is based on unrolling the iterations in low-radix digit recurrence algorithms. These units are mapped on generic FPGA reconfigurable fabric without taking advantage of any advanced architectural components available in high capacity FPGAs. The implementations of these designs show that their performances are comparable to, and sometimes higher than, the performances of non-iterative designs based of high radix numbers. The iterative divider and square root unit occupy less than 1% of an XC2V6000 FPGA chip while their pipelined counterparts can produce throughputs that reach the 100 MFLOPS mark by consuming a modest 8% of the chip area.

REFERENCES

• 1: Parkes, S. M. DSP (Demanding Space-based Processing!): the Path Behind and the Road Ahead. In Proceedings of 6th International Workshop on Digital Signal Processing Techniques for Space Applications, (Noordwijk, The Netherlands, Sep 23--25, 1998), 1--11.
• 2: IEEE Standard Board. IEEE Standard for Binary Floatingpoint Arithmetic. In The Institute for Electrical and Electronics Engineers. (New York, Aug 12, 1985).
• 3: Kurt Keutzer, Challenges in CAD for the one million gate FPGA, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.133-134, February 09-11, 1997, Monterey, California, United States [doi>10.1145/258305.258326]
• 4: Govindu, G., Scrofano, R., and Prasanna, V. K. A Library of Parameterizable Floating-Point Cores for FPGAs and their Application to Scientific Computing. In International Conference on Engineering of Reconfigurable Systems and Algorithms, (Monte Carlo Resort, Las Vegas, Nevada, USA, June 27--30, 2005).
• 5: Paschalakis, S., and Lee, P. Double Precision Floating-Point Arithmetic on FPGAs. In IEEE Conference on Field-Programmable Technology, (Tokyo, Japan, Dec 15--17, 2003), 352--358.
• 6: Lee, B., and Burgess, N. Parameterisable Floating--Point Operations on FPGA. In Asilomar Conference on Signals, Systems, and Computers (Nov 3-6, 2002), 1064--1068.
• 7: Xiaojun Wang , Brent E. Nelson, Tradeoffs of Designing Floating-Point Division and Square Root on Virtex FPGAs, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.195, April 09-11, 2003
• 8: Daga, V., Govindu, G., Prasanna, V., Gangadharapalli, S., and Sridhar, V. Efficient Floating-Point Based Block LU Decomposition on FPGAs. In International Conference on Engineering of Reconfigurable Systems and Algorithms, (Las Vegas, Nevada, USA, June 21-24, 2004), 276--279.
• 9: Scrofano, R., and Prasanna, V. K. Computing Lennard-Jones Potentials and Forces with Reconfigurable Hardware. International Conference on Engineering of Reconfigurable Systems and Algorithms, (June 22, 2004), 284--290.
• 10: Yamin Li , Wanming Chu, Implementation of single precision floating point square root on FPGAs, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.226, April 16-18, 1997

INDEX TERMS

Primary Classification:
  B. Hardware
  B.2 ARITHMETIC AND LOGIC STRUCTURES
      B.2.4 High-speed Arithmetic

General Terms:
Algorithms, Design, Performance

Keywords:
FPGA, division, floating point, pipelining, square root