Fast and linearizable concurrent priority queue via dynamic aggregation of operations

• US 8,387,057 B2
• Filed: 12/16/2010
• Issued: 02/26/2013
• Est. Priority Date: 12/16/2010
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Wilmarth, Terry
• Primary Examiner(s): TO, JENNIFER N
• Application Number:
  US12/970,691
• Publication Number:
  US 20120159498A1
• Time in Patent Office: 803 Days
• Field of Search: None
• US Class Current: 718/102
• CPC Class Codes: G06F 9/526 Mutual exclusion algorithms

Abstract

Embodiments of the invention improve parallel performance in multi-threaded applications by serializing concurrent priority queue operations to improve throughput. An embodiment uses a synchronization protocol and aggregation technique that enables a single thread to handle multiple operations in a cache-friendly fashion while threads awaiting the completion of those operations spin-wait on a local stack variable, i.e., the thread continues to poll the stack variable until it has been set or cleared appropriately, rather than rely on an interrupt notification. A technique for an enqueue/dequeue (push/pop) optimization uses re-ordering of aggregated operations to enable the execution of two operations for the price of one in some cases. Other embodiments are described and claimed.

Claims

1. A computer implemented system, comprising:

a processor coupled to memory, the processor configured to execute multi-threaded application programs;

a multi-threaded application executing on the processor, the multi-threaded application program configured to utilize a concurrent entity, and wherein a plurality of threads of the multi-threaded application are configured to generate a plurality of operation nodes to operate upon the concurrent entity concurrently with other threads;

a synchronization and aggregation logic component coupled to the multi-threaded application and configured to accept operation nodes from the plurality of threads, each operation node corresponding to a single thread, the accepted operation nodes to be placed in a temporary list, the operation nodes defining an operation to perform on the concurrent entity, wherein only one thread, known as a handler thread, is permitted to operate on the temporary list to perform the operations on the concurrent entity, and wherein each thread is permitted to provide only one operation node to the temporary list and waits until the corresponding operation node has been processed by the handler thread before being permitted to provide another operation node to a second temporary list; and

the concurrent entity stored in the memory accessible to the multi-threaded application program, wherein the concurrent entity comprises a concurrent priority queue configured to accept enqueue and dequeue operations, and wherein each operation node comprises one of either an enqueue or dequeue operation.

2. The system as recited in claim 1, wherein the handler thread is configured to poll a handler_busy flag to determine whether operation on the temporary list is to commence, and wherein the handler thread for the temporary list is a thread having added an operation node to the temporary list before any other thread.

3. The system as recited in claim 1, wherein a thread is configured to poll a ready flag after placing an operation node on the temporary list, the ready flag being an indicator of whether the thread is permitted to continue operation, and wherein the handler thread is configured to reset the ready flag corresponding to the thread after processing the operation node from the temporary list.

4. The system as recited in claim 1, wherein the handler thread is configured to retrieve the temporary list into a new pointer object, and to replace the original temporary list with an empty list, both via an atomic operation.

5. The system as recited in claim 1, wherein the threads are configured to place an operation node in the temporary list via an atomic operation.

6. The system as recited in claim 1, further comprising:

an enqueue/dequeue optimization logic component coupled to the multi-threaded application and having access to the concurrent priority queue, wherein the handler thread is configured to operate on the temporary list to process both enqueue operation nodes as they apply to the concurrent priority queue as well as constant-time dequeue operations, prior to operating on non-constant-time dequeue operations, before re-sorting items in the concurrent priority queue, and wherein enqueue operations are performed before all non-constant time dequeue operations, and wherein the handler thread is further configured to provide a fully heap-sorted concurrent priority queue to the multi-threaded application after performing all operation nodes and re-sorting the concurrent priority queue.

7. The system as recited in claim 6, wherein the concurrent priority queue comprises an array data structure stored in the memory, where, when non-empty, at least a portion of the array elements are sorted into a heap.

8. The system as recited in claim 7, wherein the hander thread is configured to process enqueue and dequeue operation nodes from the temporary list one at a time, wherein enqueue operation nodes are added to an unsorted portion of the concurrent priority queue until a dequeue operation node is processed, and wherein when a last item added to the unsorted portion of the priority queue has a higher priority than a highest priority item in the heap, the thread is configured to perform a dequeue operation by returning the last enqueued item added to the unsorted portion, and when all enqueue operation items have been added to the unsorted portion of the concurrent priority queue, then performing any remaining dequeue operation nodes and re-sort the heap portion of the concurrent priority queue as operation nodes are removed from the heap.

