Dynamic calendar queue

Seung Hyun Oh, Jong Suk Ahn

Research output: Contribution to journalConference articlepeer-review

25 Scopus citations

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 languageEnglish
Pages (from-to)20-25
Number of pages6
JournalProceedings of the IEEE Annual Simulation Symposium
StatePublished - 1999
EventProceedings of the 32nd Annual Simulation Symposium - San Diego, CA, USA
Duration: 11 Apr 199915 Apr 1999

Fingerprint

Dive into the research topics of 'Dynamic calendar queue'. Together they form a unique fingerprint.

Cite this