|
Abstract 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 of Qheap 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.
<<
back | 
