The Synchronous Parallel Environment for Emulation and Discrete-Event Simulation (SPEEDES) is now using a new general-purpose priority queue data structure called the SPEEDES Qheap for managing its set of pending events in ascending time order. Empirical studies have shown this data structure to outperform more traditional priority queue data structures for large numbers of elements without breaking down.

Two operations are required of the SPEEDES Qheap:(1) Insertion of time-tagged events (time represents a priority of an event -- low time means high priority) and (2) Removal of the event with the smallest time tag. These operations help SPEEDES preserve causality since events, which may generate future events, must always be processed in ascending time order. The SPEEDES Qheap is composed of two lists: (1) a temporary list denoted as Qtemp and (2) a primary list denoted as Qheap.

Insertions are always accomplished in constant time by adding the inserted event to the bottom of Qtemp. The minimum time tag of Qtemp is always maintained. If the newly inserted event has a smaller time tag than the previous value, the minimum time-tag value is updated. Removal of events is more complicated. There are two cases.

Case 1:

If the event with the smallest time tag is in Qtemp, then Qtemp is sorted using a very fast merge-sort algorithm for linked lists. The event with the smallest time tag is removed from Qtemp and returned as the next event. The rest of Qtemp is Metasized into a single Metaitem that is inserted into Qheap. Note that the newly formed metaitem is actually a sorted list of events. The time tag of the metaitem is defined as the time tag of the first event in its sorted list. If the number of metaitems in Qheap ever grows larger than a specified value, S, then the metaitems in Qheap are further metasized into a single metaitem so that the number of metaitems in Qheap is reduced back to one. This helps keep Qheap small enough so that straight insertion of metaitems remains efficient. Metaitems may contain lists of other metaitems, which can contain lists of other metaitems, etc. In this way, Qheap is a recursively linked list data structure that adheres to the heap property.

Case 2:

The event with the smallest time tag is in Qheap. This is more difficult since it is possible that the item removed from the top ofQheap is actually a metaitem itself. If this is so, then the metaitem must be untangled by removing its top item, redefining the rest of the list of the metaitem as a new metaitem, making sure that Qheap does not have more than S elements (if it does, then the elements in Qheap are turned into a single metaitem and placed back into Qheap as a single element), and then inserting this new metaitem back into Qheap. The untangling procedure is repeated until a single event is obtained.

Because heaps are known to have worst-case log2(n)amortized behavior, this data structure should never break down. Also, because it is composed exclusively of linked lists, it should have very low overheads. There are no complicated rotation operations or arbitrary balancing heuristics to apply. This data structure does not require resizable arrays or modular arithmetic schemes either. The only (slightly) complicated part of the SPEEDES Qheap is the untangling procedure (which is actually very straight-forward). Because of its nice properties, the SPEEDES Qheap is highly recommended for general-event list management in discrete-event simulations and for other applications that require general-purpose priority queues. Provided below is a step-by-step procedure for implementing the SPEEDES Qheap.

SPEEDES Qheap Insertion

  1. Place the event to be inserted at the end of the Qtemp.
  2. Update Tmin if this item has the smallest time tag out of all the items in Qtemp.

SPEEDES Qheap Removal

  1. Check if Tmin is less than the time tag of the next item in Qheap. If so, perform steps a through f and then return. Otherwise, go on to step 2.
    1. Sort Qtemp and then set Tmin to infinity.
    2. Remove the top element (this is what is returned as the next event) and call it NextEvent.
    3. Metasize the rest of the elements from Qtemp into a new metaitem called Metatemp.
    4. Check if Qheap already contains S elements. If it does, metasize all of its elements into a new metaitem and place it back into Qheap as its only element.
    5. Insert Metatemp into Qheap.
    6. Return NextEvent.
  2. Remove the top item from Qheap and call it NextItem. Then loop over steps a through e below until NextItem is not a metaitem.
    1. Check if NextItem is a metaitem. If not, then break out of the loop and return NextItem as the NextEvent. Otherwise, we know that NextItem is a metaitem which must be untangled in the steps b-e below.
    2. Remove the top element from NextItem and call it NewItem. NextItem now contains one less item. If NextItem has only a single element, then unmetasize it so that NextItem is a regular item.
    3. Check if Qheap already contains S elements. If it does, metasize all of its elements into a new metaitem and place it back into Qheap as its only element.
    4. Insert NextItem into Qheap.
    5. Set NextItem = NewItem and then go back to a.

This work was done by Jeffrey S. Steinman of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com under the category Information Sciences

NPO-20095


NASA Tech Briefs Magazine

This article first appeared in the January, 1999 issue of NASA Tech Briefs Magazine.

Read more articles from the archives here.