An Optimal and Practical Approach to Single Constant Multiplication

作者：Thong Jason^*; Nicolici Nicola

来源：IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2011, 30(9): 1373-1386.

DOI：10.1109/TCAD.2011.2153853

• Common subexpression elimination
• directed acyclic graphs
• optimal algorithm
• single constant multiplication

We propose an exact solution to the single constant multiplication (SCM) problem. Existing optimal algorithms are limited to constants of up to 19 bits. Our algorithm requires less than 10 s on average to find a solution for a 32 bit constant. Optimality is guaranteed via an exhaustive search. We analyze two common SCM frameworks and the corresponding search strategies that each framework facilitates. Combining the strengths of both frameworks, we obtain highly aggressive pruning. The various strategies used in our algorithm and their underlying intuition are discussed extensively in this paper.

• 出版日期2011-9