Browse Prior Art Database

Estimating Chip Wirability by Routing Configuration Averaging

IP.com Disclosure Number: IPCOM000047304D
Original Publication Date: 1983-Oct-01
Included in the Prior Art Database: 2005-Feb-07
Document File: 4 page(s) / 23K

Publishing Venue

IBM

Related People

Kurtzberg, JM: AUTHOR [+2]

Abstract

It is desirable to be able to evaluate a particular placement of macros on a semiconductor chip in terms of its wirability prior to an actual wiring. A procedure is described for estimating expected critical areas of congestion, with particular application toward custom chip designs. In 1 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 the cost of making a via between levels) and the number of available wiring tracks.

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

Page 1 of 4

Estimating Chip Wirability by Routing Configuration Averaging

It is desirable to be able to evaluate a particular placement of macros on a semiconductor chip in terms of its wirability prior to an actual wiring. A procedure is described for estimating expected critical areas of congestion, with particular application toward custom chip designs. In 1 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 the cost of making a via between levels) and the number of available wiring tracks. The notion of the graph model is here employed in estimating expected areas of congestion. For all the wires, a shortest route path algorithm 2 is used to find minimum cost routes on the graph. A routing configuration is an assignment of wires to the wiring regions specifying routes for all the nets and is characterized by the wire usage of each region. The costs on the edges of the graph are modified on the basis of the wire usage, namely, edges associated with highly congested regions are assigned a high cost. A new routing configuration is then found by the use of the same path-finding algorithm operating on the modified edge costs, thereby tending to avoid regions of previous heavy congestion. This process is repeated to generate a set of wiring configurations, each one using a different set of costs on the edges. Although the method used for each configuration is simple and efficient, all wires are assigned to direct minimum- cost paths and are not distributed among alternative routes. In effect, each routing configuration produces a trial wiring that need not obey the channel capacity constraints so that the wiring specified by any particular configuration is not necessarily realizable. To obtain an estimate of the wire distribution that would result from a realizable wiring, i.e., one that would be produced by a good global wiring algorithm, the set of configurations are "superimposed", or averaged. Each new routing of the nets is derived from the previous ones by searching for low-cost routes on a modified network which takes into account the pattern of congestion on the chip. Thus, the frequency with which particular channels are used is an indication of their "desirability", and the estimate represents a weighted sampling reflecting the extent to which given routings are preferred. If the predicted channel usages exceed channel capacities in certain areas of the chip, overcongestion in these areas is probable. The first trial wiring configuration is obtained by assigning to each edge (i,j) a cost proportional to d(i,j), the distance between the centers of channels i and j. (Via connectio...