Message Passing with Queues and Channels

• US 20110246582A1
• Filed: 03/30/2010
• Published: 10/06/2011
• Est. Priority Date: 03/30/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Dozsa, Gabor J., Heidelberger, Philip, Kumar, Sameer, Wisniewski, Robert W., Ratterman, Joseph D., Steinmacher-Burow, Burkhard
• Granted Patent: US 8,543,722 B2
• Time in Patent Office: Days
• US Class Current: 709/206
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

In an embodiment, a send thread receives an identifier that identifies a destination node and a pointer to data. The send thread creates a first send request in response to the receipt of the identifier and the data pointer. The send thread selects a selected channel from among a plurality of channels. The selected channel comprises a selected hand-off queue and an identification of a selected message unit. Each of the channels identifies a different message unit. The selected hand-off queue is randomly accessible. If the selected hand-off queue contains an available entry, the send thread adds the first send request to the selected hand-off queue. If the selected hand-off queue does not contain an available entry, the send thread removes a second send request from the selected hand-off queue and sends the second send request to the selected message unit.

Claims

1. A method comprising:

receiving, by a send thread, an identifier that identifies a destination node and a data pointer;

creating, by a send thread, a first send request in response to the receiving;

selecting, by the send thread, a selected channel from among a plurality of channels, wherein the selected channel comprises a selected hand-off queue and a selected identification of a selected message unit, wherein the each of the plurality of channels comprise a respective hand-off queue and a respective identification of a respective message unit;

if the selected hand-off queue contains an available entry, adding, by the send thread, the first send request to the selected hand-off queue; and

if the selected hand-off queue does not contain an available entry, removing, by the send thread, a second send request from the selected hand-off queue and sending the second send request to the selected message unit identified by the selected identification in the selected channel, wherein the selected message unit sends the data pointed to by the data pointer to the destination node.

2. The method of claim 1, wherein each of the respective identifications in the plurality of channels identifies a different of the respective message units.

3. The method of claim 1, wherein the selecting further comprises selecting the selected channel via a hash function on an identifier of the destination node and an identifier of a set of nodes to which a source node and the destination node belong.

4. The method of claim 1, further comprising:

determining whether the selected hand-off queue contains the available entry, wherein the determining further comprises determining whether a tail counter is not equal to a size of the hand-off queue minus a head counter.

5. The method of claim 1, further comprising:

removing, by an injection thread, the first send request from the selected hand-off queue and sending the first send request to the selected message unit, wherein the removing the first send request further comprises incrementing a tail counter of the selected hand-off queue mod a size of the selected hand-off queue, wherein the selected hand-off queue is randomly accessible.

6. The method of claim 1, wherein the adding the first send request to the selected hand-off queue further comprises:

incrementing a head counter of the selected hand-off queue mod a size of the selected hand-off queue.

7. The method of claim 1, wherein the receiving receives the identifier of the destination node and the data pointer from an application that executes synchronously within the send thread.

8. The method of claim 5, wherein the send thread and the injection thread comprise different threads that execute asynchronously from each other.

9. The method of claim 5, wherein the send thread and the injection thread comprise a same thread.

10. A computer-readable storage medium encoded with instructions, wherein the instructions when executed comprise:

receiving, by a send thread, an identifier that identifies a destination node and a data pointer;

creating, by a send thread, a first send request in response to the receiving;

selecting, by the send thread, a selected channel from among a plurality of channels, wherein the selected channel comprises a selected hand-off queue and a selected identification of a selected message unit, wherein the each of the plurality of channels comprise a respective hand-off queue and a respective identification of a respective message unit, wherein the selecting further comprises selecting the selected channel via a hash function on the identifier of the destination node and an identifier of a set of nodes to which a source node and the destination node belong, wherein the selected hand-off queue is randomly accessible;

if the selected hand-off queue contains an available entry, adding, by the send thread, the first send request to the selected hand-off queue; and

if the selected hand-off queue does not contain an available entry, removing, by the send thread, a second send request from the selected hand-off queue and sending the second send request to the selected message unit identified by the selected identification in the selected channel, wherein the selected message unit sends the data pointed to by the data pointer to the destination node asynchronously from execution of the send thread.

11. The computer-readable storage medium of claim 10, wherein each of the respective identifications in the plurality of channels identifies a different of the respective message units.

12. The computer-readable storage medium of claim 10, further comprising:

determining whether the selected hand-off queue contains the available entry, wherein the determining further comprises determining whether a tail counter is not equal to a size of the hand-off queue minus a head counter.

13. The computer-readable storage medium of claim 10, further comprising:

removing, by an injection thread, the first send request from the selected hand-off queue and sending the first send request to the selected message unit, wherein the removing the first send request further comprises incrementing a tail counter of the selected hand-off queue mod a size of the selected hand-off queue.

14. The computer-readable storage medium of claim 10, wherein the adding the first send request to the selected hand-off queue further comprises:

incrementing a head counter of the selected hand-off queue mod a size of the selected hand-off queue.

15. The computer-readable storage medium of claim 10, wherein the receiving receives the identifier of the destination node and the data pointer from an application that executes synchronously within the send thread.

16. The computer-readable storage medium of claim 13, wherein the send thread and the injection thread comprise different threads that execute asynchronously from each other.

17. The computer-readable storage medium of claim 13, wherein the send thread and the injection thread comprise a same thread.

18. A node comprising:

a processor;

a plurality of message units communicatively connected to the processor; and

memory communicatively connected to the processor and the message unit, wherein the memory is encoded with instructions, and wherein the instructions when executed on the processor comprise;

receiving, by a send thread, an identifier that identifies a destination node and a data pointer,

creating, by a send thread, a first send request in response to the receiving,

selecting, by the send thread, a selected channel from among a plurality of channels, wherein the selected channel comprises a selected hand-off queue and a selected identification of a selected message unit, wherein the each of the plurality of channels comprise a respective hand-off queue and a respective identification of a respective different one of the plurality of message units, wherein the selecting further comprises selecting the selected channel via a hash function on the identifier of the destination node and an identifier of a set of nodes to which the node and the destination node belong, wherein the selected hand-off queue is randomly accessible,

if the selected hand-off queue contains an available entry, adding, by the send thread, the first send request to the selected hand-off queue, and

if the selected hand-off queue does not contain an available entry, removing, by the send thread, a second send request from the selected hand-off queue and sending the second send request to the selected message unit identified by the selected identification in the selected channel, wherein the selected message unit sends the data pointed to by the data pointer to the destination node asynchronously from execution of the send thread.

19. The node of claim 18, wherein the instructions further comprise:

determining whether the selected hand-off queue contains the available entry, wherein the determining further comprises determining whether a tail counter is not equal to a size of the hand-off queue minus a head counter.

20. The node of claim 18, wherein the instructions further comprise:

removing, by an injection thread, the first send request from the selected hand-off queue and sending the first send request to the selected message unit, wherein the removing the first send request further comprises incrementing a tail counter of the selected hand-off queue mod a size of the selected hand-off queue.

21. The node of claim 18, wherein the adding the first send request to the selected hand-off queue further comprises:

incrementing a head counter of the selected hand-off queue mod a size of the selected hand-off queue.

22. The node of claim 18, wherein the receiving receives the identifier of the destination node and the data pointer from an application that executes synchronously within the send thread.

23. The node of claim 20, wherein the send thread and the injection thread comprise different threads that execute asynchronously from each other.

24. The node of claim 20, wherein the send thread and the injection thread comprise a same thread.