9. A computer implemented system, comprising:

a processor coupled to memory, the processor configured to execute multi-threaded application programs;

a multi-threaded application executing on the processor, the multi-threaded application program configured to utilize a concurrent priority queue stored in the memory and configured to accept enqueue and dequeue operations, and wherein a plurality of threads of the multi-threaded application are configured to generate a plurality of operation nodes to operate upon the concurrent priority queue concurrently with other threads, and wherein each operation node comprises one of either an enqueue or dequeue operation;

an enqueue/dequeue optimization logic component coupled to the multi-threaded application and having access to the concurrent priority queue, wherein a handler thread is configured to operate on the temporary list to process both enqueue operation nodes as they apply to the concurrent priority queue as well as constant-time dequeue operations, prior to operating on non-constant-time dequeue operations, before re-sorting items in the concurrent priority queue, and wherein enqueue operations are performed before all non-constant time dequeue operations, and wherein the handler thread is further configured to provide a fully sorted concurrent priority queue to the multi-threaded application after performing all operation nodes and re-sorting the concurrent priority queue.

10. The system as recited in claim 9, wherein the concurrent priority queue comprises an array data structure stored in the memory, where, when non-null, at least a portion of the array elements are sorted into a heap.

11. The system as recited in claim 10, wherein the handler thread is configured to process enqueue and dequeue operation nodes from the temporary list one at a time, wherein enqueue operation nodes are added to an unsorted portion of the concurrent priority queue until a dequeue operation node is processed, and wherein when a last item added to the unsorted portion of the priority queue has a higher priority than a highest priority item in the heap, the thread is configured to perform a dequeue operation by returning the last enqueued item added to the unsorted portion, and when all enqueue operation items have been added to the unsorted portion of the concurrent priority queue, then performing any remaining dequeue operation nodes and re-sort the heap portion of the concurrent priority queue as operation nodes are removed from the heap.

12. The system as recited in claim 9, wherein the handler thread is further configured to reset a handler_busy flag after completing processing of the temporary list, the handler_flag to indicate that a waiting thread may commence processing on a second temporary list comprising operation nodes.

13. The system as recited in claim 9, further comprising:

a synchronization and aggregation logic component coupled to the multi-threaded application and configured to accept operation nodes from the plurality of threads, each operation node corresponding to a single thread, the accepted operation nodes to be placed in a temporary list, the operation nodes defining an operation to perform on the concurrent priority queue, wherein only one thread, known as a handler thread, is permitted to operate on the temporary list to perform the operations on the concurrent priority queue, and wherein each thread is permitted to provide only one operation node to the temporary list and waits until the corresponding operation node has been processed by the handler thread before being permitted to provide another operation node to a second temporary list; and

the temporary list stored in the memory accessible to the enqueue/dequeue optimization logic component for processing with the concurrent priority queue.

14. The system as recited in claim 13, wherein the handler thread is configured to poll a handler_busy flag to determine whether operation on the temporary list is to commence, and wherein the handler thread for the temporary list is a thread having added an operation node to the temporary list before any other thread.

15. The system as recited in claim 13, wherein a thread is configured to poll a ready flag after placing an operation node on the temporary list, the ready flag being an indicator of whether the thread is permitted to continue operation, and wherein the handler thread is configured to reset the ready flag corresponding to the thread after processing the operation node from the temporary list.

16. The system as recited in claim 13, wherein the handler thread is configured to retrieve the temporary list into a new pointer, and to leave behind an initially empty list comprising the second temporary list, both via an atomic operation.

17. The system as recited in claim 13, wherein the threads are configured to place an operation node in the temporary list via an atomic operation.

18. A non-transitory machine accessible medium having instructions stored thereon, the instructions when executed on a machine, cause the machine to:

add operation nodes to a temporary list, by at least one thread of a plurality of threads executing in a multi-threaded application running on the machine;

assign a first thread that added an operation node to the temporary list a role as handler thread for the temporary list;

wait by the handler thread for a flag indicating processing of the temporary list is permitted to commence;

