Smart priority queue algorithms for self-optimizing event storage

    Authors

    H. A. Bahr;R. F. DeMara

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    Simul. Model. Pract. Theory

    Keywords

    discrete event simulation; event set optimization; adaptive data; structures; priority queue; adaptive algorithm; calendar queue; Computer Science, Interdisciplinary Applications; Computer Science, ; Software Engineering

    Abstract

    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.

    Journal Title

    Simulation Modelling Practice and Theory

    Volume

    12

    Issue/Number

    1

    Publication Date

    1-1-2004

    Document Type

    Article

    Language

    English

    First Page

    15

    Last Page

    40

    WOS Identifier

    WOS:000221089100002

    ISSN

    1569-190X

    Share

    COinS