Programmable numerical function generators based on quadratic approximation: architecture and synthesis method

ABSTRACT

This paper presents an architecture and a synthesis method for programmable numerical function generators (NFGs) for trigonometric, logarithmic, square root, and reciprocal functions. Our NFG partitions a given domain of the function into non-uniform segments using an LUT cascade, and approximates the given function by a quadratic polynomial for each segment. Thus, we can implement fast and compact NFGs for a wide range of functions. Implementation results on an FPGA show that: 1) our NFGs require only 4% of the memory needed by NFGs based on the linear approximation with non-uniform segmentation; and 2) our NFGs require only 22% of the memory needed by NFGs based on the 5th-order approximation with uniform segmentation. Our automatic synthesis system generates such compact NFGs quickly.

REFERENCES

• 1: Ray Andraka, A survey of CORDIC algorithms for FPGA based computers, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.191-200, February 22-25, 1998, Monterey, California, United States [doi>10.1145/275107.275139]
• 2: Jun Cao , Belle W. Y. Wei , Jie Cheng, High-Performance Architectures for Elementary Function Generation, Proceedings of the 15th IEEE Symposium on Computer Arithmetic, p.136, June 11-13, 2001
• 3: D. Defour, F. de Dinechin, and J.-M. Muller, "A new scheme for table-based evaluation of functions," 36th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, California, pp. 1608--1613, Nov. 2002.
• 4: J. Detrey and F. de Dinechin, "Second order function approximation using a single multiplication on FPGAs," Proc. Inter. Conf. on Field Programmable Logic and Applications (FPL'04), pp. 221--230, 2004.
• 5: Nobuhiro Doi , Takashi Horiyama , Masaki Nakanishi , Shinji Kimura, Minimization of fractional wordlength on fixed-point conversion for high-level synthesis, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.80-85, January 27-30, 2004, Yokohama, Japan
• 6: Hannes Hassler , Naofumi Takagi, Function Evaluation by Table Look-up and Addition, Proceedings of the 12th Symposium on Computer Arithmetic, p.10, July 19-21, 1995
• 7: T. Ibaraki and M. Fukushima, FORTRAN 77 Optimization Programming, Iwanami, 1991 (in Japanese).
• 8: Realization of Multiple-Output Functions by Reconfigurable Cascades, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.388, September 23-26, 2001
• 9: D.-U. Lee, W. Luk, J. Villasenor, and P. Y. K. Cheung, "Non-uniform segmentation for hardware function evaluation," Proc. Inter. Conf. on Field Programmable Logic and Applications, pp. 796--807, Lisbon, Portugal, Sept. 2003.
• 10: Dong-U Lee , Wayne Luk , John Villasenor , Peter Y. K. Cheung, A Hardware Gaussian Noise Generator for Channel Code Evaluation, Proceedings of the 11th Annual IEEE Symposium on Field-Programmable Custom Computing Machines, p.69, April 09-11, 2003
• 11: John H Mathews, Numerical methods for computer science, engineering, and mathematics, Prentice-Hall, Inc., Upper Saddle River, NJ, 1986
• 12: Jean-Michel Muller, Elementary functions: algorithms and implementation, Birkhauser Boston, Inc., Secaucus, NJ, 1997
• 13: S. Nagayama and T. Sasao, "Compact representations of logic functions using heterogeneous MDDs," IEICE Trans. on fundamentals, Vol. E86-A, No. 12, pp. 3168--3175, Dec. 2003.
• 14: S. Nagayama, T. Sasao, and J. T. Butler, "Error analysis for programmable numerical function generators based on quadratic approximation," http://www.lsi-cad.com/Error-QNFG/.
• 15: T. Sasao, M. Matsuura, and Y. Iguchi, "A cascade realization of multiple-output function for reconfigurable hardware," Inter. Workshop on Logic Synthesis (IWLS'01), Lake Tahoe, CA, pp. 225--230, June 12--15, 2001.
• 16: T. Sasao, J. T. Butler, and M. D. Riedel, "Application of LUT cascades to numerical function generators," Proc. the 12th workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI'04), Kanazawa, Japan, pp. 422--429, Oct. 2004.
• 17: T. Sasao, S. Nagayama, and J. T. Butler, "Programmable numerical function generators: architectures and synthesis method," Proc. Inter. Conf. on Field Programmable Logic and Applications (FPL'05), Tampare, Finland, pp. 118--123, Aug. 2005.
• 18: Scilab 3.0 INRIA-ENPC, France, http://scilabsoft.inria.fr/
• 19: Michael J. Schulte , James E. Stine, Approximating Elementary Functions with Symmetric Bipartite Tables, IEEE Transactions on Computers, v.48 n.8, p.842-847, August 1999 [doi>10.1109/12.795125]
• 20: James E. Stine , Michael J. Schulte, The Symmetric Table Addition Method for Accurate Function Approximation, Journal of VLSI Signal Processing Systems, v.21 n.2, p.167-177, June 1999 [doi>10.1023/A:1008004523235]
• 21: J. E. Volder, "The CORDIC trigonometric computing technique," IRE Trans. Electronic Comput., Vol. EC-820, No. 3, pp. 330--334, Sept. 1959.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.7 INTEGRATED CIRCUITS
      B.7.1 Types and Design Styles

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis
  B.7 INTEGRATED CIRCUITS
      B.7.2 Design Aids
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

General Terms:
Design, Performance