NDLI: Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs

Content Provider	ACM Digital Library
Author	Antreich, Kurt J. Schlichtmann, Ulf Wurth, Bernd Eckl, Klaus
Copyright Year	1999
Abstract	Functional decomposition is an important technique for technology mapping to look up table-based FPGA architectures. We present the theory of and a novel approach to functional disjoint decomposition of multiple-output functions, in which common subfunctions are extracted during technology mapping. While a Boolean function usually has a very large number of subfunctions, we show that not all of them are useful for multiple-output decomposition. We use a partition of the set of bound set vertices as the basis to compute $\textit{preferable}$ decomposition functions, which are sufficient for an optimal multiple-output decomposition. We propose several new algorithms that deal with central issues of functional multiple-output decomposition. First, an efficient algorithm to solve the variable partitioning problem is described. Second, we show how to implicitly compute all preferable functions of a single-output function and how to identify all common preferable functions of a multiple-output function. Due to implicit computation in the crucial steps, the algorithm is very efficient. Experimental results show significant reductions in area.
Starting Page	313
Ending Page	350
Page Count	38
File Format	PDF
ISSN	10844309
e-ISSN	15577309
DOI	10.1145/315773.315783
Volume Number	4
Issue Number	3
Journal	ACM Transactions on Design Automation of Electronic Systems (TODAES)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Boolean functions FPGA technology TOS Assignable functions Computer-aided design of VLSI Decomposition Implicit BDD-based methods Mapping synthesis Multiple-output decomposition Preferable functions Subfunction sharing gain Subfunction sharing potential Variable partitioning for decomposition
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications Electrical and Electronic Engineering

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

Post-placement bdd-based decomposition for FPGAs

Optimality study of logic synthesis for LUT-based FPGAs

New approach of exploiting symmetry in SAT-based Boolean matching for FPGA technology mapping

FPGA technology mapping optimization by rewiring algorithms

Efficient SAT-based Boolean matching for FPGA technology mapping

Technology mapping for TLU FPGAs based on decomposition of binary decision diagrams

A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs

FPGA area reduction by multi-output function based sequential resynthesis

Notes on Complexity of the lookup-table minimization problem for FPGA technology mapping

Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs

Similar Documents

Post-placement bdd-based decomposition for FPGAs

Optimality study of logic synthesis for LUT-based FPGAs

New approach of exploiting symmetry in SAT-based Boolean matching for FPGA technology mapping

FPGA technology mapping optimization by rewiring algorithms

Efficient SAT-based Boolean matching for FPGA technology mapping

Technology mapping for TLU FPGAs based on decomposition of binary decision diagrams

A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs

FPGA area reduction by multi-output function based sequential resynthesis

Notes on Complexity of the lookup-table minimization problem for FPGA technology mapping

Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs