Automatic SIMD vectorization of chains of recurrences

ABSTRACT

Many computational tasks require repeated evaluation of functions over structured grids, such as plotting in a coordinate system, rendering of parametric objects in 2D and 3D, numerical grid generation, and signal processing. In this paper, we present a method and toolset to speed up closed-form function evaluations over grids by vectorizing Chains of Recurrences (CR). CR forms of closed-form functions require fewer operations to evaluate per grid point. However, the present CR formalism makes CR forms inherently non-vectorizable due to the dependences carried from one point to the next. To address this limitation, we developed a new decoupling method for the CR algebra to translate math functions into Vector Chains of Recurrences (VCR) forms. The VCR coefficients are packed in short vector registers for efficient execution. Performance results of benchmark functions evaluated in single and double precision VCR forms are compared to the Intel compiler's auto-vectorized code and the high-performance small vector math library (SVML). The results show a significant performance increase of our VCR method over SVML and scalar CRs, from doubling the execution speed to running an order of magnitude faster. An auto-tuning tool for VCR is developed for optimal performance and accuracy.

REFERENCES

• 1: SWI-Prolog's Home. Available from http://www.swi-prolog.org/.
• 2: Intel Math Kernel Library Reference Manual, March 2007. Intel Document number: 630813-025US.
• 3: Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 4: Vicki H. Allan , Reese B. Jones , Randall M. Lee , Stephen J. Allan, Software pipelining, ACM Computing Surveys (CSUR), v.27 n.3, p.367-432, Sept. 1995 [doi>10.1145/212094.212131]
• 5: Ken Kennedy , John R. Allen, Optimizing compilers for modern architectures: a dependence-based approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 6: O. Bachmann. Chains of Recurrences. PhD thesis, Kent State University, College of Arts and Sciences, 1996.
• 7: Olaf Bachmann , Paul S. Wang , Eugene V. Zima, Chains of recurrences—a method to expedite the evaluation of closed-form functions, Proceedings of the international symposium on Symbolic and algebraic computation, p.242-249, July 20-22, 1994, Oxford, United Kingdom [doi>10.1145/190347.190423]
• 8: Aart J. C. Bik, Software Vectorization Handbook, The: Applying Intel Multimedia Extensions for Maximum Performance, Intel Press, 2004
• 9: L. Kylex. How to Avoid Bottlenecks in Simple Math Functions. Available from http://softwarecommunity.intel.com/articles/eng/3524.htm, Intel 2004.
• 10: R. van Engelen. Symbolic Evaluation of Chains of Recurrences for Loop Optimization. Technical report, TR-000102, Computer Science Dept., Florida State University, 2000.
• 11: Robert van Engelen, Efficient Symbolic Analysis for Optimizing Compilers, Proceedings of the 10th International Conference on Compiler Construction, p.118-132, April 02-06, 2001
• 12: Robert A. van Engelen , J. Birch , Y. Shou , B. Walsh , Kyle A. Gallivan, A unified framework for nonlinear dependence testing and symbolic analysis, Proceedings of the 18th annual international conference on Supercomputing, June 26-July 01, 2004, Malo, France [doi>10.1145/1006209.1006226]
• 13: An Efficient Algorithm for Pointer-to-Array Access Conversion for Compiling and Optimizing DSP Applications, Proceedings of the Innovative Architecture for Future Generation High-Performance Processors and Systems (IWIA'01), p.80, January 18-19, 2001
• 14: Robert van Engelen , Lex Wolters , Gerard Cats, CTADEL: a generator of multi-platform high performance codes for PDE-based scientific applications, Proceedings of the 10th international conference on Supercomputing, p.86-93, May 25-28, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237578.237589]
• 15: J. E. Volder. The Cordic Trigonometric Computing Technique. IRE Transactions Electronic Computers, EC-8:330--334, September 1959.
• 16: A. K. Yuen. Intel's Floating--Point Processors. In Electro/88 Conference Record, pages 48/5/1--7, 1988.
• 17: Eugene V. Zima, Recurrent Relations and Speed-up of Computations Using Computer Algebra Systems, Proceedings of the International Symposium on Design and Implementation of Symbolic Computation Systems, p.152-161, April 13-15, 1992
• 18: E V Zima, Automatic construction of systems of recurrence relations, USSR Computational Mathematics and Mathematical Physics, v.24 n.11-12, p.193-197, March 1986
• 19: Eugene V. Zima, On computational properties of chains of recurrences, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.345, July 2001, London, Ontario, Canada [doi>10.1145/384101.384148]
• 20: Eugene V. Zima , Karthi R. Vadivelu , Thomas L. Casavant, Mapping Techniques for Parallel Evaluation of Chains of Recurrences, Proceedings of the 10th International Parallel Processing Symposium, p.620-624, April 15-19, 1996

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Parallel and vector implementations

General Terms:
Algorithms, Performance

Keywords:
ILP, chains of recurrences, short vector simd, vectorization