The problem of multiplying by a given set of constants based on a control input has been studied to a much lesser degree in the literature than parallel multiplier blocks. One major difference to the parallel multiplier blocks is that now multiplexers are needed, which, as the add/subtracts have area requirements. We have developed a tool that generates multiplexed multiplier blocks for any set of constants and bitwidth. Below we show a general multiplexed multiplier block and a very simple example - a multiplier block for the multiplexed multiplication with the constants 11 and 21, generated by our tool.
Input: A list of integer or fixed-point constants c_1, ...,c_n.
Output: Synthesizable Verilog code and the corresponding directed acyclic graph (DAG) for the multiplier block implementing the time-multiplexed multiplications c_i*x for i=1..n. The only operations used in the generated DAG and code are additions, subtractions, multiplexers and shifts.
The Figures below show an example benchmark from [1]. It is a comparision between a baseline approach consisting of a generic multiplier and a lookup table, and the above presented dag fusion algorithm. Each point in the plots is averaged over 10 sets of randomly drawn 16 bit constants. Considerable area gains, compared to the multiplier based solution, are possible at the cost of increased latency. In the example below, for up to 18 constants our multiplier blocks use less resources than the baseline approach, despite double the latency.
Our software is available under GNU GPL license. A commercial license can be obtained on request.
Copyright (c) 2006 by Peter Tummeltshammer for the SPIRAL Project, Carnegie Mellon University
Contact: Peter Tummeltshammer, petertu AT ecs DOT tuwien DOT ac DOT at