Multiple Constant Multiplication: From Target Constants to Optimized Pipelined Adder Graphs

Multiple Constant Multiplication (MCM) is a ubiquitous problem for numerous computation-intensive applications. A standard and efficient approach is to replace generic multipliers by multiplierless architectures based on bit-shifts and additions. The adder graphs describing the multiplierless circuits can be optimized according to various metrics, in particular improving throughput by pipelining. In this paper, we improve the state-ofthe-art for the design of pipelined adder graphs by searching for an optimal solution directly from target coefficients. In contrast to existing approaches, which are based on fixed adder graphs or heuristics, our solution is to describe the complete design space with Mixed-Integer Linear Programming (MILP). This results in an optimization model that can be solved to find optimal adder graphs and prove the optimality of the solutions thanks to the efficiency of modern MILP solvers. Mathematical modeling allows for an easily extendable tool which can target FPGAs and ASICs and adapt to evolving hardware models/metrics. With this work, we provide a modular framework to automate the design of adder graph-based circuits with exact optimization. The experiments demonstrate efficiency of our approach which fuses multiple design steps into a single problem