Browse Prior Art Database

Wiring Multinode Nets

IP.com Disclosure Number: IPCOM000047972D
Original Publication Date: 1983-Dec-01
Included in the Prior Art Database: 2005-Feb-08
Document File: 4 page(s) / 83K

Publishing Venue

IBM

Related People

Kurtzberg, JM: AUTHOR [+2]

Abstract

A procedure is described herein for efficiently generating good multinode Steiner nets. Since the problem of finding minimal length Steiner trees is NP-complete 1, heuristic approaches must be employed. The approach disclosed here has the advantage of being computationally efficient and in practice leads to good nets, namely, those that are of near minimal cost. Of particular interest is the wiring of custom chips, and the procedure is given in terms of this task. Wiring a chip requires interconnecting a large number of sets of pins to form nets using a minimal amount of wire and as few vias as possible.

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

Page 1 of 4

Wiring Multinode Nets

A procedure is described herein for efficiently generating good multinode Steiner nets. Since the problem of finding minimal length Steiner trees is NP-complete 1, heuristic approaches must be employed. The approach disclosed here has the advantage of being computationally efficient and in practice leads to good nets, namely, those that are of near minimal cost. Of particular interest is the wiring of custom chips, and the procedure is given in terms of this task. Wiring a chip requires interconnecting a large number of sets of pins to form nets using a minimal amount of wire and as few vias as possible. For the purposes of this disclosure, it is assumed that the wiring on the chip is rectilinear, that is, the distance between two points p1 and p2 is D(p1,p2)= x1-x2 + y1-y2 and the connected net is in the form of a Steiner tree. For custom chips, the problem is complicated by the fact that the shortest rectilinear distance between two pins is not necessarily given by the sum of the direct horizontal and vertical distances between them, due to the possibility of intervening blockages. In [2] a method is given for partitioning a chip into wiring channel regions by consideration of the geometric placement of the macros. The chip is then modelled by an edge-weighted graph, with the vertices representing the wiring regions and the edges the possible connections between regions and between wiring levels. The weights, or costs, associated with the edges are a function of the distance between regions (or of the cost of making a via between levels) and the number of available wiring tracks. Routing a wire is accomplished by selecting a minimum cost sequence of adjacent vertices on the graph to form a path between terminal vertices that are associated with wiring pins 3.Ù The cost of a particular net is the sum of the costs on the selected edges. In the method presented here, a multinode net is wired in two phases. First, a pair of pins is selected and a segment connecting them is generated. Next, the remaining pins are sequentially selected and adjoined one at a time to the partial net recursively formed. The (statistically) best choice for the first two pins so as to minimize the expected final net length is to select that pair of pins that meets the following criteria: 1. The path connecting them is relatively determined, thereby preventing an unduly adverse decision about the particular routing of the connection between this pair (made in the absence of information about the structure of the net connecting the remainder of the pins). 2. The pair is separated by the maximum distance whenever there is no (or little) path variation possible in shortest-distance routing. In general, there is more than one minimum-cost routing to connect the first pair of pins. A poor choice of routing for this pair can inflict a penalty in length in the connection to the next pin. Fig. 1 illustrates this penalty. An expression for the...