Systems and methods for multiresolution priority queues
A system for storing and extracting elements according to their priority takes into account not only the priorities of the elements but also three additional parameters, namely, a priority resolution p Δ and two priority limits p min and p max . By allowing an ordering error if the difference in the priorities of elements are within the priority resolution, an improvement in performance is achieved.
1. A method for queuing elements for processing thereof according to element priorities, the method comprising the steps of:
(a) determining a first priority group corresponding to a first new element that is to be queued;
(b) determining a first slot in a look-up table comprising a plurality of slots, at least one slot comprising a queue pointer, the first slot corresponding to the first priority group;
(c) if the first slot is not empty:
(1) selecting a first queued element corresponding to the first slot; and
(2) queuing in a queue the first new element immediately before the first queued element;
(d) otherwise:
(1) selecting from a first set of slots that are in the look-up table and that are associated with a set of priority groups each having a priority higher than the priority group corresponding to the first new element, a second slot that is not empty and that is associated with a lowest priority group in the first set of slots;
(2) selecting a second queued element corresponding to the second slot;
(3) queuing in the queue the first new element immediately after the second queued element; and
(4) storing in the first slot a pointer to a memory location in the queue of the first new element.
2. The method of claim 1 , wherein:
the plurality of slots is configured as an array or a binary tree;
each slot corresponds to a respective priority group; and
each non-empty slot holds a respective pointer to a respective element in the queue, the respective element having a priority belonging to the respective priority group.
3. The method of claim 1 , wherein the plurality of slots is associated with a highest global priority, the method further comprising:
decreasing the highest global priority;
determining a number of slots to be shifted by identifying one or more slots each of which has a priority associated therewith that is higher than the decreased highest global priority; and
if an index k of a candidate slot is less than a difference between a total number of slots in the look-up table and the number of slots to be shifted, storing in the candidate slot having the index k a pointer stored in another slot having an index k+ the number of slots to be shifted;
otherwise, storing in the candidate slot having the index k a NULL pointer.
4. The method of claim 3 , wherein decreasing the highest global priority comprises increasing a value indicative of priority.
5. The method of claim 3 , wherein decreasing the highest global priority comprises decreasing a value indicative of priority.
6. The method of claim 1 , wherein:
the look-up table is configured as a ring structure; and
determining the first slot in the look-up table comprises computing a modulus using a slot size of the look-up table.
7. The method of claim 6 , wherein the plurality of slots is associated with a highest global priority, the method further comprising:
decreasing the highest global priority;
determining a number of slots to be shifted by identifying one or more slots each of which has a priority associated therewith that is higher than the decreased highest global priority; and
incrementing a sentinel, that indicates an element associated with the highest global priority, to a slot location obtained by:
adding the number of slots to a current slot location of the sentinel; and
obtaining a modulus of the addition using the slot size of the look-up table.
8. The method of claim 1 , wherein:
the look-up table comprises a plurality of slot sets, comprising a first slot set and a second slot set;
a first resolution is associated with the first slot set, the first resolution comprising a ratio of: (a) a difference between highest and lowest priorities associated with the first slot set and (b) a number of slots in the first slot set; and
a second resolution is associated with the second slot set, the second resolution comprising a ratio of: (a) a difference between highest and lowest priorities associated with the second slot set and (b) a number of slots in the second slot set, the second resolution being different from the first resolution.
9. The method of claim 1 , further comprising determining a lockset associated with a specified element by:
determining a priority group corresponding to the specified element;
determining a first candidate lock slot in the look-up table, the first candidate lock slot corresponding to the priority group corresponding to the specified element;
selecting from a first candidate set of slots that are in the look-up table and that are associated with a set of priority groups each having a priority higher than the priority group corresponding to the specified element, a second candidate lock slot that is not empty and that is associated with a lowest priority in the first candidate set of slots;
locking the second candidate lock slot;
if the first candidate lock slot is not empty:
locking the first candidate lock slot;
otherwise:
selecting from a second candidate set of slots in the look-up table that are associated with a set of priority groups each having a priority lower than the priority group corresponding to the specified element, a third candidate lock slot that is not empty and that is associated with a highest priority group in the second candidate set of slots; and
locking the third candidate slot.
10. The method of claim 9 , further comprising:
determining a first lockset of slots in the look-up table that are to be locked and correspond to the first new element that is to be queued, by setting the first new element as the specified element;
determining a second lockset of slots in the look-up table that are to be locked and correspond to a second new element that is to be queued, by setting the second new element as the specified element; and
concurrently initiating one or more of steps (c)(1)-(2) or (d)(2)-(4) for both the first and second new elements when the first and second locksets do not overlap.
11. A system for queuing elements for processing thereof according to element priorities, the system comprising:
a first processor; and
a first memory in electrical communication with the first processor, the first memory comprising instructions which, when executed by a processing unit comprising at least one of the first processor and a second processor, and in electronic communication with a memory module comprising at least one of the first memory and a second memory, program the processing unit to:
(a) determine a first priority group corresponding to a first new element that is to be queued;
(b) determine a first slot in a look-up table comprising a plurality of slots, at least one slot comprising a queue pointer, the first slot corresponding to the first priority group;
(c) if the first slot is not empty:
(1) select a first queued element corresponding to the first slot; and
(2) queue in a queue the first new element immediately before the first queued element;
(d) otherwise:
(1) select from a first set of slots that are in the look-up table and that are associated with a set of priority groups each having a priority higher than the priority group corresponding to the first new element, a second slot that is not empty and that is associated with a lowest priority group in the first set of slots;
(2) select a second queued element corresponding to the second slot;
(3) queue in the queue the first new element immediately after the second queued element; and
(4) store in the first slot a pointer to a memory location in the queue of the first new element.
12. The system of claim 11 , wherein:
the plurality of slots is configured as an array or a binary tree;
each slot corresponds to a respective priority group; and
each non-empty slot holds a respective pointer to a respective element in the queue, the respective element having a priority belonging to the respective priority group.
13. The system of claim 11 , wherein the plurality of slots is associated with a highest global priority, and the instructions further program the processing unit to:
decrease the highest global priority;
determine a number of slots to be shifted by identifying one or more slots each of which has a priority associated therewith that is higher than the decreased highest global priority; and
if an index k of a candidate slot is less than a difference between a total number of slots in the look-up table and the number of slots to be shifted, store in the candidate slot having the index k a pointer stored in another slot having an index k+ the number of slots to be shifted;
otherwise, store in the candidate slot having the index k a NULL pointer.
14. The system of claim 13 , wherein to decrease the highest global priority, the instructions program the processing unit to increase a value indicative of priority.
15. The system of claim 13 , wherein to decrease the highest global priority, the instructions program the processing unit to decrease a value indicative of priority.
16. The system of claim 11 , wherein:
the look-up table is configured as a ring structure; and
to determine the first slot in the look-up table, the instructions program the processing unit to compute a modulus using a slot size of the look-up table.
17. The system of claim 16 , wherein the plurality of slots is associated with a highest global priority, and the instructions further program the processing unit to:
decrease the highest global priority;
determine a number of slots to be shifted by identifying one or more slots each of which has a priority associated therewith that is higher than the decreased highest global priority; and
increment a sentinel, that indicates an element associated with the highest global priority, to a slot location obtained by:
adding the number of slots to a current slot location of the sentinel; and
obtaining a modulus of the addition using the slot size of the look-up table.
18. The system of claim 11 , wherein:
the look-up table comprises a plurality of slot sets, comprising a first slot set and a second slot set;
a first resolution is associated with the first slot set, the first resolution comprising a ratio of: (a) a difference between highest and lowest priorities associated with the first slot set and (b) a number of slots in the first slot set; and
a second resolution is associated with the second slot set, the second resolution comprising a ratio of: (a) a difference between highest and lowest priorities associated with the second slot set and (b) a number of slots in the second slot set, the second resolution being different from the first resolution.
19. The system of claim 11 , wherein the instructions further program the processing unit to determine a lockset associated with a specified element and, to determine the lockset, the instructions program the processing unit to:
determine a priority group corresponding to the specified element;
determine a first candidate lock slot in the look-up table, the first candidate lock slot corresponding to the priority group corresponding to the specified element;
select from a first candidate set of slots that are in the look-up table and that are associated with a set of priority groups each having a priority higher than the priority group corresponding to the specified element, a second candidate lock slot that is not empty and that is associated with a lowest priority in the first candidate set of slots;
lock the second candidate lock slot;
if the first candidate lock slot is not empty:
lock the first candidate lock slot;
otherwise:
select from a second candidate set of slots in the look-up table that are associated with a set of priority groups each having a priority lower than the priority group corresponding to the specified element, a third candidate lock slot that is not empty and that is associated with a highest priority group in the second candidate set of slots; and
lock the third candidate slot.
20. The system of claim 19 , wherein the instructions further program the processing unit to:
determine a first lockset of slots in the look-up table that are to be locked and correspond to the first new element that is to be queued, by setting the first new element as the specified element;
determine a second lockset of slots in the look-up table that are to be locked and correspond to a second new element that is to be queued, by setting the second new element as the specified element; and
concurrently initiate one or more of operations (c)(1)-(2) or (d)(2)-(4) for both the first and second new elements when the first and second locksets do not overlap.