NDLI: Multiway VLSI circuit partitioning based on dual net representation

Please wait, while we are loading the content...

Multiway VLSI circuit partitioning based on dual net representation

Content Provider	IEEE Xplore Digital Library
Author	Cong, J. Juan Labio, W. Shivakumar, N.
Copyright Year	1982
Abstract	In this paper, we study the area-balanced multiway partitioning problem of VLSI circuits based on a new dual netlist representation named the hybrid dual netlist (HDN), and propose a general paradigm for multiway circuit partitioning based on dual net transformation. Given a netlist, we first compute a K-way partitioning of nets based on the HDN representation, and then transform the K-way net partition into a K-way module partitioning solution. The main contribution of our paper is in the formulation and solution of the K-way module contention (KMC) problem, which determines the best assignment of the modules in contention to partitions while maintaining user-specified area requirements when we transform the net partition into a module partition. Under a natural definition of binding function between nets and modules, and preference function between partitions and modules, we show that the K-MC problem can be reduced to a min-cost max-flow problem. We present an efficient solution to the K-MC problem based on network flow computation. We apply our dual transformation paradigm to the well-known K-way Fiduccia-Mattheyses (FM) partitioning algorithm (K-FM) and show that the new algorithm, named K-DualFM, reduces the net cutsize by 20% to 31% compared with the K-FM algorithm. We also apply the same paradigm to the K-maximum fanout-free cone (MFFC)-FM algorithm, a K-FM algorithm based on MFFC clustering, and show that the resulting algorithm, K-DualMFFC-FM reduces the net cutsize by 15% to 26% compared with K-MFFC-FM. Furthermore, we compare the K-DualFM algorithm with EIG1 and Paraboli, two recently proposed spectral-based bipartitioning algorithms. We showed that K-DualFM reduces the net cutsize by 56% on average when compared with EIG1 and produces comparable results with Paraboli.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	396
Ending Page	409
Page Count	14
File Size	1548798
File Format	PDF
ISSN	02780070
Volume Number	15
Issue Number	4
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-04-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	Very large scale integration Circuits Partitioning algorithms Clustering algorithms Iterative algorithms Computer networks Computational modeling Computer science Iterative methods
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

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

Probability-based approaches to VLSI circuit partitioning

Design hierarchy-guided multilevel circuit partitioning

Network Partitioning and Ordering for MOS VLSI Circuits

GORDIAN: VLSI placement by quadratic programming and slicing optimization

MARS-a multilevel full-chip gridless routing system

A connectivity based clustering algorithm with application to VLSI circuit partitioning

A fast hierarchical quadratic placement algorithm

Robust VLSI circuit simulation techniques based on overlapped waveform relaxation

Multiway VLSI circuit partitioning based on dual net representation

Similar Documents

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

Probability-based approaches to VLSI circuit partitioning

Design hierarchy-guided multilevel circuit partitioning

Network Partitioning and Ordering for MOS VLSI Circuits

GORDIAN: VLSI placement by quadratic programming and slicing optimization

MARS-a multilevel full-chip gridless routing system

A connectivity based clustering algorithm with application to VLSI circuit partitioning

A fast hierarchical quadratic placement algorithm

Robust VLSI circuit simulation techniques based on overlapped waveform relaxation

Multiway VLSI circuit partitioning based on dual net representation