Method for deadlock-free message passing in MIMD systems using routers and buffers

摘要

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.