Parallel priority queue utilizing parallel heap on many-core processors for accelerating priority-queue-based applications
AssigneeGeorgia State University Research Foundation, Inc.
InventorsSushil K. Prasad, Xi He, Dinesh Agarwal
Life of this patent
Estimating the term…
Abstract
Disclosed are various embodiments for a parallel priority queue implemented on one or more many-core processors and/or multi-core processors such as those in general-purpose graphics processing units (GPGPUs). According to various embodiments, a priority may be determined according to a timestamp of an item, such as an event or an entry, in a priority queue. A priority queue interface may comprise functions to insert and remove entries from the priority queue. Priority order of the entries may be maintained as the entries are inserted and removed from the queue.
Claims20
A parallel heap system, comprising:
- a host processor;
- a graphics processing unit (GPU) comprising a many-core architecture;
- kernel code executable on the GPU that, when executed, causes the GPU to implement a priority queue as a parallel heap, wherein the priority queue maintains an order of priority as a plurality of queue entries are inserted and deleted from the priority queue;
- and
- host code executable on the host processor that, when executed, causes the host processor to synchronize operations of the priority queue and the parallel heap.
A method, comprising:
- implementing, by a graphics processing unit (GPU) comprising a plurality of streaming multi-core processors, a priority queue as a parallel heap, wherein the priority queue comprises a programmatic interface for retrieving, inserting, and deleting a plurality of queue entries and maintaining priority order as the plurality of queue entries are inserted and deleted from the priority queue;
- and
- synchronizing, by a host processor in communication with the GPU, operations on the parallel heap.
A method for priority-based processing of data, comprising:
- notifying, by a priority queue application, a queue controller when one or more new items are ready for insertion into a parallel heap;
- suspending, by the queue controller, the priority queue application after the notification;
- requesting, by the queue controller, a parallel heap manager to merge the one or new items with items at a root node of the parallel heap;
- receiving, by the queue controller, a plurality of R smallest items from the parallel heap manager after the parallel heap manager has completed the requested merge;
- resuming, by the queue controller, the suspended priority queue application with the plurality of R smallest items;
- and
- requesting, by the queue controller, the parallel heap manager to begin a new delete-insert cycle to maintain the parallel heap.
Dependencies are inferred from the claim text.