Browse Prior Art Database

Planarity Testing of Multiple Power And Ground Nets

IP.com Disclosure Number: IPCOM000099650D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 6 page(s) / 256K

Publishing Venue

IBM

Related People

Ho, JM: AUTHOR [+3]

Abstract

A number of power, ground, and I/O pads on the boundary of a chip is given. This boundary encloses a number of modules. On the boundary of each module, a cyclic ordering of a set of terminals is given. Each terminal on the modules is assigned to a net corresponding to a specific pad. Terminals in the same net are to be connected to the assigned pad. The problem is to test whether a planar routing of these nets exists.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 26% of the total text.

Planarity Testing of Multiple Power And Ground Nets

       A number of power, ground, and I/O pads on the boundary
of a chip is given.  This boundary encloses a number of modules. On
the boundary of each module, a cyclic ordering of a set of terminals
is given.  Each terminal on the modules is assigned to a net
corresponding to a specific pad. Terminals in the same net are to be
connected to the assigned pad.  The problem is to test whether a
planar routing of these nets exists.

      A formal statement of the problem is as follows:
Given:
1.   A list of pads P = P1, P2, ... , Pp in cyclic counterclockwise
order on a rectangular boundary;
2.   A set M = M1, M2, ... , Mm of rectangular modules inside the
rectangular boundary;
3.   For each Mi a list Ci of terminals is given in cyclic counter-
clockwise order on its boundary, to be connected to specified pads.
Let the total number of terminals be n.
An edge connecting pad Pj to module Mi is labeled as (Mi, Pj).
The underlying connection graph G(V, E) is defined by:
1.   V = P    M;
2.   E = {(Pp, P1)}    {(Pi, Pi+1)¯1 & i & p-1}    {(Mi, Pj)¯Mi and
Pj are to be connected};
3.   For each module Mi a cyclic ordering Ci of the set of edges Ei
= {(Mi, Pj)¯(Mi, Pj) e E} is also given.

      The problem is to test whether the graph G has a planar
embedding which preserves the specified cyclic orderings Ci of the
edges incident at each module Mi, such that the pads appear on the
external face of the embedding in the cyclic order given by the list
P.  A linear time algorithm for this problem can be derived from the
modification in (1) of the general planarity testing algorithm of
(2).  However, the special structure of the connection graph in the
pad routing problem implies a simple necessary and sufficient
condition for the existence of a planar routing.  A similar condition
for the case of only two nets is given in (3).  A simple linear time
algorithm for checking this necessary and sufficient condition is
given here.

      It is assumed that no two terminals on the same module need be
connected to the same pad.  This is not a restriction, because if
more than one terminal needs to be connected to the same pad, then
these terminals must appear consecutively in the cyclic order on the
module boundary, otherwise the connection graph is not planar (3).
Therefore, these terminals can be bunched logically into one
terminal.

      A module Mi is said to be consistent with the chain of pads P
if its cyclic ordering of edges Ci is a sub-ordering of P.

      A pair of modules Mi and Mj is said to interleave, if their
respective cyclic orderings of edges Ci and Cj, and the chain of pads
P satisfy one of the following conditions: 1.   Ci= ...Pa ...Pc
...;Cj= ...Pb ...Pd ...;P= ...Pa ...Pb

      ...Pc ...Pd ..., or 2.   Ci= ...Pa ...Pb ...Pd ...;Cj= ...Pa
...Pb ...Pc ...;P=
      ...Pa ...Pb ...Pc ...  Pd ...;
      Here Pc may be...