Polynomial datapath optimization using partitioning and compensation heuristics

摘要

Datapath designs that perform polynomial computations over Z2n 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 Z2n 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 Z2n. 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.