Surety is performing system maintenance this weekend. Electronic date stamps on new Prior Art Database disclosures may be delayed.
Browse Prior Art Database

A Method for Enabling Planarity Compliance in Global Routing

IP.com Disclosure Number: IPCOM000198654D
Publication Date: 2010-Aug-11
Document File: 1 page(s) / 52K

Publishing Venue

The IP.com Prior Art Database


A method is disclosed for enabling planarity compliance in global routing.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 85% of the total text.

Page 1 of 1

A Method for Enabling Planarity Compliance in Global Routing

Disclosed is a method for enabling planarity compliance in global routing.

In accordance with the method disclosed herein, a netlist is partitioned into a set of disjoint classes, in which each class of nets shares a common assignment to layer ranges. Subsequently, projection process is decomposed into a series of progressive problem expansions, in which each independent stage is spawned to a self-contained invocation to the global router as shown in fig.1. As routes for each class of nets are determined, they are locked and subsequently modelled as blockages to prevent ripup-and-reroute in future iterations. Aggregated capacity is gradually increased as new layer ranges are incorporated into the global 2D projection. A final solution is obtained by a concatenation of routes determined during intermediate phases of the algorithm.

Figure 1

In contrast to existing techniques, a faithful aggregation of routing resource is maintained during the global routing flow for ensuring planar compliance in the final solution. The approach disclosed herein may be applied to a black-box global router that has no immediate knowledge of layer directives.

The following pseudocode reflects the approach:

PLANES-compliant-global-routing() {

Partition netlist into classes based on layer directives

Sort partitions in decreasing order of range lower-bound

Set locked


routes {}

For each class i

Form sub-

problem with:

nets = c...