Browse Prior Art Database

Embed Algorithm

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

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

The algorithm described herein is a technique for embedding a graph, i.e., a "regular" logic design into a cellular lattice, i.e., a LSI (large-scale integration) module. The algorithm is effectively a calculus for effecting an embedding, such that any short which is apt to occur in the embedded design is testable. The calculus, suitably termed cell, calculus, is an extension of the cubical calculus. It was disclosed in "On a Method for Wiring Solid Logic Cards", J. P. Roth, RA 50, July 5, 1973, pp. 54-72, published by the IBM Corporation.

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

Page 1 of 3

Embed Algorithm

The algorithm described herein is a technique for embedding a graph, i.e., a "regular" logic design into a cellular lattice, i.e., a LSI (large-scale integration) module. The algorithm is effectively a calculus for effecting an embedding, such that any short which is apt to occur in the embedded design is testable. The calculus, suitably termed cell, calculus, is an extension of the cubical calculus. It was disclosed in "On a Method for Wiring Solid Logic Cards", J. P. Roth, RA 50, July 5, 1973, pp. 54-72, published by the IBM Corporation.

In considering the "cell" calculus, let the position in an LSI module be conceived of as described by Cartesian coordinates in three dimensions. If two vertices of this LSI module are adjacent, they differ in exactly one coordinate. For example, an extreme vertex might have the coordinates 000. Then, the adjacent members 100, 010 and 001 would all be connectable to it, presumably by a path. It is assumed in the cell complex that, if two vertices are contained in the complex, then the path of the 1-cell connecting them also belongs to the complex.

In a similar manner, there may exist two cells such as a first which is a 1-cell [0, 0, 0,; 7, 0, 0], this particular cell would contain eight vertices from 000 to up to 700. It is assumed that the "space" being dealt with in terms of interconnection also contains the point 000, 107. Then these two 0-cells, as they are called, differ in exactly one coordinate and therefore define a 2-cell [0, 0, 0; 1, 0, 7].

In the situation of ordinates defined as [0, 0, 0; 7, 7, 8], this would signify that the space of all 0-cells vertices have coordinates whose values lie between 0 and 7 for the X coordinate; between 0 and 7 for the Y coordinate; and between 0 and 8 for the Z coordinate. Similarly, all 1-cells and 2-cells and 3-cells defined by this collection by means of accretion would also be included in this 3-cell.

There is utilized the term "complex of cells" which consists of an assemblage of cells having the characteristic that if it contains a given cell, it then contains all of its "faces". The "faces" of the cell are obtained by reducing the freedom in each of the coordinates, in any one of the coordinates, or all of the coordinates. Thus, a cell complex consists of a collection of cells having the property that, if it contains a given cell, then it contains all of its faces. The further requirement that is imposed is that, if the complex contains the vertices of a given cell, then it also contains the cell itself.

In the ensuing portion of the description of the algorithm, reference is made to "regular embedding". The term "embedding" derives from the classical problem in mathematics wherein given topological spaces X and Y, the problem is to decide whether or not there exists a topological mapping of X into Y. The problem, by analogy, arises in LSI design in the algorithm described herein. The term "regular" derives from its usage as desc...