NDLI: Solving the net matching problem in high-performance chip design

Content Provider	IEEE Xplore Digital Library
Author	Carragher, R.J. Chung-Kuan Cheng Xiao-Ming Xiong Fujita, M. Paturi, R.
Copyright Year	1982
Abstract	In high-performance chip design, the problem of net matching is often critical for achieving correct circuit performance. We adopt a conservative design, to route all matched nets with identical topologies and equal wire lengths to achieve zero skew. The problem is formulated as a variant of the D-dimensional Steiner tree problem. We propose a two-stage solution. The first stage uses an iterative improvement strategy to generate the Steiner tree topology for all the nets. The second stage places the nodes using one of two methods. The first approach expresses the optimal Steiner node positions as a linear programming solution, with average computational complexity O(n/sup 2/m/sup 2/), where n is the number of nets and m is the number of pins. Improved efficiency is achieved under the other approach by transforming the Manhattan metric to an l/sub /spl infin// norm using a 45/spl deg/ rotation of the solution space. The norm is then approximated by either an l/sub /spl lambda// norm, for suitably large values of /spl lambda/, or an exponential "penalty" function. The solution space in both approaches becomes strictly convex, allowing us to apply a greedy approach which converges to an optimal solution with great efficiency, leading to a dramatic speed-up versus the linear programming approach.
Sponsorship	IEEE Council on Electronic Design Automation IEEE Circuits and Systems Society
Starting Page	902
Ending Page	911
Page Count	10
File Size	1071369
File Format	PDF
ISSN	02780070
Volume Number	15
Issue Number	8
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	1996-08-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	Chip scale packaging Pins Clocks Routing Delay Circuits Wire Topology Linear programming Microelectronics
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

Wire Retiming Problem With Net Topology Optimization

Minimizing wire length in floorplanning

A performance-driven global router for custom VLSI chip design

An adaptation of the interior point method for solving the global routing problem

An Integer-Linear-Programming-Based Routing Algorithm for Flip-Chip Designs

A timing-constrained simultaneous global routing algorithm

Performance-driven channel pin assignment algorithms

Performance-Driven Dual-Rail Routing Architecture for Structured ASIC Design Style

BSG-Route: A Length-Constrained Routing Scheme for General Planar Topology

Solving the net matching problem in high-performance chip design

Similar Documents

Wire Retiming Problem With Net Topology Optimization

Minimizing wire length in floorplanning

A performance-driven global router for custom VLSI chip design

An adaptation of the interior point method for solving the global routing problem

An Integer-Linear-Programming-Based Routing Algorithm for Flip-Chip Designs

A timing-constrained simultaneous global routing algorithm

Performance-driven channel pin assignment algorithms

Performance-Driven Dual-Rail Routing Architecture for Structured ASIC Design Style

BSG-Route: A Length-Constrained Routing Scheme for General Planar Topology

Solving the net matching problem in high-performance chip design