Contention resolution : a new approach to versatile subexpressions sharing in multiple constant multiplications
Chang, Chip Hong
Jong, Ching Chuen
Date of Issue2008
School of Electrical and Electronic Engineering
Xilinx Asia Pacific Pte Ltd
Multiple constant multiplications (MCM) have been a core operation in many digital signal processing applications. In this paper, an efficient generalized contention resolution algorithm (CRA) is proposed to eliminate three broad categories of reusable common subexpressions in MCM. The idea is to revert a precedential decision of suboptimal common subexpressions by a localized cost function evaluation when there is a conflict between two competitive subexpressions. The proposed derivatives of the basic CRA are versatile in that they are capable of satisfying search for both intra- and intercoefficient subexpressions, in any legitimate composition of horizontal, vertical and oblique subexpressions. As the algorithms expand the common subexpressions to higher-weight only when there is cost saving, the logic depth can be controlled by constraining the weights of the subexpressions. The variants of CRA follow an important tenet of good heuristic that significant improvement in the solution quality is attained with increased problem size but the computational time remains well bounded. Experimental results with both benchmark filters and randomly generated coefficient sets are analyzed and compared with a number of well known common subexpression elimination methods to demonstrate the effectiveness and efficiency of our proposed approach.
DRNTU::Engineering::Electrical and electronic engineering
IEEE transactions on circuits and systems—I
© 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. http://www.ieee.org/portal/site This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.