ILP modelling of the common subexpression sharing problem

Abstract

Subexpression sharing is an important implementation issue when one data is multiplied with many constants or a sum of products is computed. By modelling the subexpression sharing problem using integer linear programming (ILP) an optimal solution can be found. Further, the model can be directly incorporated with the design of algorithms that have linear design constraints, e.g., linear-phase FIR filters. The proposed method is compared with previously reported algorithms. It produces better results than other subexpression sharing methods, even though it is still not comparable with the optimal method based on graph representation. However, the possibility to expand the ILP model beyond subexpression sharing is discussed. This would then produce identical results to the optimal adder graph method.