Levent Aksoy
ABSTRACT
Multiple constant multiplications (MCM) problem that is to obtain the minimum number of addition/subtraction operations required to implement the constant multiplications finds itself and its variants in many applications, such as finite impulse response (FIR) filters, linear signal transforms, and computer arithmetic. There have been a number of efficient algorithms proposed for the MCM problem. However, due to the NP-hardness of the problem, the proposed algorithms have been heuristics and cannot guarantee the minimum solution. In this paper, we introduce an approximate algorithm that can ensure the minimum solution on more instances than the previously proposed heuristics and can be extended to an exact algorithm using an exhaustive search. The approximate algorithm has been applied on a comprehensive set of instances including FIR filter and randomly generated hard instances, and compared with the previously proposed efficient heuristics. It is observed from the experimental results that the proposed approximate algorithm finds competitive and better results than the prominent heuristics.
- L. Aksoy, E. Costa, P. Flores, and J. Monteiro. Minimum Number of Operations under a General Number Representation for Digital Filter Synthesis. In ECCTD, pages 252--255, 2007.Google Scholar
Cross Ref
- D. Bull and D. Horrocks. Primitive Operator Digital Filters. IEE Proceedings G: Circuits, Devices and Systems, 138(3):401--412, 1991.Google ScholarCross Ref
- P. Cappello and K. Steiglitz. Some Complexity Issues in Digital Signal Processing. IEEE Transactions on Acoustics, Speech, and Signal Processing, 32(5):1037--1041, 1984.Google ScholarCross Ref
- E. Costa, P. Flores, and J. Monteiro. Exploiting General Coefficient Representation for the Optimal Sharing of Partial Products in MCMs. In SBCCI, pages 161--166, 2006. Google ScholarDigital Library
- A. Dempster, S. Demirsoy and I. Kale. Designing Multiplier Blocks with Low Logic Depth. In ISCAS, pages 773--776, 2002.Google ScholarCross Ref
- A. Dempster and M. Macleod. Constant Integer Multiplication using Minimum Adders. IEE Proceedings - Circuits, Devices, and Systems, 141(5):407--413, 1994.Google ScholarCross Ref
- A. Dempster and M. Macleod. Use of Minimum-Adder Multiplier Blocks in FIR Digital Filters. IEEE Transactions on Circuits and Systems II , 42(9):569--577, 1995.Google ScholarCross Ref
- A. Dempster and M. Macleod. Digital Filter Design using Subexpression Elimination and All Signed-Digit Representations. In ISCAS, pages 169--172, 2004.Google ScholarCross Ref
- P. Flores, J. Monteiro, and E. Costa. An Exact Algorithm for the Maximal Sharing of Partial Terms in Multiple Constant Multiplications. In ICCAD, pages 13--16, 2005. Google ScholarDigital Library
- O. Gustafsson. Lower Bounds for Constant Multiplication Problems. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 54(11):974--978, 2007.Google ScholarCross Ref
- O. Gustafsson, A. Dempster and L. Wanhammar. Extended Results for Minimum-adder Constant Integer Multipliers. In ISCAS, pages 73--76, 2002.Google ScholarCross Ref
- O. Gustafsson and L. Wanhammar. ILP Modelling of the Common Subexpression Sharing Problem. In ICECS, pages 1171--1174, 2002.Google ScholarCross Ref
- R. Hartley. Subexpression Sharing in Filters using Canonic Signed Digit Multipliers. IEEE Transactions on Circuits and Systems II , 43(10):677--688, 1996.Google ScholarCross Ref
- H-J. Kang and I-C. Park. FIR Filter Synthesis Algorithms for Minimizing the Delay and the Number of Adders. IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, 48(8):770--777, 2001.Google ScholarCross Ref
- H. Nguyen and A. Chatterjee. Number-Splitting with Shift-and-Add Decomposition for Power and Hardware Optimization in Linear DSP Synthesis. IEEE Transactions on VLSI , 8(4):419--424, 2000. Google ScholarDigital Library
- R. Pasko, P. Schaumont, V. Derudder, S. Vernalde, and D. Durackova. A New Algorithm for Elimination of Common Subexpressions. IEEE Transactions on Computer-Aided Design of Integrated Circuits, 18(1):58--68, 1999. Google ScholarDigital Library
- Spiral webpage. http://www.spiral.net.Google Scholar
- Y. Voronenko and M. Puschel. Multiplierless Multiple Constant Multiplication. ACM Transactions on Algorithms, 3(2), 2007. Google ScholarDigital Library
Index Terms
- An approximate algorithm for the multiple constant multiplications problem
Recommendations
Search algorithms for the multiple constant multiplications problem: Exact and approximate
This article addresses the multiplication of one data sample with multiple constants using addition/subtraction and shift operations, i.e., the multiple constant multiplications (MCM) operation. In the last two decades, many efficient algorithms have ...
Exact and approximate algorithms for discounted {0-1} knapsack problem
The Discounted {0-1} Knapsack Problem (D{0-1}KP) is an extension of the classical 0-1 knapsack problem (0-1 KP) that consists of selecting a set of item groups where each group includes three items and at most one of the three items can be selected. The ...
A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem
The generalized quadratic multiple knapsack problem is studied.A multi-start iterated local search algorithm is developed for its solution.The algorithm combines an adaptive perturbation mechanism with local search.35 out of 48 best known solutions are ...
Reviews
Paparao S Kavalipati
Efficient synthesis of register transfer level (RTL) arithmetic operations is critical for the performance of data-processing hardware. Multipliers are crucial among all such operators. Multiplication of a variable with a single integer constant can be implemented using addition, subtraction, and shifts. When a variable is multiplied with a set of constants, the sharing of these add/subtract/shift operations becomes possible, but determining an optimal combination of those operations is nondeterministic polynomial time (NP) complete. Aksoy and Gunes introduce an approximate graph-based algorithm that improves on earlier published methods for this multiple constant multiplications (MCM) problem. The paper is well written and provides a short overview of the relevant background material. The notation is from earlier work, using an MCM formulation that is based on minimizing the number of A -operations. The authors refer to an earlier heuristic, "Hcub," that is considered to be better than previous methods. It provides an improved graph-based approach, where all the target and intermediate constants are synthesized at the end, rather than synthesizing the target constants one at a time. Section 3 describes the core contribution of the paper: the algorithm ApproximateSearch. The presentation style is good, but Step 11 of the algorithm seems redundant given the assignment at Step 9. Section 4 shows convincing evidence of the merits of the proposed method, but still "Hcub" is reportedly better in 173 of the 1,890 total instances considered. Therefore, it appears that there is further room for improvement and research. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments