Browse Prior Art Database

Automatically Determining Precise Location of Nets and Net Nodes Given the Ordering of the Nets

IP.com Disclosure Number: IPCOM000082562D
Original Publication Date: 1974-Dec-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 3 page(s) / 23K

Publishing Venue

IBM

Related People

Dunham, B: AUTHOR [+3]

Abstract

In an article by B. Dunham and J. H. North, appearing in the IBM Technical Disclosure Bulletin, Vol. 16, No. 3, August 1973 pages 866 and 867, a wire routing method for ordering nets in a column is set forth. Before a column can be wired, it is necessary to pass from a suggested ordering of nets to a precise determination of the exact location of every net line and net node.

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 53% of the total text.

Page 1 of 3

Automatically Determining Precise Location of Nets and Net Nodes Given the Ordering of the Nets

In an article by B. Dunham and J. H. North, appearing in the IBM Technical Disclosure Bulletin, Vol. 16, No. 3, August 1973 pages 866 and 867, a wire routing method for ordering nets in a column is set forth. Before a column can be wired, it is necessary to pass from a suggested ordering of nets to a precise determination of the exact location of every net line and net node.

A rapid mode of solution would be to take the first net on the left and place it as far left as possible, to take the first net on the right and place it as far right as possible. This procedure would continue until all the nets were accounted for. The resulting arrangement would have many drawbacks, because a large number of unnecessary bends would have been introduced into the nets. This might affect not only the electrical characteristics of the column, but would also make it more difficult later to make small changes in the design, such as, for example, the deletion of certain nets and the addition of others.

A procedure is required which would find a legal positioning, given its possibility, but which would not introduce numerous unnecessary bends in the lines. The solution should also permit maximum use of the space available.

The method described has several stages. First, the leftmost net is put in, but it is not permitted that any of the lines connecting nodes be bent. Then, the rightmost net is put in (as far right as possible without bends in the node links). This process continues until all the nets are placed in some imaginary column space.

If the resultant width of the imaginary column space does not exceed the actual space permitted, the problem is completed. Otherwise, step 2 must follow. Nets are put in as before except that one small type of bend is permitted in node links, namely, elbows may be introduced at the precise level of the node, as shown in the following schematic representation:

When this step has been completed, the resultant column width is determined, the left side and right side being assumed as close together as possible. If the imaginary column is too wide, then it will be necessary to proceed to step 3. In this step, at least one net link must be bent not at the node level. The identity of this net link is determined as follows.

First, it is determined at which points (levels) the left and right side are closest. If there...