Patent
1996-07-11
1999-01-12
Asta, Frank J.
3952003, 39520031, 3958001, 3958002, G06F 1300, G06F 1328
Patent
active
058599819
ABSTRACT:
A message passing system for an MIMD parallel processing computer system utilizing a CSP programming model is relatively simple and inexpensive, yet allows for deadlock-free message passing, as well as the ability to support irregular connection topologies among nodes in the computer system. Messages are passed from node to node utilizing buffers at intermediate nodes to temporarily store the messages. In accordance with the CSP programming model, the user code is divided into multiple concurrent user processes which communicate with each other via channels. Each user process executing at a node is also provided with a corresponding, but separate, router process which uses a set of N-1 virtual channels to communicate with all other processes in the system, where N is the number of processes. The router process is preferably provided with a routing table that implements an acyclic sub-graph solution for interconnecting nodes in any arbitrary network topology, including irregular network topologies. The router process also allows for standard I/O functions to be emulated at every node in the system, not just those nodes which are directly connected to an I/O device. Preferably, the router process implements a buffer pool management structure which is organized first by channels and then by hops.
REFERENCES:
patent: 4177514 (1979-12-01), Rupp
patent: 4692861 (1987-09-01), May
patent: 4783734 (1988-11-01), May et al.
patent: 4985832 (1991-01-01), Grondalski
patent: 5047917 (1991-09-01), Athas et al.
patent: 5058001 (1991-10-01), Li
patent: 5101480 (1992-03-01), Shin et al.
patent: 5105424 (1992-04-01), Flaig
patent: 5113523 (1992-05-01), Colley et al.
patent: 5152000 (1992-09-01), Hillis
patent: 5168547 (1992-12-01), Miller et al.
patent: 5170393 (1992-12-01), Peterson et al.
patent: 5243698 (1993-09-01), May
patent: 5247694 (1993-09-01), Dahl
patent: 5253342 (1993-10-01), Blount et al.
patent: 5276895 (1994-01-01), Grondalski
patent: 5278834 (1994-01-01), Mazzola
patent: 5291489 (1994-03-01), Morgan et al.
patent: 5347450 (1994-09-01), Nugent
patent: 5367636 (1994-11-01), Colley
patent: 5367692 (1994-11-01), Edelman
patent: 5444701 (1995-08-01), Cypher et al.
patent: 5708836 (1998-01-01), Wllkinson et al.
David M. Skapura, "Vector links PC/workstation apps", Electronic Engineering Times, p. 64, Oct. 23, 1995.
Herb Edelstein, "The Power of Parallel Database", DBMS, p. D3, Mar. 1995.
Crocket et al, "A MIMD Rendering ALgorithm for Distributed Memory Architectures", IEEE Conference, Oct. 25, 1993.
Yamauchi et al, "PROTON: A Parallel Detailed Router on an MIMD Parallel Machine", IEEE Conference, Nov. 11, 1991.
C.B. Stlinkel, et al. The SP2 High Performance Switch, 34 (2) IBM Systems Journal, pp. 185-204 (1995).
M. Snir, et al., The Communication Software & Parallel Environment of IBM SP2, 34 (2) IBM Systems Journal, pp. 205-221 (1995).
E. Ma, et al., E-Kernal: An Embedding Kernal on the IBM Victor V256 Multiprocessor for Program Mapping & Network Reconfiguration, 5 (9) IEEE Transactions on Paralell & Distributed Systems 977, 994 (1994).
H. Masuyama, Algorithms to Realize an Arbitrary BPC Permution in Chordal Ring Networks & Mesh Connected Networks, E77-D (10) IEICE Trans. Inf. & Sys. 1118-1129 (1994).
Z.J. Czech, et al., Parallel Algorithms for Finding a Suboptimal Fundamental-Cycle Set in a Graph, 19 Parallel Computing 1961-1971 (1993).
Agejev Vjacheslav M.
Jablonsky Sergei V.
Jalin Valerii V.
Karatanov Vjacheslav V.
Korneev Victor V.
Asta Frank J.
Pierce, III Ivan C.
Super P.C., L.L.C.
LandOfFree
Method for deadlock-free message passing in MIMD systems using r 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 for deadlock-free message passing in MIMD systems using r, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for deadlock-free message passing in MIMD systems using r will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1523920