Automating custom-precision function evaluation for embedded processors

ABSTRACT

Due to resource and power constraints, embedded processors often cannot afford dedicated floating-point units. For instance, the IBM PowerPC processor embedded in Xilinx Virtex-II Pro FPGAs only supports emulated floating-point arithmetic, which leads to slow operation when floating-point arithmetic is desired. This paper presents a customizable mathematical library using fixed-point arithmetic for elementary function evaluation. We approximate functions via polynomial or rational approximations depending on the user-defined accuracy requirements. The data representation for the inputs and outputs are compatible with IEEE single-precision and double-precision floating-point formats. Results show that our 32-bit polynomial method achieves over 80 times speedup over the single-precision mathematical library from Xilinx, while our 64-bit polynomial method achieves over 30 times speedup.

REFERENCES

• 1: Accelerated System Performance with APU-Enhanced Processing, Xcell Journal, Xilinx Inc. http://www.xilinx.com/publications/xcellonline/xcell_52/xc_pdf/xc_v4acu52.pdf.
• 2: Excalibur Device Overview Data Sheet, Altera Inc. http://www.altera.com/literature/ds/ds_arm.pdf
• 3: MicroBlaze Processor Reference Guide, Xilinx Inc. http://www.xilinx.com/ise/embedded/mb_ref_guide.pdf
• 4: ML310 User Guide, Xilinx Inc. http://www.xilinx.com/products/boards/ml310/current/pcb/sch/ug068.pdf
• 5: PowerPC 405 ProcessorBlock Reference Guide, Xilinx Inc. http://www.xilinx.com/bvdocs/userguides/ppc405block_ref_guide.pdf
• 6: Ahmet Akkas , Michael J. Schulte, A Quadruple Precision and Dual Double Precision Floating-Point Multiplier, Proceedings of the Euromicro Symposium on Digital Systems Design, p.76, September 01-06, 2003
• 7: Richard P. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, Journal of the ACM (JACM), v.23 n.2, p.242-251, April 1976 [doi>10.1145/321941.321944]
• 8: Nicolas Brisebarre , David Defour , Peter Kornerup , Jean-Michel Muller , Nathalie Revol, A New Range-Reduction Algorithm, IEEE Transactions on Computers, v.54 n.3, p.331-339, March 2005 [doi>10.1109/TC.2005.36]
• 9: Milos D. Ercegovac , Tomás Lang , Jean-Michel Muller , Arnaud Tisserand, Reciprocation, Square Root, Inverse Square Root, and Some Elementary Functions Using Small Multipliers, IEEE Transactions on Computers, v.49 n.7, p.628-637, July 2000 [doi>10.1109/12.863031]
• 10: Shmuel Gal, An accurate elementary mathematical library for the IEEE floating point standard, ACM Transactions on Mathematical Software (TOMS), v.17 n.1, p.26-45, March 1991 [doi>10.1145/103147.103151]
• 11: Yozo Hida , Xiaoye S. Li , David H. Bailey, Algorithms for Quad-Double Precision Floating Point Arithmetic, Proceedings of the 15th IEEE Symposium on Computer Arithmetic, p.155, June 11-13, 2001
• 12: Cristina Iordache , Ping Tak Peter Tang, An Overview of Floating-Point Support and Math Library on the Intel "XScale" Architecture, Proceedings of the 16th IEEE Symposium on Computer Arithmetic (ARITH-16'03), p.122, June 15-18, 2003
• 13: J. Harrison and T. Kubaska and S. Story and P.T.P. Tang. "The computation of transendental functions on the IA-64 architecture". Intel Technology Journal, Q4, pages 1--7, 1999.
• 14: I. Koren , O. Zinaty, Evaluating Elementary Functions in a Numerical Coprocessor Based on Rational Approximations, IEEE Transactions on Computers, v.39 n.8, p.1030-1037, August 1990 [doi>10.1109/12.57042]
• 15: D. Lee, A. Abdul Gaffar, O. Mencer, and W. Luk. "Adaptive range reduction for hardware function evaluation". In Proc. IEEE Int'l Conf. on Field-Programmable Technology, pages 169--176, 2004.
• 16: T. Lynch , A. Ahmed , M. Schulte , T. Callaway , R. Tisdale, The K5 transcendental functions, Proceedings of the 12th Symposium on Computer Arithmetic, p.163, July 19-21, 1995
• 17: P. W. Markstein, Computation of elementary functions on the IBM RISC System/6000 processor, IBM Journal of Research and Development, v.34 n.1, p.111-119, Jan. 1990
• 18: Oskar Mencer , Wayne Luk, Parameterized High Throughput Function Evaluation for FPGAs, Journal of VLSI Signal Processing Systems, v.36 n.1, p.17-25, January 2004 [doi>10.1023/B:VLSI.0000008067.31043.35]
• 19: Jean-Michel Muller, Elementary functions: algorithms and implementation, Birkhauser Boston, Inc., Secaucus, NJ, 1997
• 20: A. Nesterov. "Optimized math library for TMS320C67x DSP reference manual", 2001.
• 21: Behrooz Parhami, Computer arithmetic: algorithms and hardware designs, Oxford University Press, Oxford, 1999
• 22: George Paul , M. Wayne Wilson, Should the Elementary Function Library Be Incorporated Into Computer Instruction Sets?, ACM Transactions on Mathematical Software (TOMS), v.2 n.2, p.132-142, June 1976 [doi>10.1145/355681.355684]
• 23: M. J. Schulte , E. E. Swartzlander, Jr., Hardware Designs for Exactly Rounded Elementary Functions, IEEE Transactions on Computers, v.43 n.8, p.964-973, August 1994 [doi>10.1109/12.295858]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.3 SPECIAL-PURPOSE AND APPLICATION-BASED SYSTEMS
      Subjects: Real-time and embedded systems

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization; Code generation

General Terms:
Design, Measurement, Performance

Keywords:
embedded systems, fixed-point arithmetic, function evaluation, reconfigurable computing