Browse Prior Art Database

Regular Embedding

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

Publishing Venue

IBM

Related People

Roth, JP: AUTHOR

Abstract

In the technique described herein, i.e., "Regular Embedding", the term "regular" derives from the term "regular" as it is used in logic design, i.e., R-design, and an algorithm for effecting such design, i.e., the R-algorithm. To effect such regular design, there is utilized the so-called R-notation as is further explained hereinbelow. The term "embedding" derives from the classical problem in mathematics, in particular in topology, which is known as the "embedding" problem.

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

Page 1 of 6

Regular Embedding

In the technique described herein, i.e., "Regular Embedding", the term "regular" derives from the term "regular" as it is used in logic design, i.e., R- design, and an algorithm for effecting such design, i.e., the R-algorithm. To effect such regular design, there is utilized the so-called R-notation as is further explained hereinbelow. The term "embedding" derives from the classical problem in mathematics, in particular in topology, which is known as the "embedding" problem.

In the "embedding" problem in mathematics, given topological spaces X and Y, the problem is to decide whether or not there exists a topological mapping of X into Y. In this connection, the term "topological" roughly signifies that the general, i.e., connectivity, form is unaffected, i.e., no new holes are inserted and no holes are destroyed.

In large-scale integration (LSI) technology a problem analogous to the embedding problem of mathematics arises, in a specific, more constructive form. In the latter problem, there is presented a logic design which may be considered as a graph. There is also given as the "target" space, a chip, wafer, card or board, i.e., in general, a space which may be thought of as a rectilinear lattice having various layers. In each of these layers there is present a rectilinear grid of connecting lines of some sort. The target space is, of course, limited in size and, for example, may consist of two or three layers, each having a rectilinear grid of about 220 x 200 lines on each layer, and possible interconnections between the corresponding vertices and the respective different layers.

In this context, there may also exist another layer for the so-called input/output pads, i.e., those connections with a portion of a computer external to the given target space, i.e., the chip, wafer, card or board. Generally, devices which correspond to the nodes in the graph of the logic design may themselves be placed on a vertex on a separate layer. Given a graph, the problem which is presented is not only to decide whether or not an embedding is possible but, if it is, to effect or construct such embedding.

Heretofore, in proposals for providing algorithms effecting such embedding, it has been assumed that the logic design was given, the latter design being described as a substantially long list of connections giving of "come froms" and "go tos". Consequently, the high-level structure of the design itself was lost, as far as algorithms purporting to perform the embedding or attempting such performance.

Accordingly, in the regular embedding technique described herein, the first salient element thereof is to capture the design at a relatively high level of sophistication. To effect such capture, there is provided an algorithm which utilizes the programming language PL/R which is a variant of the known programming language PL/l, which is a practical adaptation of the R notation, and which includes a FOR statement for each of describi...