NDLI: Set-Cover Heuristics for Two-Level Logic Minimization

Content Provider	IEEE Xplore Digital Library
Author	Kagliwal, A. Balachandran, S.
Copyright Year	2012
Abstract	Given a Boolean function, the Unate-Covering Problem (UCP) is NP-hard. This problem can be modeled as a set cover problem where minterms are the elements and implicants form the sets. Traditional solutions in logic synthesis use set cover algorithms that are oblivious to the special semantic of the elements and sets. We propose three new heuristics for the set-cover problem which are aware of the relationship between implicants and minterms. We show that the proposed heuristics are effective for breaking ties when a cyclic core is obtained. We evaluate the heuristics on a set of hard instances from BHOSLIB benchmark suite. We also replace ESPRESSO's set cover algorithm using these heuristics and compare the logic synthesis results. We further map the minimized Boolean equations using ABC's technology mapping tool using 2-input NAND gates and 4-input Lookup Tables (LUTs).
Starting Page	197
Ending Page	202
File Size	182209
Page Count	6
File Format	PDF
ISBN	9781467304382
ISSN	10639667
DOI	10.1109/VLSID.2012.70
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2012-01-07
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Benchmark testing Boolean functions Logic gates Minimization Table lookup Field programmable gate arrays Heuristic algorithms ESPRESSO-II set-cover heuristic two-level logic minimization
Content Type	Text
Resource Type	Article
Subject	Electrical and Electronic Engineering Hardware and Architecture

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