Patent Number: 6,490,630

Title: System and method for avoiding deadlock in multi-node network

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.

Inventors: Poon; Wing Leong (Santa Clara, CA), Helland; Patrick J. (Bellevue, WA), Shimizu; Takeshi (San Jose, CA), Umezawa; Yasushi (Cupertino, CA), Weber; Wolf-Dietrich (San Jose, CA)

Assignee: Fujitsu Limited

International Classification: G06F 15/177 (20060101); G06F 15/16 (20060101); G06F 015/16 ()

Expiration Date: 12/03/2019