Improved hypercube topology for multiprocessor computer systems

Details Improved hypercube topology for multiprocessor computer systems Improved hypercube topology for multiprocessor computer systems

1991-02-13

1992-12-08

Lee, Thomas C.

Boots, shoes, and leggings

364DIG1, 364DIG2, 364931, 3649314, 36493141, 364229, G06F 1300

Patent

active

051704820

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.

REFERENCES:
patent: 4247892 (1981-01-01), Lawrence
patent: 4574311 (1986-03-01), Resnikoff et al.
patent: 4598400 (1986-07-01), Hillis
patent: 4691291 (1987-09-01), Wolfrom
patent: 4729095 (1988-03-01), Colley et al.
patent: 4730322 (1988-03-01), Pollara-Bizzola
patent: 4739476 (1988-04-01), Fiduccia
patent: 4766534 (1988-08-01), DeBenedictis
patent: 4773038 (1988-09-01), Hillis et al.
patent: 4773873 (1988-09-01), Hillis
patent: 4791641 (1988-12-01), Hillis
patent: 4805091 (1989-02-01), Thiel et al.
patent: 4805173 (1989-02-01), Hillis et al.
patent: 4809202 (1989-02-01), Wolfram
patent: 4814980 (1989-03-01), Peterson et al.
patent: 4827403 (1989-05-01), Steele, Jr. et al.
Franco P. Preparata, et al., "The Cube-Connected Cycles: A Versatile Network For Parallel Computation," Comm. of ACM vol. 24, No. 5 May 1981.
Marshall C. Pease, "The Indirect Binary n-Cube Microprocess Array," IEEE Transaction on Computers, May 1977.
Stephen Colley, et al., "A Microprocessor-based Hypercube Supercomputer," IEEE Micro, Oct. 1986.
"Combining Parallel and Sequential Sorting on a Boolean n-Cube", Johnsson; IEEE, copyright 1984.
"Dense Trivalent Graphs for Processor Interconnection", Leland and Solomon; IEEE Transactions on Computers, vo. C-31, No. 3, Mar. 1982.
"A Survey of Interconnection Networks", Tse-yun Feng, IEEE, Dec. 1981.
"Architecture of a Hypercube Supercomputer", Hayes, Madge, Stout, et al., IEEE, copyright 1986.
Collection of slides taken fron an N-Cube Corporation presentation, identified on first page with the N-Cube founders.
Selected portion of book entitled The Connection Machine, by Hills, MIT Press.
Pamphlet: "N--Cube Ten-True Parallel Computing", from N--Cube Corporation.
"Performance of the Direct Binary n-Cube Network for Multiprocessors," Abraham and Padmanabhan; IEEE, copyright 1986.
"Distributed Routing Algorithms for Broadcasting and Personalized Communication in Hypercubes", Ho and Johnson; IEEE, copyright 1986.
"The Architecture of a Homogeneous Vector Supercomputer", Gustafson, Hawkinson and Scott; IEEE, copyright 1986.
"Scalability of a Binary Tree on a Hypercube", Deshpande and Jenevein; IEEE, copyright 1986.
"Multigrid Algorithms on the Hypercube Multiprocessor", Chan and Saad; IEEE Transactions on Computers, vol. C(?), No. 11, Nov. 1986.
"How Robust is the n--Cube?", Becker and Simon; IEEE, copyright 1986.
"On Folded Hypercubers", by Latifi and El-Amawy, published in the 1989 International Conference on Parallel Processing.
"Properties and Performance of Folded Hypercubes", by El-Amawy and Latifi, published in the IEEE Transactions on Parallel and Distributed Systems.

Affiliated with

Also associated with

Rating

Improved hypercube topology for multiprocessor computer systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Improved hypercube topology for multiprocessor computer systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Improved hypercube topology for multiprocessor computer systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-966153