skip to main content
10.1109/ICCAD.2004.1382566acmconferencesArticle/Chapter ViewAbstractPublication PagesiccadConference Proceedingsconference-collections
Article

Factoring and eliminating common subexpressions in polynomial expressions

Published: 07 November 2004 Publication History

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]
{1} A. Peymandoust and G. D. Micheli, "Using Symbolic Algebra in Algorithmic Level DSP Synthesis," Proceedings of the Design Automation Conference, 2001.
[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]
{3} D.E. Knuth, The Art of Computer Programming, vol. 2: Seminumerical algorithms, Second ed: Addison-Wesley, 1981.
[4]
{4} C. Fike, Computer Evaluation of Mathematical Functions. Englewood Cliffs, N.J: Prentice-Hall, 1968.
[5]
{5} R.H. Bartels, J.C. Beatty, and B.A. Barsky, An Introduction to Splines for Use in Computer Graphics and Geometric Modeling: Morgan Kaufmann Publishers, Inc., 1987.
[6]
{6} S.S. Muchnick, Advanced Compiler Design and Implementation: Morgan Kaufmann Publishers, 1997.
[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," Proceedings of the International Symposium on Circuits and Systems, 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]
{12} A.V. Aho, S.C. Johnson, and J.D. Ullman, "Code Generation for Expressions with Common Subexpressions," ACM, vol. 24, pp. 146-160, 1977.
[13]
{13} R. Sethi and J.D. Ullman, "The Generation of Optimal Code for Arithmetic Expressions," Communications of the ACM, vol. 17, pp. 715-728, 1970.
[14]
{14} M.A. Breuer, "Generation of Optimal Code for Expressions via Faetorization," Communications of the ACM, vol. 12, pp. 333-340, 1969.
[15]
{15} C. Lee, M. Potkonjak, and W.H. Mangione-Smith, "MediaBench: a tool for evaluating and synthesizing multimedia and communicatons systems," Proceedings of the International Symposium on Microarchitecture, Research Triangle Park, North Carolina, United States, 1997.
[16]
{16} P.M. Embree, C Algorithms for Real-Time DSP: Prentice Hall, 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.

Cited By

View all
  • (2017)Probabilistic database summarization for interactive data explorationProceedings of the VLDB Endowment10.14778/3115404.311541910:10(1154-1165)Online publication date: 1-Jun-2017
  • (2016)Automatically Optimizing the Latency, Area, and Accuracy of C Programs for High-Level SynthesisProceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2847263.2847282(234-243)Online publication date: 21-Feb-2016
  • (2015)Numerical Program Optimization for High-Level SynthesisProceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2684746.2689090(210-213)Online publication date: 22-Feb-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
ICCAD '04: Proceedings of the 2004 IEEE/ACM International conference on Computer-aided design
November 2004
913 pages
ISBN:0780387023

Sponsors

Publisher

IEEE Computer Society

United States

Publication History

Published: 07 November 2004

Check for updates

Qualifiers

  • Article

Conference

ICCAD04
Sponsor:

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 28 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2017)Probabilistic database summarization for interactive data explorationProceedings of the VLDB Endowment10.14778/3115404.311541910:10(1154-1165)Online publication date: 1-Jun-2017
  • (2016)Automatically Optimizing the Latency, Area, and Accuracy of C Programs for High-Level SynthesisProceedings of the 2016 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2847263.2847282(234-243)Online publication date: 21-Feb-2016
  • (2015)Numerical Program Optimization for High-Level SynthesisProceedings of the 2015 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays10.1145/2684746.2689090(210-213)Online publication date: 22-Feb-2015
  • (2010)Polynomial datapath optimization using constraint solving and formal modellingProceedings of the International Conference on Computer-Aided Design10.5555/2133429.2133589(756-761)Online publication date: 7-Nov-2010
  • (2010)Efficient evaluation of large polynomialsProceedings of the Third international congress conference on Mathematical software10.5555/1888390.1888464(342-353)Online publication date: 13-Sep-2010
  • (2010)Modular datapath optimization and verification based on modular-HEDIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2010.205927129:9(1422-1435)Online publication date: 1-Sep-2010
  • (2009)Improved heuristics for finite word-length polynomial datapath optimizationProceedings of the 2009 International Conference on Computer-Aided Design10.1145/1687399.1687536(739-744)Online publication date: 2-Nov-2009
  • (2009)Polynomial datapath optimization using partitioning and compensation heuristicsProceedings of the 46th Annual Design Automation Conference10.1145/1629911.1630151(931-936)Online publication date: 26-Jul-2009
  • (2008)Verification of arithmetic datapaths using polynomial function models and congruence solvingProceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design10.5555/1509456.1509494(122-128)Online publication date: 10-Nov-2008
  • (2007)Finding linear building-blocks for RTL synthesis of polynomial datapaths with fixed-size bit-vectorsProceedings of the 2007 IEEE/ACM international conference on Computer-aided design10.5555/1326073.1326103(143-148)Online publication date: 5-Nov-2007
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media