NDLI: On the crossing distribution problem

Content Provider	ACM Digital Library
Author	Song, Xiaoyu Wang, Yuke
Copyright Year	1999
Abstract	VLSI layout design is typically decomposed into four steps: placement, global routing, routing region definition, and detailed routing. The crossing distribution problem occurs prior to detailed routing [Groenveld 1989; Mared-Sadowska and Sarrafzadeh 1995; Wang and Shung 1992]. A $\textit{crossing}$ is defined as the intersection of two nets. The problem of net crossing distribution is important in layout design, such as design of dense chips, multichip modules (MCM), critical net routing, and analog circuits [Groenveld 1989; Sarrafzadah 1995; Wang and Shung 1992]. It is observed that nets crossing each other are more difficult to route than those that do not cross. The layout of crossing nets has to be realized in more than two layers and requires a larger number of $\textit{vias}$ In this paper we study the crossing distribution problem of two-terminal nets between two regions. We present an optimal O(n2) time algorithm for two-sided nets, where n is the number of nets. Our results are superior to previous ones [Markek-Sadowska and Sarrafzadeh 1995; Wang and Shung 1992]. We give an optimal O(n2) time algorithm for the crossing distribution problem with one-sided nets. We solve optimally the complete version of the crossing distribution problem for two-terminal nets in two regions that has not been studied before.
Starting Page	39
Ending Page	51
Page Count	13
File Format	PDF
ISSN	10844309
e-ISSN	15577309
DOI	10.1145/298865.298868
Volume Number	4
Issue Number	1
Journal	ACM Transactions on Design Automation of Electronic Systems (TODAES)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1999-01-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	VLSI layout Crossings
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

Rectilinear block placement using B*-trees

Analysis of FPGA/FPIC switch modules

The crossing distribution problem [IC layout]

Fast placement approaches for FPGAs

Reliable crosstalk-driven interconnect optimization

Cluster-aware iterative improvement techniques for partitioning large VLSI circuits

Power-delay optimizations in gate sizing

Timing-driven routing for symmetrical array-based FPGAs

Performance-driven placement for dynamically reconfigurable FPGAs

On the crossing distribution problem

Similar Documents

Rectilinear block placement using B*-trees

Analysis of FPGA/FPIC switch modules

The crossing distribution problem [IC layout]

Fast placement approaches for FPGAs

Reliable crosstalk-driven interconnect optimization

Cluster-aware iterative improvement techniques for partitioning large VLSI circuits

Power-delay optimizations in gate sizing

Timing-driven routing for symmetrical array-based FPGAs

Performance-driven placement for dynamically reconfigurable FPGAs

On the crossing distribution problem