Title

Smart priority queue algorithms for self-optimizing event storage

Authors

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