R.S.M. Goh and I. L.-J. Thng (Singapore)
Simulation methodology, priority queue, discrete eventsimulation.
Priority queues are widely employed in numerous
applications such as discrete event simulations (DESs).
The priority queue structure plays a paramount role of
managing the pending event set of a DES. The priority
queue contains events where the minimum timestamp
event has the highest priority and the maximum
timestamp event has the lowest priority. A Calendar
Queue (CQ) is a useful structure often employed in DESs.
Its popularity is due to its expected O(1) access time for
many simulation scenarios, provided the events are evenly
distributed in the CQ structure. However, for skewed
distributions, it is likely that many events fall into some
few buckets in the CQ structure. This may cause the
performance of the CQ to deteriorate to O(n).
Furthermore, the CQ's resize operation necessary to
handle fluctuating queue sizes is costly as it copies all the
already sorted events from the old CQ structure to a
newly-created one. This article introduces a novel priority
queue implementation known as the Dynamic Cost-based
Multi-Tier Linked List (DynamicList) structure which
does not require the resize operation to obtain near O(1)
performance. The DynamicList is empirically shown to be
on the average at least 100% faster than all the current
priority queues. In some scenarios, the DynamicList is
more than one magnitude faster. These evidence suggest
strongly that it is an excellent candidate to be widely
employed in DESs.