Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data transfer regulating
Reissue Patent
2001-03-02
2004-11-09
Luu, Le Hien (Department: 2141)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data transfer regulating
C709S238000, C370S229000
Reissue Patent
active
RE038650
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to the field of digital computer systems and more particularly to multiprocessor computer systems interconnected by cyclic interconnection networks that provide for deadlock-free message transfer.
BACKGROUND OF THE INVENTION
A number of types of multiprocessor computer systems have been developed which integrate a number of processors to increase the system's processing power beyond that which can be provided by a single processor. In a multiprocessor computer system, a plurality of processing nodes are interconnected by communication links which may comprise any suitable mechanism for transferring digital information, including, for example, wires, optical fibers, and the like.
A variety of types of interconnection arrangements have been developed for interconnecting processors in a multiprocessor computer system designed according to the distributed memory model, organized in a number of topologies. For small systems, comprising two or three processing nodes, a simple bus to which all processing nodes are connected may suffice. However, as the number of processing nodes increases, contention for the bus increases, which can slow down information transfer and the processing capability of the respective systems.
Most interconnection topologies that have been proposed, studied and/or implemented, other than the aforementioned bus arrangement, have been developed for systems including a large number of processing nodes, in particular, systems numbering in the hundreds or thousands of processing nodes. However, many systems that are desired commercially are much smaller, having, for example, as few as four to five processing nodes, up to as many as fifteen to twenty. For such systems, interconnection topologies that have been developed for large systems are often not economical. Another problem with such interconnection topologies is that they are typically based on the assumption that the systems with which they are to be used includes a number of processing nodes corresponding to a power of two, and will be most economical for those numbers of processing nodes. If, for example, such a system is required to have a number of processing nodes corresponding to a power of two, it may be necessary to increase the interconnection subsystem considerably even if it is desired to increase the number of processing nodes by only one.
The aforementioned Heller, et al., patent application describes
There have been described
a number of interconnection subsystems for efficiently interconnecting small numbers of nodes, each having a selected “degree” or “radix”, (that is, or number of connections to communication links) in a multiprocessor computer system. In
a number of the
some described
interconnection subsystems
described in the Heller, et al., patent application
, all of the nodes are of degree “three”, so that each processing node can connect to as many as three communication links. Generally,
the
these
interconnection subsystems
described in the Heller, et al., patent application
are effective for interconnecting from as few as two nodes to as many as fifteen to twenty nodes, with no power-of-two limitation.
One problem that can arise in connection with interconnection subsystems
such as those described in the Heller, et al., patent application
is that deadlocks can develop in transferring information among the processing nodes. Deadlocks can arise in multiprocessor computer systems in a variety of ways; one way in which a deadlock can arise in an interconnection subsystem
described in the Heller, et al., patent application
is if a number of processing nodes are attempting to concurrently transfer information to and/or through the same processing node. In that case, the processing nodes which are attempting to transfer information will be requiring use of the same resources at the processing node to or through which the information is to be transferred. Since the resources can only be used for the information transfer by one of the processing nodes, all of the processing nodes which need to transfer information are blocked from proceeding. Since such a condition can arise, an interconnection subsystem is only useful if it can be provided with resources to ensure that deadlock cannot occur.
SUMMARY OF THE INVENTION
The invention provides an new and improved system and method for performing deadlock free message transfer in a cyclic multi-hop digital computer network that may be used in a multiprocessor computer system.
In brief summary, the invention provides a new message packet transfer system, which may be used in, for example, a multiprocessor computer system. The message packet transfer system comprises a plurality of switching nodes interconnected by communication links to define at least one cyclical packet transfer path having a predetermined diameter. The switching nodes may be connected to, for example, digital data processors and memory to form processing nodes in an multiprocessor computer system, and/or to other sources and destinations for digital data contained in the message packets. The switch nodes transfer message packets each from a respective one of the switching nodes as a respective source switching node to a respective one of the switching nodes as a respective destination switching node. At least one of the switching nodes has a plurality of buffers for buffering a corresponding plurality of message packets that it (that is, the at least one of the switching nodes) receives from another of said switching nodes during a message transfer operation, which ensures that deadlock does not occur during the message transfer operation.
REFERENCES:
patent: 4616359 (1986-10-01), Fontenot
patent: 4623996 (1986-11-01), McMillen
patent: 4742511 (1988-05-01), Johnson
patent: 4780870 (1988-10-01), McHarg et al.
patent: 4930122 (1990-05-01), Takahashi et al.
patent: 5347450 (1994-09-01), Nugent
patent: 5400329 (1995-03-01), Tokura et al.
patent: 5544154 (1996-08-01), Glitho
patent: 5583990 (1996-12-01), Birrittella et al.
patent: 5802047 (1998-09-01), Kinoshita
patent: 5838994 (1998-11-01), Valizadeh
patent: 5907717 (1999-05-01), Ellis
W. Dally, “Virtual-Channel Flow Control,” IEEE Transactions On Parallel and Distributed Systems, vol. 3, No. 2, Mar. 1992, pp. 194-205.*
G. Pifarre, et al., “Fully-Adaptive Minimal Deadlock-Free Packet Routing in Hypercubes, Meshes and Other Networks,” Proc. 3rdAnnual ACM Symp. on Parallel Algorithms and Architectures, 1991, pp. 1-20.*
P. Berman, et al., “Adaptive Deadlock- and Livelock-Free Routing With All Minimal paths in Torus Networks,” Proc. Acm Symp. on Parallel Algorithms and Architectures, pp. 3-12, 1992.
Heller Steven K.
Wade Jon P.
Luu Le Hien
Sun Microsystems Inc.
Sun Microsystems, Inc.
LandOfFree
System for performing deadlock free message transfer in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System for performing deadlock free message transfer in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for performing deadlock free message transfer in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3324629