Systems and methods for multiresolution priority queues

1. A method for queuing elements for processing thereof according to element priorities, the method comprising the steps of:

(a) in a plurality of priority groups, wherein at least one priority group corresponds to a plurality of distinct priorities, determining a first priority group corresponding to a first new element that is to be queued;

(b) determining a first slot in a contiguous 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) when 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, by storing immediately before the first slot a pointer to a memory location in the queue of the first new element, maintaining contiguity of the look-up table;

(d) when the first slot is empty:

(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, maintaining contiguity of the look-up table; 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. 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 an element to be extracted, by setting the element to be extracted as the specified element; and

concurrently initiating extraction of the element to be extracted and one or more of steps (c)(1)-(2) or (d)(2)-(4) for the first new element when the first and second locksets do not overlap.

12. 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 a first element to be extracted, by setting the first element to be extracted 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 element to be extracted, by setting the second element to be extracted as the specified element; and

concurrently initiating extraction of the first and second elements to be extracted when the first and second locksets do not overlap.

13. The method of claim 1 , further comprising extracting a specified element that is to be extracted by:

(e) determining a priority group corresponding to the specified element;

(f) determining an extraction slot in the look-up table that corresponds to the priority group corresponding to the specified element;

(g) determining that the extraction slot contains a pointer to the specified element; and

(h) if a previous element associated with the specified element belongs to the priority group corresponding to the specified element, storing in the extraction slot a pointer to a memory location in the queue of the previous element and otherwise storing in the extraction slot a NULL pointer.

14. The method of claim 13 , further comprising setting a next element of a sentinel element in the queue as the specified element that is to be extracted.

15. The method of claim 1 , further comprising:

extracting at least one element from the queue, the element comprising a task to be executed or a data element to be processed, for execution or processing of the extracted element by a specialized computer selected from the group consisting of: a parallel computer comprising a plurality of processors, a distributed computer, and an event-driven computer.

16. 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) in a plurality of priority groups, wherein at least one priority group corresponds to a plurality of distinct priorities, determine a first priority group corresponding to a first new element that is to be queued;

(b) determine a first slot in a contiguous 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) when 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, by storing immediately before the first slot a pointer to a memory location in the queue of the first new element, to maintain contiguity of the look-up table;

(d) when the first is empty:

(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, to maintain contiguity of the look-up table; and

(4) store in the first slot a pointer to a memory location in the queue of the first new element.

17. The system of claim 16 , 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.

18. 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

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.

19. The system of claim 18 , wherein to decrease the highest global priority, the instructions program the processing unit to increase a value indicative of priority.

20. The system of claim 18 , wherein to decrease the highest global priority, the instructions program the processing unit to decrease a value indicative of priority.

21. The system of claim 16 , 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.

22. The system of claim 21 , 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.

23. The system of claim 16 , 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.

24. The system of claim 16 , 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.

25. The system of claim 24 , 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.

26. The system of claim 24 , 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 an element to be extracted, by setting the element to be extracted as the specified element; and

concurrently initiate extraction of the element to be extracted and one or more of operations (c)(1)-(2) or (d)(2)-(4) for the first new element when the first and second locksets do not overlap.

27. The system of claim 24 , 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 a first element to be extracted, by setting the first element to be extracted 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 element to be extracted, by setting the second element to be extracted as the specified element; and

concurrently initiate extraction of the first and second elements to be extracted when the first and second locksets do not overlap.

28. The system of claim 16 , wherein the instructions further program the processing unit to extract a specified element that is to be extracted and, to extract the specified element, the instructions program the processing unit to:

(e) determine a priority group corresponding to the specified element;

(f) determine an extraction slot in the look-up table that corresponds to the priority group corresponding to the specified element;

(g) determine that the extraction slot contains a pointer to the specified element; and

(h) if a previous element associated with the specified element belongs to the priority group corresponding to the specified element, store in the extraction slot a pointer to a memory location in the queue of the previous element and otherwise store in the extraction slot a NULL pointer.

29. The system of claim 28 , wherein the instructions further program the processing unit to: set a next element of a sentinel element in the queue as the specified element that is to be extracted.

30. The system of claim 16 , wherein the instructions further program the processing unit to:

extract at least one element from the queue, the element comprising a task to be executed or a data element to be processed, for execution or processing of the extracted element by a specialized computer selected from the group consisting of: a parallel computer comprising a plurality of processors, a distributed computer, and an event-driven computer.