Polynomial datapath optimization using partitioning and compensation heuristics
O. Sarbishei, Bijan Alizadeh, Masahiro Fujita · 2009
Datapath designs that perform polynomial computations over Z 2 nare 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 2 n 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 2 n. 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.