Browse Prior Art Database

Line Ordering Program Which Cleaves Data Into Streets and then Eliminates Waste Spots

IP.com Disclosure Number: IPCOM000079670D
Original Publication Date: 1973-Aug-01
Included in the Prior Art Database: 2005-Feb-26
Document File: 2 page(s) / 15K

Publishing Venue

IBM

Related People

Dunham, B: AUTHOR [+2]

Abstract

In certain wire routing problems, space is lost if lines must bend get around obstacles, particularly if several lines must bend in parallel. Space can also be lost if a line must pass between two obstacles located on consecutive levels, since the two obstacles cannot then mesh together. Hence, if a number of nets running essentially in parallel on a single surface of limited width are to be ordered, each net composed of two or more nodes, each node covering a number of wiring channels, it is important that the ordering achieved avoid waste space, particularly at those levels where possible waste is limited.

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

Page 1 of 2

Line Ordering Program Which Cleaves Data Into Streets and then Eliminates Waste Spots

In certain wire routing problems, space is lost if lines must bend get around obstacles, particularly if several lines must bend in parallel. Space can also be lost if a line must pass between two obstacles located on consecutive levels, since the two obstacles cannot then mesh together. Hence, if a number of nets running essentially in parallel on a single surface of limited width are to be ordered, each net composed of two or more nodes, each node covering a number of wiring channels, it is important that the ordering achieved avoid waste space, particularly at those levels where possible waste is limited.

The method described here deals with this problem by first assigning the nets to "streets", a process called "cleaving".

First, there is preliminary cleaving, no street being permitted more than one net node at a given level. The algorithm always assigns next that candidate net which has the least number of possible streets available to it. Among equals, it selects the net having the most nodes first. If more than one street is available, the method assigns the net to that street which already contains the most nodes.

This preliminary cleaving step usually results in a number of rather densely packed streets, there being a small overflow of nets assigned a final street. Sometimes, it is a good strategy to reassign the overflow nets in that final street back into the densely packed streets, relaxing the rule that no street is permitted more than one node at a given level.

The design method next deals with the individual streets, testing whether there is a possible ordering of the nets which avoids loss (within the street) because a line at some point passes between nodes on consecutive levels. Call such an occurrence an "opposition". Some oppositions are more acceptable than others, since the available space for maneuvering may vary from level-to-level. The objective, therefore, is to order the nets in a subject street in such a way that no unacceptable oppositions occur.

If no such satisfactory ordering is possible, one of the contributory nets can be placed in some other street, or else traded with an acceptable net from some other street. The immediate problem, then, is to provide an efficient way of determining whether, for a given collection of nets in a street, a satisfactory ordering is possible.

Since the number of nets can be quite large, sheer exhaustion is infeasible. First, all potential oppositions are noted, that is, cases where two different nets have nodes on consecutive levels, there being other nets which pass those levels. A so-called "exclusion clause" is formed which simply states, for example, that nets A and B exclude nets F, G, and H. This exclusion clause means that nets A and B have nodes on c...