US5170482A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Improved hypercube topology for multiprocessor computer systems
Assignee: University of Minnesota System
•
Filing: 1991-02-13
•
Granted: 1992-12-08
•
Expires: 2011-02-13
Abstract
Abstract A hypercube system which has been modified by adding additional communication links between the most distant nodes of a classic hypercube topology is described herein. This improvement in a hypercube topology is termed as a Modified Hypercube topology. Such a topology contains extra links which connects a node to another node in the topology which requires the greatest number of nodal hops over the shortest path. Also stated another way, that node having the greatest number of singly traversed or hopped nodes along the shortest path from an originating node to that node makes that node the most distant processor node. If hamming were to be implemented in the system, there is added an extra link between two nodes having the greatest hamming distance. Such a system makes a technological trade off to reduce the diameter of a classic hypercube at the cost of incrementally increasing the number of I/O ports at each node. This trade off has been recognized in the industry as advantageous since a great gain in performance is achieved n exchange for an incremental impact to the hardware. Clearly the performance advantages of the present invention grows as the number of nodes in the hypercube grows and the maximum distance between nodes increases.
Inventors
- 👤 Renben Shu
- 👤 David H. C. Du
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 21:11
CPC Classifications
G; G06; G06F; G06F15/00; G06F15/16; G06F15/163; G06F15/173; G06F15/17337; G06F15/17343
Claims Analysis
Total Claims: 18
Claim 1
Independent Claim
114 words
A modified hypercube computing system, comprising: a plurality of 2 n processor nodes, where n is a whole integer greater than two, in an n-dimensional hypercube configuration having first bidirectional communication paths along the edges only of said hypercube; second bidirectional communication paths only directly connecting each of said processor nodes to the processor nodes' most distant processor node, which requires the greatest number of nodal hops over the shortest path, such that the total number of bidirectional communication paths does not exceed (2 n-1 )(n+1); and whereby said first and second bidirectional communications paths are substantially identical and the total number of communication paths connected to each processor node does not exceed (n+1).
Claim 2
Dependent Claim
114 words
A modified hypercube computing system, comprising: a plurality of 2 n processor nodes, where n is a whole integer greater than two, in an n-dimensional hypercube configuration having first bidirectional communication paths along the edges only of said hypercube; second bidirectional communication paths only directly connecting each of said processor nodes to the processor nodes' most distant processor node, which requires the greatest number of nodal hops over the shortest path, such that the total number of bidirectional communication paths does not exceed (2 n-1 )(n+1); and whereby said first and second bidirectional communications paths are substantially identical and the total number of communication paths connected to each processor node does not exceed (n+1).
Claim 3
Dependent Claim
17 words
The system according to claim 1 wherein each of said processor nodes is a single processing element.
Claim 4
Dependent Claim
25 words
The system according to claim 2 wherein the number of second bidirectional communication paths connecting each node to its most distant processor node is one.
Claim 5
Dependent Claim
21 words
The system according to claim 1 wherein each of said processor nodes is a substituted topology comprising a plurality of processors.
Claim 6
Dependent Claim
14 words
The system according to claim 4 wherein each substituted topology has the same topology.
Claim 7
Dependent Claim
16 words
The system according to claim 4 wherein each substituted topology is arranged as a cycle-connected topology.
Claim 8
Dependent Claim
16 words
The system according to claim 4 wherein each substituted topology is arranged as a hypercube topology.
Claim 9
Dependent Claim
17 words
The system according to claim 4 wherein each substituted topology is arranged as a modified hypercube topology.
Claim 10
Dependent Claim
146 words
A multiprocessor computing system, comprising: a plurality of 2 n substituted topologies, where n is a whole integer greater than two, wherein each substituted topology comprises a plurality of processors and a first communications network connecting said processors; a second communications network connecting said substituted topologies in a modified hypercube topology, said modified hypercube topology being connected with first communication paths in a hypercube topology and with additional communication paths only directly connecting each substituted topology to the substituted topology's most distant substituted topology which requires the greatest number of substituted topology hops over the shortest path, such that the total number of first communication paths in said second communications network does not exceed (2 n-1 )(n+1); and whereby said first and additional communications paths are substantially identical and the total number of communication paths connected to each of said substituted topologies does not exceed (n+1).
Claim 11
Dependent Claim
146 words
A multiprocessor computing system, comprising: a plurality of 2 n substituted topologies, where n is a whole integer greater than two, wherein each substituted topology comprises a plurality of processors and a first communications network connecting said processors; a second communications network connecting said substituted topologies in a modified hypercube topology, said modified hypercube topology being connected with first communication paths in a hypercube topology and with additional communication paths only directly connecting each substituted topology to the substituted topology's most distant substituted topology which requires the greatest number of substituted topology hops over the shortest path, such that the total number of first communication paths in said second communications network does not exceed (2 n-1 )(n+1); and whereby said first and additional communications paths are substantially identical and the total number of communication paths connected to each of said substituted topologies does not exceed (n+1).
Claim 12
Dependent Claim
17 words
The system according to claim 9 wherein each substituted topology is arranged as a modified hypercube topology.
Claim 13
Dependent Claim
16 words
The system according to claim 9 wherein each substituted topology is arranged as a cycle-connected topology.
Claim 14
Dependent Claim
16 words
The system according to claim 9 wherein each substituted topology is arranged as a hypercube topology.
Claim 15
Dependent Claim
140 words
A multicomputer system, comprising: a plurality of 2 n computing systems, where n is an integer greater than two, wherein each computing system comprises a plurality of processors and a first communications network having first communications paths connecting said processors; and a second communications network connecting said computing systems in a modified hypercube topology, said modified hypercube topology being a hypercube topology with additional communication paths only directly connecting each computing system to the computing sytem's most distant computing system, which requires the greatest number of system hops over the shortest path, such that a combined total number of said first and additional communication paths does not exceed (2 n-1 (n+1); and whereby said first and additional communications path are substantially identical and the total number of communication paths connected to each of said computing systems does not exceed (n+1).
Claim 16
Dependent Claim
140 words
A multicomputer system, comprising: a plurality of 2 n computing systems, where n is an integer greater than two, wherein each computing system comprises a plurality of processors and a first communications network having first communications paths connecting said processors; and a second communications network connecting said computing systems in a modified hypercube topology, said modified hypercube topology being a hypercube topology with additional communication paths only directly connecting each computing system to the computing sytem's most distant computing system, which requires the greatest number of system hops over the shortest path, such that a combined total number of said first and additional communication paths does not exceed (2 n-1 (n+1); and whereby said first and additional communications path are substantially identical and the total number of communication paths connected to each of said computing systems does not exceed (n+1).
Claim 17
Dependent Claim
129 words
A parallel processor computing system, comprising: an n-dimensional hypercube having a plurality of 2 n processor nodes, where n is a whole integer greater than two and having first data communication paths directly connecting each of said processor nodes to an adjacent neighbor processor node along the edges of said hypercube; second data communication paths within said hypercube directly connecting each of said processor nodes to a most distant processor node, which requires the greatest number of nodal hops over the shortest path, within said hypercube such that the total number of data communication paths does not exceed (2 n-1 )(n+1); and whereby said first and second data communications paths are substantially identical and the number of data communication paths connected to each processor node does not exceed (n+1).
Claim 18
Dependent Claim
129 words
A parallel processor computing system, comprising: an n-dimensional hypercube having a plurality of 2 n processor nodes, where n is a whole integer greater than two and having first data communication paths directly connecting each of said processor nodes to an adjacent neighbor processor node along the edges of said hypercube; second data communication paths within said hypercube directly connecting each of said processor nodes to a most distant processor node, which requires the greatest number of nodal hops over the shortest path, within said hypercube such that the total number of data communication paths does not exceed (2 n-1 )(n+1); and whereby said first and second data communications paths are substantially identical and the number of data communication paths connected to each processor node does not exceed (n+1).
References Cited (Backward Citations)
US4247892A
Cited
EP0132926A2
Cited
US4598400A
Cited
US4574311A
Cited
US4805091A
Cited
US4739476A
Cited
US4691291A
Cited
US4730322A
Cited
US4809202A
Cited
US4773038A
Cited
US4814980A
Cited
US4729095A
Cited
EP0251594A2
Cited
US4791641A
Cited
US4805173A
Cited
US4773873A
Cited
US4766534A
Cited
WO1988004077A1
Cited
US4827403A
Cited
JPS63186365A
Cited
WO1988008566A1
Cited
WO1988008652A1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1995-12-08 | 1996-06-08 | 1996-12-08 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1999-12-08 | 2000-06-08 | 2000-12-08 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2003-12-08 | 2004-06-08 | 2004-12-08 | $7700.00 | Window Closed / Lapsed |