NDLI: Exact and Approximate Algorithms for the Optimization of Area and Delay in Multiple Constant Multiplications

Content Provider	IEEE Xplore Digital Library
Author	Aksoy, L. da Costa, E. Flores, P. Monteiro, J.
Copyright Year	1982
Abstract	The main contribution of this paper is an exact common subexpression elimination algorithm for the optimum sharing of partial terms in multiple constant multiplications (MCMs). We model this problem as a Boolean network that covers all possible partial terms that may be used to generate the set of coefficients in the MCM instance. We cast this problem into a 0-1 integer linear programming (ILP) by requiring that the single output of this network is asserted while minimizing the number of gates representing operations in the MCM implementation that evaluate to one. A satisfiability (SAT)-based 0-1 ILP solver is used to obtain the exact solution. We argue that for many real problems, the size of the problem is within the capabilities of current SAT solvers. Because performance is often a primary design parameter, we describe how this algorithm can be modified to target the minimum area solution under a user-specified delay constraint. Additionally, we propose an approximate algorithm based on the exact approach with extremely competitive results. We have applied these algorithms on the design of digital filters and present a comprehensive set of results that evaluate ours and existing approximation schemes against exact solutions under different number representations and using different SAT solvers.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	1013
Ending Page	1026
Page Count	14
File Size	668759
File Format	PDF
ISSN	02780070
Volume Number	27
Issue Number	6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2008-06-01
Publisher Place	U.S.A.
Access Restriction	One Nation One Subscription (ONOS)
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Delay Signal processing algorithms Finite impulse response filter Algorithm design and analysis Digital signal processing Integer linear programming Approximation algorithms Digital filters Constraint optimization Fast Fourier transforms pseudo-Boolean optimization (PBO) Canonical signed digit (CSD) common subexpression elimination (CSE) delay constraints minimal signed digit (MSD) multiple constant multiplications (MCMs)
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Electrical and Electronic Engineering Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Contention Resolution—A New Approach to Versatile Subexpressions Sharing in Multiple Constant Multiplications

On the inclusion of prime factors to calculate the theoretical lower bounds in multiplierless single constant multiplications

A Common Subexpression Elimination Tree Algorithm

Contention resolution algorithm for common subexpression elimination in digital filter design

Information Theoretic Approach to Complexity Reduction of FIR Filter Design

Time-Efficient Single Constant Multiplication Based on Overlapping Digit Patterns

A novel common-subexpression-elimination method for synthesizing fixed-point FIR filters

Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression elimination

On “A New Common Subexpression Elimination Algorithm for Realizing Low-Complexity Higher Order Digital Filters”

Exact and Approximate Algorithms for the Optimization of Area and Delay in Multiple Constant Multiplications

Similar Documents

Contention Resolution—A New Approach to Versatile Subexpressions Sharing in Multiple Constant Multiplications

On the inclusion of prime factors to calculate the theoretical lower bounds in multiplierless single constant multiplications

A Common Subexpression Elimination Tree Algorithm

Contention resolution algorithm for common subexpression elimination in digital filter design

Information Theoretic Approach to Complexity Reduction of FIR Filter Design

Time-Efficient Single Constant Multiplication Based on Overlapping Digit Patterns

A novel common-subexpression-elimination method for synthesizing fixed-point FIR filters

Multiple constant multiplications: efficient and versatile framework and algorithms for exploring common subexpression elimination

On “A New Common Subexpression Elimination Algorithm for Realizing Low-Complexity Higher Order Digital Filters”

Exact and Approximate Algorithms for the Optimization of Area and Delay in Multiple Constant Multiplications