Factoring and eliminating common subexpressions in polynomial expressions

ABSTRACT

Polynomial expressions are used to compute a wide variety of mathematical functions commonly found in signal processing and graphics applications, which provide good opportunities for optimization. However existing compiler techniques for reducing code complexity such as common subexpression elimination and value numbering are targeted towards general purpose applications and are unable to fully optimize these expressions. This work presents algorithms to reduce the number of operations to compute a set of polynomial expression by factoring and eliminating common subexpressions. These algorithms are based on the algebraic techniques for multi-level logic synthesis. Experimental results on a set of benchmark applications with polynomial expressions showed an average of 42.5% reduction in the number of multiplications and 39.6% reduction in the number of clock cycles for computation of these expressions on the ARM processor core, compared to common subexpression elimination.

REFERENCES

• 1: Armita Peymandoust , Giovanni De Micheli, Using symbolic algebra in algorithmic level DSP synthesis, Proceedings of the 38th conference on Design automation, p.277-282, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.378485]
• 2: [2] A. Peymandoust, T. Simunic, and G. D. Micheli, "Low Power Embedded Sottware Optimization Using Symbolic Algebra," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 2002.
• 3: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 4: [4] C. Fike, Computer Evaluation of Mathematical Functions. Englewood Cliffs, N.J: Prentice-Hall, 1968.
• 5: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to splines for use in computer graphics & geometric modeling, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 6: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 7: [7] R. Green, "Faster Math Functions," Sony Computer Entertainment Research and Development 2003.
• 8: [8] "GNU C Library." http://www.gnu.org
• 9: [9] R.K. Brayton and C.T. McMullen, "The Decomposition and Factorization of Boolean Expressions," , 1982.
• 10: [10] A.S. Vincentelli, A. Wang, R.K. Brayton, and R. Rudell, "MIS: Multiple Level Logic Optimization System," IEEE Transactions on Computer Aided Design of Integrated Circuits and Systems, 1987.
• 11: [11] R.K. Brayton, R. Rudell, A.S. Vincentetli, and A. Wang, "Multi-level Logic Optimization and the Rectangular Covering Problem.," Proceedings of the International Conference on Compute Aided Design, 1987.
• 12: A. V. Aho , S. C. Johnson , J. D. Ullman, Code Generation for Expressions with Common Subexpressions, Journal of the ACM (JACM), v.24 n.1, p.146-160, Jan. 1977 [doi>10.1145/321992.322001]
• 13: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]
• 14: Melvin A. Breuer, Generation of optimal code for expressions via factorization, Communications of the ACM, v.12 n.6, p.333-340, June 1969 [doi>10.1145/363011.363153]
• 15: Chunho Lee , Miodrag Potkonjak , William H. Mangione-Smith, MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.330-335, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Paul M. Embree, C language algorithms for real-time DSP, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 17: [17] M.D. Smith and G. Holloway, "An Introduction to Machine SUIF and its Portable Libraries for Analysis and Optimization," Harvard University, Cambridge, Mass. 2000.
• 18: [18] "Maple," Waterloo Maple Inc, 1998.
• 19: [19] "ARM7TDMI Technical Reference Manual," 2003.