Abstract
Discrete event simulations need a priority queue sorting events according to their timestamp to process events in their time order. As the number of events increases, the choice of data structure for this event list can affect the simulation performance significantly. A calendar queue is one of data structures popularly used in most discrete event simulators due to its O(1) time complexity regardless of the number of stored events. Calendar queues, however, perform poorly over skewed event distributions due to the static resize algorithm and the inappropriate selection of events for measuring the degree of the event distribution. To improve the calendar queue's performance over uneven event distributions, this paper proposes two new mechanisms. We call our calendar queue adopting these two mechanisms DCQ (Dynamic Calendar Queue). Our experiment results showed that DCQ can achieve an order of magnitude speed-up for uneven distributions while performing as well over even distributions as the conventional calendar queue.
Original language | English |
---|---|
Pages (from-to) | 20-25 |
Number of pages | 6 |
Journal | Proceedings of the IEEE Annual Simulation Symposium |
State | Published - 1999 |
Event | Proceedings of the 32nd Annual Simulation Symposium - San Diego, CA, USA Duration: 11 Apr 1999 → 15 Apr 1999 |