Method and apparatus for maintaining message order in multi-user FIFO stacks

• US 5,901,291 A
• Filed: 10/21/1996
• Issued: 05/04/1999
• Est. Priority Date: 10/21/1996
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wilhelm, George William Jr., Feeney, James William, Olnowich, Howard Thomas
• Primary Examiner(s): Asta, Frank J.
• Assistant Examiner(s): VU, THONG H
• Application Number:
  US08/731,809
• Time in Patent Office: 925 Days
• Field of Search: 395/800.14, 395/306, 395/200.83, 395/200.75, 364/200, 370/85.1, 370/85, 370/409
• US Class Current: 709/253
• CPC Class Codes: G06F 13/128 for dedicated transfers to a network for protocol converters G06F13/387
• CPC Class Codes: H04L 49/90 Buffering arrangements
• CPC Class Codes: H04L 49/901 using storage descriptor, e.g. read or write pointers
• CPC Class Codes: H04L 49/9031 Wraparound memory, e.g. overrun or underrun detection
• CPC Class Codes: H04L 49/9073 Early interruption upon arrival of a fraction of a packet

Abstract

A digital parallel processing system wherein a plurality of nodes communicate via messages sent over an interconnection network. Messages are maintained in strict chronological order even though sent by nodes where several sources are generating messages simultaneously. A network adapter is described for interconnecting the processor and its associated memory to a network over a bus. The adapter includes an adapter associated memory programmable into a plurality of functional areas, said functional areas including a send FIFO for storing and forwarding messages to said network from said processor; a stack list for queueing in strict message order activation commands for said send FIFO; and an adapter program area for storing adapter program instructions which control the storing of messages to said send FIFO; and control means responsive to said stack list for executing said adapter program instructions in said strict message order without processor intervention.

Claims

1. A network adapter for interconnecting a processor and its associated memory to a network over a bus for sending direct memory access (DMA) and immediate messages from said processor to said network under control of activation commands, comprising:

an adapter associated memory programmable into a plurality of functional areas, said functional areas including

a send FIFO for storing and forwarding DMA and immediate messages to said network from said processor;

a stack list for ordering the sending of DMA and immediate messages to said send FIFO; and

an adapter program area for storing adapter program instructions which control the storing of DMA messages from said processor'"'"'s associated memory to said send FIFO and for storing immediate messages from said processor;

said processor being operable to store at least one of said DMA messages to its associated memory and to send an activation command to said stack list for each of said DMA messages, thereby commanding the network adapter to read in order said message from the processor'"'"'s associated memory via direct memory access for sending said message to said send FIFO and network;

said processor being further operable to send at least one of said immediate messages to said adapter program store area and an activation command to said stack list for each of said immediate messages directly to the network adapter without storing said messages to its associated memory;

said activation commands for said DMA messages and said activation commands for said immediate messages being queued in strict order into said stack list; and

a controller responsive to activation commands stored in said stack list for transferring immediate messages to send FIFO and for executing said adapter program instructions for transferring DMA messages to said send FIFO, whereby DMA and immediate messages are transferred to said send FIFO in said strict message order without processor intervention.

2. The network adapter of claim 1 wherein said controller, responsive to said adapter program instructions, executes direct memory access to memory associated with said processor to control the storing and forwarding of processor messages without processor intervention.

3. The network adapter of claim 1 wherein said controller is responsive to said adapter program instructions to control the storing and forwarding of said adapter program instructions to said send FIFO.

4. The network adapter of claim 1 wherein said controller fetches and executes said adapter program instructions sequentially in the order determined by said stack list.

5. The network adapter of claim 1 wherein said stack list contains a plurality of entries, each entry being a pointer to a plurality of adapter program instructions.

6. The network adapter of claim 5 wherein said controller executes processor commands received from said bus to add pointers to said stack list.

7. The network adapter of claim 6 wherein said stack list is a FIFO which orders entries by adding the most recently received entry to the bottom of said stack list.

8. The network adapter of claim 5 wherein said controller sequentially accesses pointers in said stack list, and responsive to said sequentially accessed pointers locates and executes the corresponding adapter program, and removes said accessed pointer from said stack list.

9. The network adapter of claim 8 wherein said stack list is a FIFO.

10. A network adapter for interconnecting a processor and its associated memory to a network over a bus for sending direct memory access (DMA) messages and immediate messages from said processor to said network under control of activation commands, comprising:

an adapter memory including a send buffer, a program store, an immediate message store, and a send pointer list;

said send buffer storing and forwarding said DMA and immediate messages in order to said network from said processor;

said program store storing direct memory access (DMA) programs for controlling the network adapter to read DMA messages from the processor'"'"'s associated memory via direct memory access and to

send DMA messages to said send buffer and network, and for storing and holding immediate DMA programs including immediate messages, until said messages are sent in order to said send buffer and network; and

said send pointer list queuing activation commands;

said processor being operable to store at least one of said DMA messages to its associated memory and to send one of said activation commands to said pointer list for each of said DMA messages;

said processor being further operable to send at least one of said immediate messages over said bus directly to said program of said adapter memory and to send one of said activation commands to said pointer list for each of said immediate messages;

a plurality of activation commands for said DMA messages and said immediate messages being queued in strict order into said pointer list; and

an adapter control responsive to said activation commands for transferring immediate messages to send buffer from said adapter program store and executing DMA programs for transferring DMA messages to said send buffer;

whereby said DMA and immediate messages transferred to said send buffer are in strict sequential order without processor intervention.

11. The network adapter of claim 10 wherein each of a plurality of said activation commands includes an address within said adapter memory of a corresponding DMA program.

12. The network adapter of claim 11 wherein each said plurality of activation commands further includes indicia identifying whether said DMA program is an immediate DMA program.

13. The network adapter of claim 12 wherein said adapter control is responsive to receipt of an immediate DMA program from said processor for adding a corresponding activation command to the bottom of said send pointer list.

14. Method for controlling the transfer of messages from a nodal processor and its associated memory through a network adapter to an interconnection network, said messages including direct memory access (DMA) messages and immediate messages being transferred under control of activation commands, comprising the steps of:

storing said DMA messages to said associated memory of said nodal processor;

storing said immediate messages in an adapter memory within said network adapter;

storing activation commands for said DMA and immediate messages in a send FIFO stacked list within said network adapter;

sequentially accessing said send FIFO stacked list to control the storing of said DMA and immediate messages to a send FIFO buffer; and

transferring said DMA and immediate messages from said send FIFO buffer to said interconnection network in sequential order.

15. The method of claim 14 wherein said storing steps include storing messages in said program store in other than strict sequential order, and storing pointers in said stacked list in strict sequential order.

16. The method of claim 15 wherein said transferring step includes sequentially accessing said stacked list to address and transfer said messages to said send FIFO buffer.