NDLI: Recursive bi-partitioning of netlists for large number of partitions

Content Provider	IEEE Xplore Digital Library
Author	Drechsler, R. Gunther, W. Eschbach, T. Linhard, L. Angst, G.
Copyright Year	2002
Description	Author affiliation: Inst. of Comput. Sci., Bremen Univ., Germany (Drechsler, R.)
Abstract	In many application in VLSI CAD, a given netlist has to be partitioned into smaller sub-designs which can be handled much better. In this paper we present a new recursive bi-partitioning algorithm that is especially applicable, if a large number of final partitions, e.g. more than 1000, has to be computed. The algorithm consists of two steps. Based on recursive splits the problem is divided into several sub-problems, but with increasing recursion depth more run time is invested. By this an initial solution is determined very fast. The core of the method is a second step, where a very powerful greedy algorithm is applied to refine the partitions. Experimental results are given that compare the new approach to state-of-the-art tools. The experiments show that the new approach outperforms the standard techniques with respect to run time and quality. Furthermore, the memory usage is very low and is reduced in comparison to other methods by more than a factor of four.
Starting Page	38
Ending Page	44
File Size	378610
Page Count	7
File Format	PDF
ISBN	0769517900
DOI	10.1109/DSD.2002.1115349
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2002-09-04
Publisher Place	Germany
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Partitioning algorithms Computer science Very large scale integration Field programmable gate arrays Algorithm design and analysis Application software Greedy algorithms Design automation Design optimization Routing
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

MARS-a multilevel full-chip gridless routing system

Thumbnail rectilinear Steiner trees

Segmented channel routing

Incremental CAD

Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement

Field Programmable Gate-Arrays

A genetic local search hybrid architecture for VLSI circuit partitioning

MR: a new framework for multilevel full-chip routing

Architecture driven k-way partitioning for multichip modules

Recursive bi-partitioning of netlists for large number of partitions

Similar Documents

MARS-a multilevel full-chip gridless routing system

Thumbnail rectilinear Steiner trees

Segmented channel routing

Incremental CAD

Seeing the Forest and the Trees: Steiner Wirelength Optimization in Placement

Field Programmable Gate-Arrays

A genetic local search hybrid architecture for VLSI circuit partitioning

MR: a new framework for multilevel full-chip routing

Architecture driven k-way partitioning for multichip modules

Recursive bi-partitioning of netlists for large number of partitions