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

Global Wiring with Minimum Rectangles

IP.com Disclosure Number: IPCOM000049008D
Original Publication Date: 1982-Apr-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 45K

Publishing Venue

IBM

Related People

Giaccone, LF: AUTHOR

Abstract

When a chip is partitioned into x by y "global" cells, each terminal can then be said to occupy a cell C(ij). A net is a set of terminals to be connected by paths consisting of adjacent global cells. Each border of a cell (N,S,E,W) is associated with a supply (S) which is the capacity of the cell to convey paths from itself to its neighbor.

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

Global Wiring with Minimum Rectangles

When a chip is partitioned into x by y "global" cells, each terminal can then be said to occupy a cell C(ij). A net is a set of terminals to be connected by paths consisting of adjacent global cells. Each border of a cell (N,S,E,W) is associated with a supply (S) which is the capacity of the cell to convey paths from itself to its neighbor.

Consider a two-terminal net whose enclosing rectangle is n by m cells. The terminals occupy diagonal corners, and the minimum distance between them, in cells, is the half perimeter (1/2P) of the rectangle or n+m-1 cells. The minimum path will occupy some sequence of cells within the rectangle of length 1/2P but not necessarily the half perimeter.

It is possible to assess the potential demand made by the net on the cells enclosed by rectangle r(i) and assign to each cell some portion of that demand. It has been stated that the "demand" is 1/2P and, moreover, that the demand consists of a vertical and a horizontal component of m-1 and n-1 cell borders, respectively, to be crossed. With reference to Figs. 1 and 2, any path crossing a cell boundary in the horizontal direction may occupy one of m cell boundaries and any vertical path may occupy one of n cell boundaries. Thus, the demand assignable to each cell boundary to be crossed is d/i/(x)=l/m and d(i)/y/=l/n for rectangle r/i/.

For multi-terminal nets a Steiner (or other) tree is constructed for each net and the additional path length is apportioned to the horizontal and vertical components of the rectangle as (see original). Note that the additional path length is only assigned to the separate components and therefore may be reassigned when occasion suits, as will be seen.

Now consider the effect of all the nets (rectangles) on the individual cell borders. It is clear that the demands on any cell border due to the rectangles may be summed. We therefore write D (see original), giving the total demand placed on the east border of cell C/ij/. It is assumed that only the positive (east and north) borders X and Y are recorded at each cell.

It is now possible to compare the supply (the capacity of the cell to carry paths) to the demand. If the demand exceeds the supply, then an overflow exists, meaning that one or more of the rectangles, making demands on this cell and whose exact identities are as yet undetermined, cannot be satisfi...