Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression elimination

TLDR

Many DSP, telecom, graphics, and control applications involve numerous multiplications of a single variable by constants, and optimizing this multiple constant multiplication (MCM) problem can substantially improve throughput, area, and power, yet it has received little attention. The authors formulate the MCM problem by first minimizing required shifts, then minimizing additions through common subexpression elimination, and develop an efficient branch‑and‑bound algorithm for a scaling transformation. They use an iterative pairwise matching heuristic for common subexpression elimination, augment it with a preprocessing scaling transformation that reduces shifts and additions, and extend the approach to other synthesis tasks such as constant matrix‑vector multiplications, linear transforms, and polynomial evaluations. Benchmarks demonstrate the effectiveness of the proposed framework across multiple synthesis tasks.

Abstract

Many applications in DSP, telecommunications, graphics, and control have computations that either involve a large number of multiplications of one variable with several constants, or can easily be transformed to that form. A proper optimization of this part of the computation, which we call the multiple constant multiplication (MCM) problem, often results in a significant improvement in several key design metrics, such 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 elimination. The algorithm for common subexpression elimination is based on an iterative pairwise matching heuristic. The power of the MCM approach is augmented by preprocessing the computation structure with a new scaling transformation that reduces the number of shifts and additions. An efficient branch and bound algorithm for applying the scaling transformation has also been developed. The flexibility of the MCM problem formulation enables the application of the iterative pairwise matching algorithm to several other important and common high level synthesis tasks, such as the minimization of the number of operations in constant matrix-vector multiplications, linear transforms, and single and multiple polynomial evaluations. All applications are illustrated by a number of benchmarks.