Computer-aided design and analysis of circuits and semiconductor – Nanotechnology related integrated circuit design
Reexamination Certificate
1998-09-16
2001-12-11
Smith, Matthew (Department: 2825)
Computer-aided design and analysis of circuits and semiconductor
Nanotechnology related integrated circuit design
Reexamination Certificate
active
06330706
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates to interconnecting nodes and information elements in electronic, computer, and communication systems (for example, cells on an integrated circuit, modules in a multiprocessor system, or subscribers to a telecommunications network). Because of the general character of the topology that is the foundation of the proposed method and of the resulting structure, it can be used in hardware as well as in software architecture design.
2. Description of Background Art
Optimizing node interconnections is very important for modern electronic, computer, and communication systems. One of the most effective and general architectures of nodes interconnections is based on a full graph diagram in which each node is connected to every other node. A straightforward implementation of this architecture, however, cannot be realized practically in devices because of the very large number of interconnecting lines between nodes.
Numerous attempts to solve both this problem and the problems of the number and the complexity of the switching elements, delay time, etc. were not successful. For example, the well known hypercube architecture diminishes the number of interconnecting lines, but increases the delay time of information exchanges.
The hypercube architecture has many other disadvantages. Particularly, k-dimensional hypercubes have N=2
k
vertices, so these structures are restricted to having exactly 2
k
nodes. Because structure sizes must be a power of 2, there are large gaps in the sizes of systems that can be built with the hypercubes. This severely restricts the number of possible nodes.
A hypercube architecture has a delay time approximately equal to 2 log N, and has a “skew”, i.e., different delay times for different interconnecting nodes. This creates additional difficulties when using hypercube structures in system designs.
Similar problems are characteristic of other known methods of interconnection and corresponding types of architectures (bus, ring, etc.). Detailed descriptions of the interconnection structures mentioned above and their main characteristics can be found in H. Sullivan and T. Bashkov, “A large scale, homogenous, fully distributed parallel machine, 1.”
Proc.
4
Symp. Comp. Arch.,
1977, pp. 105-117 and in T. L. Casavant, P. Tvrdik, F. Plá{haeck over (s)}il,
Parallel computers: theory and practice
, IEEE Computer Society Press, Los Alamitos, Calif., 1995, 422 pp., the subject matter of both are incorporated herein by reference. Neither one of these architectures, however, can ensure an optimal solution to the interconnection problems.
Consequently, there is a need to develop an interconnecting method and structure that lacks the above-described shortcomings of known architectures.
SUMMARY OF THE INVENTION
The present invention provides a method for interconnecting a plurality of nodes. The plurality of nodes are arranged in a regular array having a preselected number N columns and having a preselected number S rows. The nodes in one row are interconnected to nodes in the previous row and the subsequent row using relationships based on hyperspace, Galois fields, and Perfect Difference Sets. An order n is selected for a Perfect Difference Set, which includes the set of integers {d
0
, d
1
, . . . , d
n
}. The preselected number N equals n
2
+n+1. Each node (s, j) is coupled to nodes (s−1, [j+d
i
] (Mod N)) for i=0, 1, . . . , n. Each node (s, j) is coupled to nodes (s+1, [j+d
i
] (Mod N)) for i=0, 1, . . . , n. Information elements are coupled to nodes (s, j), for s=0, 1, . . . , S, and j=0, 1, . . . , N−1.
The interconnection between nodes of different rows may have a weight assigned thereto for the interconnection. Such a weight may be signal loss between the nodes, attenuation of the coupling between the nodes, or the like.
The nodes may execute predefined functions such as logical functions. The nodes may form a Bayesian network in which intermediate nodes are uncertainty nodes. The output of such a node is not predetermined and may be beyond the control of the system operator. Such nodes may analyze data communicated to the node and, responsive to such data, provide the data to another node according to the logical function.
The present invention also provides an interconnection structure that includes a plurality of connecting lines and a plurality of nodes arranged in a regular array having a preselected number N columns and having a preselected number S rows. Each node (s, j) is coupled to nodes (s−1, [j+d
i
] (Mod N)), for i=0, 1, . . . , n, and is coupled to nodes (s+1, [j+d
i
] (Mod N)), for i=0, 1, . . . , n. The integers d
i
are components of a Perfect Difference Set of order n. The preselected number N of columns equals n
2
+n+1. The interconnection structure also includes a plurality of information elements, each of the plurality of information elements is coupled to any of the nodes (s, j), for s=1, 2, . . . , S and j=0, 1, . . . , N−1. The connecting lines couple nodes together and couple nodes and information elements.
The nodes may be hierarchical nodes (substructures of different levels) with an order of the node less than or equal to the number of inputs of the structure of the higher order.
The interconnection structure may be a bipartite interconnection structure that includes a plurality of connecting lines and a preselected number 2N of information elements, and includes a plurality of nodes arranged in a regular array having the preselected number N of columns and having three rows. Each node (0, j) of the first row is coupled to one of the plurality of information elements by a connecting line. Each node (1, j) of the second row is coupled to the nodes ([j+d
i
] (Mod N)) of the first and third rows for i=0, 1, . . . , n. Each node (2, j) of the third row is coupled to one of the plurality of information elements by a connecting line. The connecting lines couple nodes together and couple nodes and information elements.
The interconnection structure may be a complete hyperstar interconnection structure in which the nodes of row 0 and row S (i.e. the first and last rows) are integral and form a bi-directional node. Likewise, the information elements include both transmitters and receivers and are each coupled to one of the bi-directional nodes.
REFERENCES:
patent: 5734580 (1998-03-01), Rakov
Day et al., “A Comparative Study of Topological Properties of Hypercubes and Star Graphs” IEEE Trans on Parallel and Distributed Systems, vol. 5, No. 1, pp. 31-38, 1994.*
Misic et al., “Communications Aspects of the Star Graph Interconnection Network,” IEEE Trans on Parallel and Distributed Systems., vol. 5, No. 7, pp. 678-687, 1994.
Mackall John R.
Rakov Mikhail A.
Costello Leo F.
Garbowski Leigh Marie
Smith Matthew
LandOfFree
Method of interconnecting functional nodes and a hyperstar... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of interconnecting functional nodes and a hyperstar..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of interconnecting functional nodes and a hyperstar... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2598131