retrieve the temporary list and generate an initially empty second temporary list, by the handler thread, in an atomic operation, when the flag indicates processing of the temporary list is permitted to commence, wherein the second temporary list is to receive operation nodes by at least one thread when the at least one thread does not have an unprocessed operation node on the retrieved temporary list; and

process the temporary list by the handler thread into a concurrent entity, wherein the concurrent entity comprises a concurrent priority queue, and an operation node comprises either one of a dequeue or enqueue operation to be performed on the concurrent priority queue.

19. The medium as recited in claim 18, further comprising instructions to:

assign a second handler thread associated with the second temporary list upon the second handler thread having added a first operation node to the second temporary list; and

wait by the second handler thread until the temporary list has been processed by the handler thread before processing the second temporary list by the second handler thread.

20. The medium as recited in claim 18, wherein operation nodes are added to the temporary list by threads, via an atomic operation.

21. The medium as recited in claim 18, wherein the concurrent priority queue comprises an array data structure stored in the memory, where, when non-empty, at least a portion of the array elements are sorted into a heap.

22. The medium as recited in claim 21, further comprising instructions to:

process operation nodes in the temporary list by the handler thread, wherein enqueue operation nodes in the temporary list are added to the concurrent priority queue in constant time, and non-constant time dequeue operations in the temporary list are delayed until all constant-time enqueue and dequeue operation nodes in the temporary list have been processed by the handler thread; and

re-sort the concurrent priority queue after the temporary list has been processed by the handler thread, when necessary.

23. The medium as recited in claim 22, further comprising instructions to:

add enqueue operation items to an unsorted portion of the concurrent priority queue until a dequeue operation node is processed, and wherein when a last item added to the unsorted portion of the priority queue has a higher priority than a highest priority item in the heap, then perform a dequeue operation on the last enqueued item added to the unsorted portion; and

when all enqueue operation items have been added to the unsorted portion of the concurrent priority queue, then perform any remaining dequeue operation nodes and re-sort the heap portion of the concurrent priority queue as operation nodes are removed from the heap.

24. A non-transitory machine accessible medium having instructions stored thereon, the instructions when executed on a machine, cause the machine to:

process enqueue and dequeue operation nodes from a temporary list, the enqueue and dequeue operation nodes corresponding to operations to be performed on a concurrent priority queue associated with a multi-threaded application executing on the machine, the processing to be performed by a thread assigned to be a handler thread for the temporary list, and wherein the concurrent priority queue comprises an array data structure stored in memory, where, when non-empty, at least a portion of the array elements are sorted into a heap;

process operation nodes in the temporary list by the handler thread, wherein enqueue operation nodes in the temporary list are added to the concurrent priority queue in constant time, and non-constant time dequeue operations in the temporary list are delayed until all constant-time enqueue and dequeue operation nodes in the temporary list have been processed by the handler thread; and

re-sort the concurrent priority queue after the temporary list has been processed by the handler thread, when necessary.

25. The medium as recited in claim 24, further comprising instructions to:

add enqueue operation nodes to an unsorted portion of the concurrent priority queue until a dequeue operation node is processed, and wherein when a last item added to the unsorted portion of the priority queue has a higher priority than a highest priority item in the heap, then perform a dequeue operation returning the last enqueued item added to the unsorted portion; and

when all enqueue operation nodes have been added to the unsorted portion of the concurrent priority queue, then perform any remaining dequeue operation nodes and re-sort the heap portion of the concurrent priority queue as operation nodes are removed from the heap.

26. The medium as recited in claim 24, further comprising instructions to generate the temporary list, comprising:

assign a first thread that added an operation node to the temporary list a role as the handler thread for the temporary list;

wait by the handler thread for a flag indicating processing of the temporary list is permitted to commence; and

retrieve the temporary list and generate an initially empty second temporary list, by the handler thread, via an atomic operation, when the flag indicates processing of the temporary list is permitted to commence, wherein the second temporary list is to receive operation nodes by at least one thread when the at least one thread does not have an unprocessed operation node on the retrieved temporary list.

27. The medium as recited in claim 26, further comprising instructions to:

assign a second handler thread associated with the second temporary list upon the second handler thread having added a first operation node to the second temporary list; and

wait by the second handler thread until the temporary list has been processed by the handler thread before processing the second temporary list by the second handler thread.

28. The medium as recited in claim 26, wherein operation nodes are added to the temporary list by threads, via an atomic operation.