Smart priority queue algorithms for self-optimizing event storage
Abbreviated Journal Title
Simul. Model. Pract. Theory
discrete event simulation; event set optimization; adaptive data; structures; priority queue; adaptive algorithm; calendar queue; Computer Science, Interdisciplinary Applications; Computer Science, ; Software Engineering
Low run-time overhead, self-adapting storage policies for priority queues called smart priority queue (SPQ) techniques are developed and evaluated. The proposed SPQ policies employ a low-complexity linear queue for near-head activities and a rapid-indexing variable bin-width calendar queue for distant events. The SPQ configuration is determined by monitoring queue access behavior using cost-scoring factors and then applying heuristics to adjust the organization of the underlying data structures. To illustrate and evaluate the method, an SPQ-based scheduler for discrete event simulation has been implemented and was used to assess the resulting efficiency, components of access time, and queue usage distributions of the existing and proposed algorithms. Results indicate that optimizing storage to the spatial distribution of queue access can decrease HOLD operation cost between 25% and 250% over existing algorithms such as calendar queues. (C) 2004 Elsevier B.V. All rights reserved.
Simulation Modelling Practice and Theory
"Smart priority queue algorithms for self-optimizing event storage" (2004). Faculty Bibliography 2000s. 4191.