NDLI: Minimum replication min-cut partitioning

Content Provider	IEEE Xplore Digital Library
Author	Wai-Kei Mak Wong, D.F.
Copyright Year	1982
Abstract	Logic replication has been shown to be very effective in reducing the number of cut nets in partitioned circuits. Liu et al. (see IEEE Trans. Computer-Aided Design, vol. 14, p. 623-30, May 1995) considered the circuit partitioning problem with logic replication for separating two given nodes and presented an algorithm to determine a partitioning of the minimum possible cut size. In general, there are many possible partitioning solutions with the minimum cut size and the difference in the required amount of replication by these solutions can be significant. Since there is a size constraint on each component of the partitioning in practice, it is desirable to also minimize the amount of replication. In this paper, we present a network-flow based algorithm to determine an optimum replication min-cut partitioning that requires minimum replication. We show that the algorithm can be generalized to separate two given subsets of nodes giving an optimum partitioning of the minimum possible cut size using the least possible amount of replication. We also show that our algorithm can be used to improve the solutions produced by any existing size-constrained replication min-cut partitioning algorithm by reducing the cut size and shrinking the replication set.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	1221
Ending Page	1227
Page Count	7
File Size	234660
File Format	PDF
ISSN	02780070
Volume Number	16
Issue Number	10
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1997-10-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	Partitioning algorithms Logic circuits Very large scale integration Costs
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

A replication cut for two-way partitioning

Optimal min-area min-cut replication in partitioned circuits

Min-cut floorplacement

Net Cluster: A Net-Reduction-Based Clustering Preprocessing Algorithm for Partitioning and Placement

An evaluation of bipartitioning techniques

Bipartite Folding and Partitioning of a PLA

Ratio cut partitioning for hierarchical designs

Wirelength minimization for min-cut placements via placement feedback

Evaluation and optimization of replication algorithms for logic bipartitioning

Minimum replication min-cut partitioning

Similar Documents

A replication cut for two-way partitioning

Optimal min-area min-cut replication in partitioned circuits

Min-cut floorplacement

Net Cluster: A Net-Reduction-Based Clustering Preprocessing Algorithm for Partitioning and Placement

An evaluation of bipartitioning techniques

Bipartite Folding and Partitioning of a PLA

Ratio cut partitioning for hierarchical designs

Wirelength minimization for min-cut placements via placement feedback

Evaluation and optimization of replication algorithms for logic bipartitioning

Minimum replication min-cut partitioning