Multi-processor computer system with distributed memory and an interprocessor communication mechanism, and method for operating such mechanism

• US 5,036,459 A
• Filed: 03/09/1989
• Issued: 07/30/1991
• Est. Priority Date: 03/09/1989
• Status: Expired due to Fees

• Current Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Original Assignee: US Philips Corporation (Koninklijke Philips N.V.)
• Inventors: Hopmans, Franciscus P. M., den Haan, Petrus A. M.
• Primary Examiner(s): Fleming, Michael R.
• Assistant Examiner(s): CHUN, DEBRA
• Application Number:
  US07/321,412
• Time in Patent Office: 873 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 709/237
• CPC Class Codes: G06F 15/17 using an input/output type connection, e.g. channel, I/O port
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A method and process for operating an interprocess communication mechanism in a multi processor computer system are described. If a sender node needs sending a message to a receiver node, it accesses the latter for available storage space. If available, the message is transferred and the sender node may resume processing. If nonavailable the transferring is deferred. In either case the message is queued to any message either awaiting processing at the receiver node or awaiting transfer, in that at the instant when such transfer was necessary, no storage space had been available. If the receiver node wants to process a message, it accesses the least recent item of the message queue and unlinks it, while belated transferring is now executed, if necessary.

Thereupon the original sender node was still kept waiting, it is now allowed to resume processing. Generally only two communication operations are required per message. Only in case of inavailability of storage space, the message in question needs four communication operations.

Claims

1. A multiprocessor computer system with distributed memory and an interprocessor communication mechanism, said system comprising for transmitting a message from a sender node to a receiver node:

(a) in the sender node

(I) first local communication process means,

(II) sender process means for delivering a message,

(III) means for requesting a second local communication process means in the receiver node to queue said message;

(b) in the receiver node, said second communication process means, including

(I) first detecting means for detecting a queuing request from said requesting means,

(II) a first local memory facility,

(III) inspection means for inspecting the first local memory facility to determine whether the first local memory facility is available for storing said message,

(IV) local queuing control means for, if said first local memory facility is available, receiving and queuing said message to a local position of a waiting queue, which local position is in said first local memory facility, and for generating an arrival signal for said message, and for sending an acknowledge signal to said sender node,

(V) a receiver process means, coupled to receive said arrival signal,

(VI) non-local queueing control means for,

(A) if said first local memory facility is not available, arresting and queueing said message to a non-local position of the waiting queue, which non-local position is in a second local memory facility of the sender node, and

(B) generating a pendency signal with respect to said message to the receiver process means;

(VII) chaining means for, under control of any output signal of said detecting means, signalling, to an applicable local communication process of any node containing a most recent preceding message of the waiting queue, a link indication signal identifying the node containing said message, whereby said message becomes a next successor message in the waiting queue, and whereby when the first local memory facility is not available said waiting queue extends over a plurality of nodes;

(VIII) second detecting means, in the receiver process means, for after receiving either said arrival or said pendency signal, accessing a least recently activated position of the waiting queue and for detecting whether the least recently activated position is local or non-local;

(IX) first dequeueing means for, if said least recently activated position is local, dequeueing and accepting from said waiting queue, the message in said least recently activated position for processing in said receiver processing means;

(X) second dequeueing means for, if said least recently activated position is non-local,

(A) dequeueing the message in said least recently activated position by controlling an applicable communication process means of any node containing the least recently activated position of the queue to present the message in said least recently activated position;

(B) accepting the message for said receiver processing means from said least recently activated position;

(C) reactivating said second detection means until the queue be empty; and

(XI) acknowledge means for, after said accepting, transmitting an acknowledge signal to an applicable sender node.

2. A method for interprocessor communication, in a multiprocessor communication system with distributed memory, comprising the steps of:

(a) producing a message in a sender process within a first local communication process in a sender node;

(b) requesting a second local communication process in a receiver node to queue said message;

(c) in the second local communication process of the receiver node, detecting the queueing request;

(d) inspecting a first local memory facility in said receiver node to determine whether the first local memory facility is available for storing said message;

(e) if said first local memory facility is available,

(I) accepting and queuing said message to a local position of a waiting queue in said first local memory facility; and

(II) signalling a receiver process of the receiving node of the arrival of said message;

(f) if said first local memory facility is not available, retaining said message in a second, non-local position of the waiting queue which is located in a second local memory facility in the sender node;

(g) signalling, to a local communication process which contains a most recent pending message of the waiting queue, a link indication identifying the node containing said message, whereby said message becomes a next successor message in the waiting queue and whereby if said first local memory facility is not available, said waiting queue extends over a plurality of nodes;

(h) accessing, by said receiver process in the receiver node, a least recently activated message of the waiting queue;

(i) detecting whether the least recently activated message is local or non-local to the receiver node;

(j) if the least recently activated message is local to the receiver node, dequeueing and accepting the least recently activated message from said waiting queue for processing by the receiver process;

(k) if the least recently activated message is non-local to the receiver node,

(I) controlling an applicable communication process of the node containing the least recently activated message to dequeue and present the least recently activated message;

(II) accepting the least recently activated message by the receiver process;

(l) processing the waiting queue until it is empty;

(m) after accepting any transmitted message, transmitting an acknowledge message from the receiver node to an applicable sender node.

3. The method of claim 2 wherein

(a) said producing step comprises delivering said message to the first local communication process;

and

(b) said requesting step is performed within the first local communication process.

4. A method as claimed in claim 2 or 3, wherein said queueing is order preserving.

5. The method of claim 2 or 3 wherein step (e) (I) requires two network operations.

6. The method of claim 2 or 3 wherein step (e) (I) requires four network operations.

7. The method of claim 2 or 3, comprising the step of maintaining a second waiting queue in the receiver node for storing a second message having a second message type.

8. A method for transmitting and storing an interprocessor communication, in a multiprocessor communication system with distributed memory, comprising the steps of:

(a) producing a message in a sender process within a first local communication process in a sender node;

(b) requesting a second local communication process in a receiver node to queue said message;

(c) in the second local communication process of the receiver node, detecting the queueing request;

(d) inspecting a first local memory facility in said receiver node to determine whether the first local memory facility is available for storing said message;

(e) if said first local memory facility is available,

(I) accepting and queuing said message to a local position of a waiting queue in said first local memory facility; and

(II) signalling a receiver process of the receiving node of the arrival of said message;

(f) if said first local memory facility is not available, retaining said message in a second, non-local position of the waiting queue which is located in a second local memory facility in the sender node; and

(g) signalling, to a local communication process which contains a most recent pending message of the waiting queue, a link indication identifying the node containing said message, whereby said message becomes a next successor message in the waiting queue and whereby if said first local memory facility is not available, said waiting queue extends over a plurality of nodes.

9. A method for accessing a stored interprocessor communication in a multiprocessor system with distributed memory comprising the steps of:

(a) accessing, by a receiver process in a receiver node, a least recently activated message of a waiting queue which links waiting messages for the receiver node, which waiting messages are stored in memory facilities local to a plurality of nodes;

(b) detecting whether the least recently activated message is local or non-local to the receiver node;

(c) if the least recently activated message is local to the receiver node, dequeueing and accepting the least recently activated message from said waiting queue for processing by the receiver process;

(d) if the least recently activated message is non-local to the receiver node,

(I) controlling an applicable communication process of a node containing the least recently activated message to dequeue and present the least recently activated message;

(II) accepting the least recently activated message by the receiver process;

(e) processing the waiting queue until it is empty; and

(f) after accepting any transmitted message, transmitting an acknowledge message from the receiver node to an applicable sender node.