Browse Prior Art Database

Detailed ROUTING of Multiple Power and Ground Nets on a Single Layer

IP.com Disclosure Number: IPCOM000034438D
Original Publication Date: 1989-Feb-01
Included in the Prior Art Database: 2005-Jan-27
Document File: 5 page(s) / 21K

Publishing Venue

IBM

Related People

Ho, JM: AUTHOR [+3]

Abstract

The problem of constructing a detailed routing of an arbitrary number of power, ground, and other I/O nets on a single layer is considered. The case where the number of such nets is two is discussed in [1]. A rectangle called the chip boundary, enclosing a number of rectangles called the modules, is given. On the boundary of each module, a cyclic ordering of a set of terminals is given. A set of power, ground, and other I/O pads are placed on the boundary of the chip. Each pad corresponds to a distinct power, ground or I/O net. Each terminal on the modules is assigned to a specific net, and terminals in the same net are to be connected to its assigned pad. The placement of the modules, the positions of the terminals on the modules, and the positions of the pads on the boundary are all assumed given.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 24% of the total text.

Page 1 of 5

Detailed ROUTING of Multiple Power and Ground Nets on a Single Layer

The problem of constructing a detailed routing of an arbitrary number of power, ground, and other I/O nets on a single layer is considered. The case where the number of such nets is two is discussed in [1]. A rectangle called the chip boundary, enclosing a number of rectangles called the modules, is given. On the boundary of each module, a cyclic ordering of a set of terminals is given. A set of power, ground, and other I/O pads are placed on the boundary of the chip. Each pad corresponds to a distinct power, ground or I/O net. Each terminal on the modules is assigned to a specific net, and terminals in the same net are to be connected to its assigned pad. The placement of the modules, the positions of the terminals on the modules, and the positions of the pads on the boundary are all assumed given. It is also assumed that there is a feasible routing of these nets on a single layer, and that an abstract embedding of the routing is given as input. An abstract planar embedding is simply a description of the embedding, in terms of the cyclic orderings of the incident edges at each vertex. A realization of the embedding is a non-crossing drawing, in which the orderings of the edges at the vertices in the embedding are preserved. Note that the cyclic orderings of the edges at the vertices determine the faces of the planar embedding. This problem is called the single layer multiple pad routing problem. Formally, the problem is defined as follows. Given: 1. A placement of a list of pads P = P1, P2, ... , Pp in cyclic counter-clockwise order on a rectangular

boundary; 2. A placement of 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. 4. For each Pi a linear ordering of the edges incident on

it from the modules is given. The single layer pad routing problem is to realize the pad-module connections on a single layer. This process involves the routing of the edges (wires) of the connection graph between the terminals and the pads so as to realize the faces of the abstract embedding. Such a process is also referred to as detailed routing. In this disclosure a detailed routing algorithm that runs in O(m x n) time is presented, where m is the number of modules, and n is the total number of terminals. The algorithm guarantees that the total number of turns in the routing is bounded by c x m x n for a small constant c. The algorithm routes all the wires simultaneously in the form of a "pipe," thus avoiding the mazes that can be created by a sequential insertion method. The algorithm first constructs a permutation of the modules by chaining them together. Next, it uses this chain as a pipe to carry all the wires from the pads, and thus constructs a permutation layout [2] betw...