Browse Prior Art Database

Large Scale Integration Physical Design Procedures

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

Publishing Venue

IBM

Related People

Ellozy, HA: AUTHOR [+2]

Abstract

The problem of embedding a logic design into a chip, wafer, module, etc. involves the computation of topological components, neighborhoods etc. at every stage of the embedding process. In this approach an inescapable operation is the #-product which is a kind of differencing operation. Given two cells u and v, u#v is a "cover" of all vertices of u that are not in v. This operation is frequently performed, for example, to remove a cell or assemblage of cells from the space A of available cells and paths. The running time is a strong exponential function of the number of cells, when "sharping" one cover from another.

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

Page 1 of 2

Large Scale Integration Physical Design Procedures

The problem of embedding a logic design into a chip, wafer, module, etc. involves the computation of topological components, neighborhoods etc. at every stage of the embedding process. In this approach an inescapable operation is the #-product which is a kind of differencing operation. Given two cells u and v, u#v is a "cover" of all vertices of u that are not in v. This operation is frequently performed, for example, to remove a cell or assemblage of cells from the space A of available cells and paths. The running time is a strong exponential function of the number of cells, when "sharping" one cover from another.

By interposing the operation CONTAIN, dramatic improvements are obtained. In addition, in this procedure the operation of REMOVE is interposed, which removes redundant cells leaving a nonredundant and usually very much smaller cover. The frequency or condition under which REMOVE is activated is a parameter of the procedure. 1) Select cell co of C for REMOVE operation. 2) Construct neighborhood U(c,C) of c with respect to C.

At each stage of the computation two disjoint spaces are significant: A, the space of vertices and paths Available for subsequent interconnections and N, the space of those Not available. Suppose a chain ch of cells connecting an assemblage of given cells, usually vertices, is constructed. Once selected, ch is removed from A and this is done by performing the #-product. For this purpose first form, for each cell c of C, the neighborhood U(c,C), defined as all cells c' of C having a nondegenerate interface with c, exclusive of c itself. First consider the problem of forming c#(C-c). It is clear that c#(C-c) = c#U(c,C).

This is the first embellishment of the #-procedure. REMOVE Procedure for removing redundant cells (1) Select "smallest" cell r in cover C, i.e., one with fewest vertices and form U(r,C). (2) Form r#U(r,C). If empty, then r is removed from C, a...