Title

Smart Priority Queue Algorithms For Self-Optimizing Event Storage

Keywords

Adaptive algorithm; Adaptive data structures; Calendar queue; Discrete event simulation; Event set optimization; Priority queue

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. © 2004 Elsevier B.V. All rights reserved.

Publication Date

4-1-2004

Publication Title

Simulation Modelling Practice and Theory

Volume

12

Issue

1

Number of Pages

15-40

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1016/j.simpat.2004.01.002

Socpus ID

1642586104 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/1642586104

This document is currently not available here.

Share

COinS