Efficient substitution of multiple constant multiplications by shifts and additions using iterative pairwise matching

1 January 1994

proceedings article
Published by Association for Computing Machinery (ACM)

p. 189-194
https://doi.org/10.1145/196244.196343

Abstract

Many numerically intensive applications have computations that involve a large number of multiplications of one variable with several constants. 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. After defining the MCM problem, we formulate it as a special case of common subexpression elimination. The algorithm for common subexpression elimination is based on an iterative pairwise matching heuristic. The flexibility of the MCM problem formulation enables the application of the iterative pairwise matching algorithm to several other important high level synthesis tasks. All applications are illustrated by a number of benchmarks.

Keywords

This publication has 0 references indexed in Scilit: