System and method for avoiding deadlock in multi-node network

• US 6,490,630 B1
• Filed: 04/02/1999
• Issued: 12/03/2002
• Est. Priority Date: 05/08/1998
• Status: Expired due to Term

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Umezawa, Yasushi, Poon, Wing Leong, Shimizu, Takeshi, Weber, Wolf-Dietrich, Helland, Patrick J.
• Primary Examiner(s): Najjar, Saleh
• Application Number:
  US09/285,316
• Time in Patent Office: 1,341 Days
• Field of Search: 709/200, 709/201, 709/206, 709/207, 709/235, 709/234, 709/232, 370/229, 370/231, 370/232
• US Class Current: 709/235
• CPC Class Codes: G06F 15/17 using an input/output type connection, e.g. channel, I/O port

Abstract

A computer architecture for avoiding a deadlock condition in an interconnection network comprises a messaging buffer having a size pre-calculated to temporarily store outgoing messages from a node. Messages are classified according to their service requirements and messaging protocols, and reserved quotas in the messaging buffer are allocated for different types of messages. The allocations of the reserved quotas are controlled by a mechanism that, to prevent overflow, limits the maximum number of messages that can be outstanding at any time. The messaging buffer is sized large enough to guarantee that a node is always able to service incoming messages, thereby avoiding deadlock and facilitating forward progress in communications. The buffer may be bypassed to improve system performance when the buffer is empty or when data in the buffer is corrupted. In addition, a multicast engine facilitates dense packing of the buffer and derives information from a message header to determine whether there is a multicast to perform and to permit passage of messages. Other considerations to reduce the buffer size are incorporated.

Claims

1. A message passing apparatus for avoiding deadlock in a multi-node computer network, comprising:

a buffer for receiving network messages of various types including reliable transaction messages associated with transactions that must be completed reliably, and unreliable transaction messages associated with transactions that do not need to be completed reliably, said message types being classified based on their service requirements and messaging protocols;

a decoder for decoding the types of said network messages; and

an output controller coupled to said buffer and to said decoder for controlling the passage of said messages trough said buffer.

2. The apparatus of claim 1 wherein said buffer is coupled between an output of a node and a network.

3. The apparatus of claim 1 wherein said buffer is variably partitioned to suit a system configuration based on a predominant pattern of traffic of said network messages.

4. The apparatus of claim 1 wherein said network messages are stored in said buffer in a dense format.

5. The apparatus of claim 1 further comprising a multicast engine, coupled to said buffer, for determining whether there is a multicast to permit passage of messages and for reducing the number of entries needed in said buffer for a multicast message.

6. The apparatus of claim 1 further comprising a bypass engine coupled to said buffer for permitting messages to bypass said buffer, depending on a state of said buffer.

7. The apparatus of claim 1 wherein said buffer is extendable upon an indication of an overflow of messages stored in said buffer.

8. The apparatus of claim 1 wherein said buffer includes, for each of said network message types, a reserved quota based on a maximum number of outstanding messages allowed for the respective message type.

9. The apparatus of claim 8 wherein said reserved quota prevents overflow of said buffer.

10. The apparatus of claim 8 wherein the size of said buffer is large enough so that a node is always able to service incoming messages, thereby avoiding deadlock and facilitating forward progress in communications.

11. The apparatus of claim 8 wherein the size of said reserved quota for said posted messages is based on a number of said posted messages that a node is permitted to have outstanding.

12. The apparatus of claim 8 wherein the size of said reserved quota for said unreliable transaction messages is based on an expected frequency of a transaction associated with said unreliable transaction messages.

13. The apparatus of claim 1 wherein each of said message types includes a plurality of sub message types.

14. The apparatus of claim 13 wherein said sub message types for said reliable transaction messages include intervention-transaction and regular-transaction message types.

15. The apparatus of claim 13 wherein said sub message types allow space conservation for said buffer.

16. The apparatus of claim 1 wherein said network messages include a header having information on whether there is a multicast.

17. The apparatus of claim 1 wherein said output controller limits a number of network messages of each of said network message types.

18. The apparatus of claim 1 further comprising a network interface for guaranteeing message delivery in said network to reduce a number of message fan-out.

19. A message passing apparatus for avoiding deadlock in a multi-node computer network, comprising:

a buffer for receiving network messages of various types classified based on their service requirements and messaging protocols and including

reliable transaction messages associated with transactions that must be completed reliably,

posted messages associated with transactions that do not require a reply or other response message, and

unreliable transaction messages associated with transactions that do not need to be completed reliably,

said buffer having a reserved quota for each of said network message types based on a maximum number of outstanding messages allowed for the respective message type, the size of said reserved quota for said reliable transaction messages being a product of a maximum number of outstanding transactions per node, a maximum number of message fan-outs per transaction, a size of each message type, and half of a total number of nodes requiring reliable communication with one another;

a decoder for decoding said network message types; and

an output controller coupled to said buffer and to said decoder for controlling the passage of said messages through said buffer.

20. A method for avoiding deadlock in a multiple-node computer network using network messages, comprising the steps of:

providing a buffer for storing said network messages;

classifying said network messages into different types including

reliable transaction messages associated with transactions that must be completed reliably,

posted messages associated with transactions that do not require a reply or other response message, and

unreliable transaction messages associated with transactions that do not need to be completed reliably;

allocating reserved areas for said types of messages in said buffer, and

implementing a flow control mechanism to ensure said reserved allocations are not exceeded.

21. A data processing system for avoiding deadlock in a multi-node computer network, comprising:

an inter-processor communication network;

a first processor node including at least one processor;

a first network interface unit coupled to said first processor node and coupled to said network, said first network interface unit including;

a first buffer for receiving first network messages from said first processor node;

a first decoder for decoding said first network messages into different types; and

a first output controller coupled to said first buffer and to said first decoder for controlling the passage of said first messages through said first buffer;

a second processor node including at least one processor;

a second network interface unit coupled to said second processor node and coupled to said network, said second network interface unit including;

a second buffer for receiving second network messages from said second processor node;

a second decoder for decoding said second network messages into different types; and

a second output controller coupled to said second buffer and to said second decoder for controlling the passage of said second messages.