MULTIPLE CONSTANT MULTIPLICATIONS - EFFICIENT AND VERSATILE FRAMEWORKAND ALGORITHMS FOR EXPLORING COMMON SUBEXPRESSION ELIMINATION

Many applications in DSP, telecommunications, graphics, and control ha ve computations that either involve a large number of multiplications of one variable with several constants, or can easily be transformed t o that form. A proper optimization of this part of the computation, wh ich we call the multiple constant multiplication (MCM) problem, often results in a significant improvement in several key design metrics, su ch as throughput, area, and power. However, until now little attention has been paid to the MCM problem. After defining the MCM problem, we introduce an effective problem formulation for solving it where first the minimum number of shifts that are needed is computed, and then the number of additions is minimized using common subexpression eliminati on. The algorithm for common subexpression elimination is based on an iterative pairwise matching heuristic. The power of the MCM approach i s augmented by preprocessing the computation structure with a new scal ing transformation that reduces the number of shifts and additions. An efficient branch and bound algorithm for applying the scaling transfo rmation has also been developed. The flexibility of the MCM problem fo rmulation enables the application of the iterative pairwise matching a lgorithm to several other important and common high level synthesis ta sks, such as the minimization of the number of operations in constant matrix-vector multiplications, linear transforms, and single and multi ple polynomial evaluations. All applications are illustrated by a numb er of benchmarks.