MESSAGE SELECTION FOR INTER-THREAD COMMUNICATION IN A MULTITHREADED PROCESSOR

• US 20100333099A1
• Filed: 06/30/2009
• Published: 12/30/2010
• Est. Priority Date: 06/30/2009
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ziegler, Frederick Jacob, Kupferschmidt, Mark Gary, Schardt, Paul Emery, Mejdrich, Eric Oliver
• Granted Patent: US 8,495,643 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 2209/547 Messaging middleware
• CPC Class Codes: G06F 9/546 Message passing systems or structures, e.g. queues

Abstract

A method and circuit arrangement process a workload in a multithreaded processor that includes a plurality of hardware threads. Each thread receives at least one message carrying data to process the workload through a respective inbox from among a plurality of inboxes. A plurality of messages are received at a first inbox among the plurality of inboxes, wherein the first inbox is associated with a first thread among the plurality of hardware threads, and wherein each message is associated with a priority. From the plurality of received messages, a first message is selected to process in the first thread based on that first message being associated with the highest priority among the received messages. A second message is selected to process in the first thread based on that second message being associated with the earliest time stamp among the received messages and in response to processing the first message.

Claims

1. A method of processing a workload in a multithreaded processor of the type that includes a plurality of hardware threads, each of the plurality of hardware threads configured to receive at least one message carrying data to process the workload through a respective inbox from among a plurality of inboxes, the method comprising:

receiving a plurality of messages at a first inbox among the plurality of inboxes, wherein the first inbox is associated with a respective first hardware thread among the plurality of hardware threads, and wherein each of the plurality of messages includes a priority associated therewith;

from the plurality of received messages, selecting a first message among the plurality of received messages to process in the first hardware thread based on the first message being associated with a highest priority among the plurality of received messages; and

in response to processing the first message, selecting a second message among the plurality of messages to process in the first hardware thread based on the second message being associated with an earliest time stamp among the plurality of received messages.

2. The method of claim 1, wherein selecting the first message based on the first message being associated with the highest priority among the plurality of received messages includes:

determining that two or more messages among the plurality of messages are associated with the highest priority among the plurality of received messages; and

selecting the first message among the two or more messages to process in the first hardware thread based on the first message being associated with an earliest time stamp among the two or more messages.

3. The method of claim 1, wherein selecting the second message based on the second message being associated with the earliest time stamp among the plurality of received messages includes:

determining that two or more messages among the plurality of messages are associated with the earliest time stamp; and

selecting the second message among the two or more messages to process in the first hardware thread based on the second message being associated with the highest priority among the two or more messages.

4. The method of claim 1, further comprising:

configuring the first hardware thread to process at least a portion of a software pipeline.

5. A method of processing a workload in a multithreaded processor of the type that includes a plurality of hardware threads, each of the plurality of hardware threads configured to receive at least one prioritized message carrying data to process the workload through a respective priority message buffer from among a plurality of priority message buffers, each of the plurality of hardware threads configured to receive at least one message carrying data to process the workload through a respective inbox from among a plurality of inboxes, the method comprising:

receiving a plurality of prioritized messages at a first priority message buffer among the plurality of priority message buffers, wherein the first priority message buffer is associated with a respective first hardware thread among the plurality of hardware threads, and wherein each of the prioritized messages includes a priority associated therewith;

receiving a plurality of messages at a first inbox among the plurality of inboxes, wherein the first inbox is associated with the first hardware thread, and wherein each of the plurality of messages does not include a priority associated therewith;

from the plurality of received prioritized messages, selecting a first prioritized message among the plurality of received prioritized messages to process in the first hardware thread based on the first prioritized message being associated with a highest priority among the plurality of received prioritized messages; and

in response to processing the first prioritized message, selecting a first message among the plurality of received messages and the plurality of received prioritized messages to process in the first hardware thread based on the first message being associated with an earliest time stamp among the plurality of received messages and the plurality of received prioritized messages.

6. The method of claim 5, wherein selecting the first prioritized message based on the first message prioritized being associated with the highest priority among the plurality of received prioritized messages includes:

determining that two or more prioritized messages among the plurality of prioritized messages are associated with the highest priority among the plurality of received prioritized messages; and

selecting the first prioritized message among the two or more prioritized messages to process in the first hardware thread based on the first prioritized message being associated with an earliest time stamp among the two or more prioritized messages.

7. The method of claim 5, wherein selecting the first message based on the first message being associated with an earliest time stamp among the plurality of received messages and the plurality of received prioritized messages includes:

determining that two or more messages among the plurality of received messages and the plurality of received prioritized messages are associated with the earliest time stamp; and

selecting the first message among the two or more messages to process in the first hardware thread based on the first message being associated with the highest priority among the two or more messages.

