Browse Prior Art Database

Large Scale Integration Embedding

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

Publishing Venue

IBM

Related People

Ellozy, HA: AUTHOR [+2]

Abstract

In the paper "On a Method for Wiring Solid Logic Cards", J. P. Roth, published in Algorithmic Design III Embedding: Diagnosis, Hard and Soft, RA 50, July 5, 1973, pp. 54-72, and published by the IBM Corporation, there is described a process or, more precisely stated, a calculus for embedding a graph (Logic Design) into a cubical lattice, i.e., a large-scale integration (LSI) body such as a chip.

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 Embedding

In the paper "On a Method for Wiring Solid Logic Cards", J. P. Roth, published in Algorithmic Design III Embedding: Diagnosis, Hard and Soft, RA 50, July 5, 1973, pp. 54-72, and published by the IBM Corporation, there is described a process or, more precisely stated, a calculus for embedding a graph (Logic Design) into a cubical lattice, i.e., a large-scale integration (LSI) body such as a chip.

The basic concept of this process is to describe the space of available paths and of unavailable paths at each stage of the computation utilizing the concept of a "cellular cover". The "cellular cover", is constituted by an assemblage of cells of dimensions 0, 1, 2, or 3 which define, by its "extreme-most" vertices, all of the 1 cells and vertices therein. A connecting chain is constructed between certain nodes and, as such construction proceeds, it is necessary to delete from the available space, those cells which are selected, i.e., are in the connecting chain.

The process for performing this deletion is called the "#-product", the latter term being a generalization of the term "#-product" as it is defined in "Algebraic Topological Methods for the Synthesis of Switching Systems", Transactions of American Mathematical Society, v. 88, July 1958, which treats of a similar geometric operation for complexes of cubes. This "#-product" notion is utilized in the calculus described in the embedding process referred to in the RA 50 publication hereinabove.

It has been found through experiment that the required computer running time for determining the #-product, as defined in the above-mentioned paper in the RA 50 publication, is excessive for large problems. This undesirably long- running time results from the large storage of cells at intermediate stages...