Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Net Absorption as a Wire Routing Technique

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

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, pp. 866-867 a wire routing method was set forth for ordering nets so as to avoid loss of space. In particular, the method tested whether there was a possible ordering of the nets which avoided loss because a line at some point passed between nodes on consecutive levels, an occurrence referred to as an "opposition". Because available space may vary from level-to-level, the objective is to order the nets under consideration in such a way that no unacceptable oppositions occur. Since the number of nets can be quite large, sheer exhaustion of the different possible orderings is unfeasible.

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

Page 1 of 2

Net Absorption as a Wire Routing Technique

In an article by B. Dunham and J. H. North, appearing in the IBM Technical Disclosure Bulletin, Vol. 16, No. 3, August 1973, pp. 866-867 a wire routing method was set forth for ordering nets so as to avoid loss of space. In particular, the method tested whether there was a possible ordering of the nets which avoided loss because a line at some point passed between nodes on consecutive levels, an occurrence referred to as an "opposition". Because available space may vary from level-to-level, the objective is to order the nets under consideration in such a way that no unacceptable oppositions occur. Since the number of nets can be quite large, sheer exhaustion of the different possible orderings is unfeasible.

The method first required a noting of all potential oppositions, 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 consecutive levels and that nets F, G, and H overlap the region in question.

An ordering such as GAFBH would violate the exclusion clause because F comes between A and B. Thus, the problem of finding a satisfactory ordering for a body of nets can be reduced to the problem of finding a sequence of letters, followed by one or more additional letters. The following may be taken as a typical set of exclusion clauses:. (1) AR-S (to be read: A and R exclude S) (2) FY-ARS (3) FY-ARS (4) FR-ASY (5) HR-AFSY (6) HL-ACFRSY (7) CL-AFHRSY
(8) CS-AFHLRY (9) AR-HY.

Now the purpose of the "absorption" step is to cut down on the extent and complexity of the exclusion clauses which must be satisfied if a satisfactory ordering is to be achieved, thereby reducing the overall computation required. It involves treating two nets temporarily as one. Such a maneuver could not, of course, introduce a new opposition into the problem; but it might, if not properly restricted, conceal from the calculation one already there.

The precise rule is as follows: A may be absorbed by B if A confronts B Sand B only) and A is not excluded by B in combination with more than one other net. The general effect of step-by-step application of this rule can be seen when it is applied to the exclusion clauses listed above. At each step all duplications an...