Polynomial datapath optimization using partitioning and compensation heuristics

ABSTRACT

Datapath designs that perform polynomial computations over Z₂ⁿ are used in many applications such as computer graphics and digital signal processing domains. As the market of such applications continues to grow, improvements in high-level synthesis and optimization techniques for multivariate polynomials have become really challenging. This paper presents an efficient algorithm for optimizing the implementation of a multivariate polynomial over Z₂ⁿ in terms of the number of multipliers and adders. This approach makes use of promising heuristics to extract more complex common sub-expressions from the polynomial compared to the conventional methods. The proposed algorithm also utilizes a canonical decision diagram, Horner-Expansion Diagram (HED) [1] to reduce the polynomial's degree over Z₂ⁿ. Experimental results have shown an average saving of 27% and 10% in terms of the number of logic gates and critical path delay respectively compared to existing high-level synthesis tools as well as state of the art algebraic approaches.

REFERENCES

• 1: B. Alizadeh and M. Fujita, "Modular-HED: A Canonical Decision Diagram for Modular Equivalence Verification of Polynomial Functions", in the fifth Workshop on Constraints in Formal Verification (CFV), pp. 22--40, 2008.
• 2: A. Peymandoust and G. DeMicheli, "Application of Symbolic Computer Algebra in High-Level Data-Flow Synthesis", IEEE Trans. CAD, vol. 22, pp. 1154--11656, 2003.
• 3: Sivaram Gopalakrishnan and Priyank Kalla, "Optimization of polynomial datapaths using finite ring algebra", ACM Trans. Design Automation of Electronics Systems, vol. 12, pp. 49, 2007.
• 4: S. Gopalakrishnan, P. Kalla, Brandon Meredith, and F. Enescu, "Finding linear building-blocks for RTL synthesis of polynomial datapaths with fixed-size bit-vectors", in ICCAD, pp. 143--148, 2007.
• 5: A. Hosangadi, F. Fallah, R. Kastner, "Factoring and Eliminating Common Subexpressions in Polynomial Expressions", in ICCAD, pp. 169--174, 2004.
• 6: JuanCSE, "Extensible, programmable and reconfigurable embedded systems group", Available at: http://express.ece.ucsb.edu/suif/cse.html.
• 7: E. Kaltofen, J. P. May, Z. Yang, L. Zhi, "Approximate Factorization of Multivariate Polynomials Using Singular Value Decomposition", Journal of Symbolic Computation, pp. 359--376, 2008.
• 8: J. Krumm, "Savitzky-Golay Filters for 2D Images", Available at: http://homepages.inf.ed.ac.uk/rf/CVonline/LOCAL_COPIES/KRUMMI/SavGol.htm.
• 9: V. J. Mathews and G. L. Sicuranza, Polynomial Signal Processing, Wiley-Interscience, 2000.
• 10: M. R. Guthaus and et al., "Mibench: A Free, Commercially Representative Embedded Benchmark Suite", in IEEE 4^th Annual Workshop on Workload Characterization, pp. 3--14, 2001.
• 11: A. Hosangadi, F. Fallah, and R. Kastner, "Optimizing polynomial expressions by algebraic factorization and common subexpression elimination", IEEE Trans. CAD, vol. 25, pp. 2012--2022, Oct 2006.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.5 REGISTER-TRANSFER-LEVEL IMPLEMENTATION
      B.5.1 Design
          Subjects: Data-path design

General Terms:
Algorithms

Keywords:
high-level synthesis, modular HED, polynomial datapath