Title :
Contention Resolution—A New Approach to Versatile Subexpressions Sharing in Multiple Constant Multiplications
Author :
Xu, Fei ; Chang, Chip-Hong ; Jong, Ching-Chuen
Author_Institution :
Xilinx Asia Pacific Pte. Ltd., Singapore
fDate :
3/1/2008 12:00:00 AM
Abstract :
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.
Keywords :
FIR filters; digital signal processing chips; benchmark filters; coefficient sets; contention resolution algorithm; cost function evaluation; digital signal processing; multiple constant multiplications; reusable common subexpressions; suboptimal common subexpressions; versatile subexpressions sharing; Canonical Signed Digit; Canonical signed digit (CSD); Common Subexpression Elimination; Finite Impulse Response Filter; Multiple Constant Multiplication; common subexpression elimination (CSE); finite-impulse response (FIR) filter; multiple constant multiplication (MCM);
Journal_Title :
Circuits and Systems I: Regular Papers, IEEE Transactions on
DOI :
10.1109/TCSI.2007.913707