8. The method of claim 7, wherein the first message is a second prioritized message.

9. The method of claim 5, further comprising:

configuring the first hardware thread to process at least a portion of a software pipeline.

10. A circuit arrangement, comprising:

a plurality of hardware threads configured to process a workload;

a plurality of inboxes in communication with the respective plurality of hardware threads, each of the plurality of inboxes configured to receive a plurality of messages; and

control logic disposed in each of the plurality of hardware threads and configured to, during processing of at least a portion of the workload in a first hardware thread among the plurality of hardware threads, select a first message among a plurality of messages received at a respective first inbox among the plurality of inboxes to process in the first hardware thread based on the first message being associated with a highest priority among the plurality of received messages and, in response to processing the first message, select a second message among the plurality of messages to process in the first hardware thread based on the second message being associated with an earliest time stamp among the plurality of received messages.

11. The circuit arrangement of claim 10, the control logic further configured to determine that two or more messages among the plurality of messages are associated with the highest priority among the plurality of received messages and select the first message among the two or more messages to process in the first hardware thread based on the first message being associated with an earliest time stamp among the two or more messages.

12. The circuit arrangement of claim 10, the control logic further configured to determine that two or more messages among the plurality of messages are associated with the earliest time stamp among the plurality of received messages and select the second message among the two or more messages to process in the first hardware thread based on the second message being associated with the highest priority among the two or more messages.

13. A program product comprising a computer readable medium and program code resident on the computer readable medium and defining the circuit arrangement of claim 10.

14. An integrated circuit device comprising the circuit arrangement of claim 10.

15. The integrated circuit device of claim 14, wherein the integrated circuit device further comprises:

an interconnected set of hardware-based processing elements,

wherein the first hardware thread is disposed on at least one hardware-based processing element of the interconnected set of hardware-based processing elements.

16. The integrated circuit device of claim 15, wherein the interconnected set of hardware-based processing elements comprises a plurality of nodes interconnected to one another in a Network On Chip (NOC) arrangement.

17. The integrated circuit device of claim 16, wherein at least a subset of the plurality of hardware threads are configured in at least a portion of a software pipeline such that the first hardware thread is configured in the at least a portion of the software pipeline.

18. A circuit arrangement, comprising:

a plurality of hardware threads configured to process a workload;

a plurality of priority message buffers in communication with the respective plurality of hardware threads, each of the plurality of priority message buffers configured to receive a plurality of prioritized messages;

a plurality of inboxes in communication with the respective plurality of hardware threads, each of the plurality of inboxes configured to receive a plurality of messages; and

control logic disposed in each of the plurality of hardware threads and configured to, during processing of at least a portion of the workload in a first hardware thread among the plurality of hardware threads, select a first prioritized message among the plurality of prioritized messages received at a respective first priority message buffer among the plurality of priority message buffers to process in the first hardware thread based on the first prioritized message being associated with a highest priority among the plurality of received prioritized messages, and select a first message among the plurality of messages received at a respective first inbox among the plurality of inboxes and the plurality of received prioritized messages to process in the first hardware thread based on the first message being associated with an earliest time stamp among the plurality of received messages and the plurality of received prioritized messages.

19. The circuit arrangement of claim 18, wherein the first message is a second prioritized message.

20. The circuit arrangement of claim 18, the control logic further configured to determine that two or more prioritized messages among the plurality of prioritized messages are associated with the highest priority among the plurality of received prioritized messages and select the first prioritized message among the two or more prioritized messages to process in the first hardware thread based on the first prioritized message being associated with an earliest time stamp among the two or more prioritized messages.

21. The circuit arrangement of claim 18, the control logic further configured to determine that two or more messages among the plurality of received messages and the plurality of received prioritized messages are associated with the earliest time stamp and select the first message among the two or more messages to process in the first hardware thread based on the first message being associated with the highest priority among the two or more messages.

22. The circuit arrangement of claim 21, wherein the first message is a second prioritized message.

23. A program product comprising a computer readable medium and program code resident on the computer readable medium and defining the circuit arrangement of claim 18.

24. An integrated circuit device comprising the circuit arrangement of claim 18.

25. The integrated circuit device of claim 24, wherein the integrated circuit device further comprises:

an interconnected set of hardware-based processing elements,

wherein the first hardware thread is disposed on at least one hardware-based processing element of the interconnected set of hardware-based processing elements.

26. The integrated circuit device of claim 25, wherein the interconnected set of hardware-based processing elements comprises a plurality of nodes interconnected to one another in a Network On Chip (NOC) arrangement.

27. The integrated circuit device of claim 26, wherein at least a subset of the plurality of hardware threads are configured in at least a portion of a software pipeline such that the first hardware thread is configured in the at least a portion of the software pipeline.