NDLI: An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications

Content Provider	IEEE Xplore Digital Library
Author	Flores, P. Monteiro, J. Costa, E.
Copyright Year	2005
Description	Author affiliation: IST-INESC-ID, Lisboa, Portugal (Flores, P.; Monteiro, J.)
Abstract	In this paper, we propose an exact algorithm that maximizes the sharing of partial terms in multiple constant multiplication (MCM) operations. We model this problem as a Boolean network that covers all possible partial terms which may be used to generate the set of coefficients in the MCM instance. The PIs to this network are shifted versions of the MCM input. An AND gate represents an adder or a subtracter, i.e., an AND gate generates a new partial term. All partial terms that have the same numerical value are ORed together. There is a single output which is an /spl and/ over all the coefficients in the MCM. We cast this problem into a 0-1 integer linear programming (ILP) problem by requiring that the output is asserted while minimizing the total number of AND gates that evaluate to one. A SAT-based 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. We present results using binary, CSD and MSD representations. Two main conclusions can be drawn from the results. One is that, in many cases, existing heuristics perform well, computing the best solution, or one close to it. The other is that the flexibility of the MSD representation does not have a significant impact in the solution obtained.
Starting Page	13
Ending Page	16
File Size	212212
Page Count	4
File Format	PDF
ISBN	078039254X
DOI	10.1109/ICCAD.2005.1560032
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2005-11-06
Publisher Place	USA
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Finite impulse response filter Hardware Digital signal processing Integer linear programming Fast Fourier transforms Computer architecture Energy consumption Signal processing algorithms
Content Type	Text
Resource Type	Article

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

Maximal sharing of partial terms in MCM under minimal signed digit representation

An Exact Breadth-First Search Algorithm for the Multiple Constant Multiplications Problem

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

An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications

FFT hardware accelerator

Maximal Sharing of Partial Terms in Multiple Constant Multiplications: Analysis of an Exact Algorithm (2005)

Multiple FIR filters on a finite ring

A genetic algorithm for the optimisation of a reconfigurable pipelined FFT processor

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

An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications

Similar Documents

Maximal sharing of partial terms in MCM under minimal signed digit representation

An Exact Breadth-First Search Algorithm for the Multiple Constant Multiplications Problem

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

An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications

FFT hardware accelerator

Maximal Sharing of Partial Terms in Multiple Constant Multiplications: Analysis of an Exact Algorithm (2005)

Multiple FIR filters on a finite ring

A genetic algorithm for the optimisation of a reconfigurable pipelined FFT processor

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

An exact algorithm for the maximal sharing of partial terms in multiple constant multiplications