Routing technique for a hierarchical interprocessor-communication network between massively-parallel processors

Patent 5224100 Issued on June 29, 1993. Estimated Expiration Date:

May 9, 2011. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Path oriented routing system and method for packet switching networks
Patent #: 4736363
Issued on: 04/05/1988
Inventor: Aubin , et al.

Multicast routing algorithm
Patent #: 4740954
Issued on: 04/26/1988
Inventor: Cotton , et al.

Fiber-optic star tree network
Patent #: 4809362
Issued on: 02/28/1989
Inventor: Claus , et al.

Multiple memory loading system based on multilevel lists
Patent #: 4866668
Issued on: 09/12/1989
Inventor: Edmonds , et al.

Network system comprising a plurality of LANs using hierarchical routing
Patent #: 5018133
Issued on: 05/21/1991
Inventor: Tsukakoshi, et al.

High-speed mesh connected local area network
Patent #: 5088091
Issued on: 02/11/1992
Inventor: Schroeder, et al.

Inter-computer message routing system with each computer having separate routinng automata for each dimension of the network
Patent #: 5105424
Issued on: 04/14/1992
Inventor: Flaig, et al.

Storage star network
Patent #: 5109379
Issued on: 04/28/1992
Inventor: Kume, et al.

5117430

System for routing messages in a vertex symmetric network by using addresses formed from permutations of the transmission line indicees Patent #: 5125076
Issued on: 06/23/1992
Inventor: Faber, et al.

Inventors

Assignee

David Sarnoff Research Center, Inc.

Application

No. 697556 filed on 05/09/1991

US Classes:

370/408, Nodes interconnected in hierarchy to form a tree340/825.02Tree or cascade

Examiners

Primary: Olms, Douglas W.
Assistant: Ton, Dang

Attorney, Agent or Firm

Burke; William J.

International Class

H04J 003/24

Abstract

A routing process for a single-instruction-multiple-data (SIMD) multi-level hierarchical network of nodes, which are arranged in clusters and interconnected by dual, unidirectional channels, are used to send data packets including routing address information during a succession of routing cycles from transmitting ones to receiving ones of a large number of parallel processors (e.g., 4096 processors arranged in a hierarchy of 8 cabinets, each of which contains a cluster of 8 circuit boards, with each circuit board containing a cluster of 64 processors). Each of the nodes includes a storage buffer having a capacity equal to a given number which is one more than the total number of channels terminating at that node. This routing process guarantees prevention of deadlock between levels and buffer overflow, and offers high-speed, low-cost interprocessor communication for SIMD computers.

Other References

Chin D. et al., "The Princeton Engine: A Real Tim Video System Simulator": IEEE Transaction on Consumer Electronics, vol. 34, No. 2, May 1988
Alverson, R. et al., "The Tera Computer System," ACM, 1990
Wu, S. and Liu, M., "A Cluster Structure as an Interconnection Network for Large Multimicrocomputer Systems," IEEE Transactions on Computers, vol. C30 No. 4, Apr., 1981
Vranesic, Z. et al., "Hector: A Hierarchically Structure Shared-Memory Multiprocessor", Computer, 1991
Pitelli, F. and Smitley, D., "Analysis of a 3D Torodal Network for a Shared Memory Architecture," Proc. of Suprcomputing '88, IEEE, 1988
Germain, C. et al., "An Interconnection Network and a Roting Scheme for a Massively Parallel Message-Passing Multicomputer" Proc. of the Symposium the Frontiers of Massively Parallel Computation, IEEE, 199