Browse Prior Art Database

An Event Scanning Algorithm of Nearly Constant Complexity November

IP.com Disclosure Number: IPCOM000128530D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 5 page(s) / 22K

Publishing Venue

Software Patent Institute

Related People

William R. Frenta: AUTHOR [+4]

Abstract

In recent publications, several algorithms have been presented for the realization of event scheduling routines suitable for general purpose discrete event simulation systems. Several exhibited a performance superior to commonly used simple linked list algorithms. In this paper a new event scheduling algorithm is presented which improves on two aspects of the best of the previously published algorithms. First the new algorithm s performance is quite insensitive to skewed distributions, and second, its time complexity is nearly constant. Test results showing its superior performance are included. key words and phrases: simulation, time flow mechanisms, event scanning mechanisms, multi-linked lists CR Categories 3.34, 4.22, 5,5, $.1

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 23% of the total text.

Page 1 of 5

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

An Event Scanning Algorithm of Nearly Constant Complexity November

By William R. Frenta and Kurt Maly

0400218 Computer, Information, and Control Sciences Department Institute of Technology

114 Lind Hall University of Minnesota Minneapolis, Minnesota 55455, 1975 Cover design courtesy of Ruth and Jay Leavitt and Kurt Maly An Event Scanning Algorithm of Nearly Constant Complexity

by W.R. Franta and Kurt Maly

Abstract

In recent publications, several algorithms have been presented for the realization of event scheduling routines suitable for general purpose discrete event simulation systems. Several exhibited a performance superior to commonly used simple linked list algorithms. In this paper a new event scheduling algorithm is presented which improves on two aspects of the best of the previously published algorithms. First the new algorithm s performance is quite insensitive to skewed distributions, and second, its time complexity is nearly constant. Test results showing its superior performance are included. key words and phrases: simulation, time flow mechanisms, event scanning mechanisms, multi-linked lists

CR Categories 3.34, 4.22, 5,5, $.

I. Introduction

Two recent communications articles [2,3] investigated the possibility of providing efficient event scheduling routines for general purpose discrete event simulation systems. Both papers suggest that the most promising algorithms are those which use an index pointer to determine a list or sub-list into which the event notice :being scheduled is to be placed (see method B and C of [3] and the indexed list algorithm of [2]). Following the indexed selection of a list or sub-list, a linear search is used to determine the exact placement of the event notice in the selected list or sub- :List. For these algorithms, consecutive indices span a time interval of width dt, and they operate on the basis of a fixed number, du, of indices. The papers leave as an open problem an operational procedure for the specifica-tion of dt, and du in the face of the perhaps dynamic but.usually unknown distribution of event times for the totality of scheduled events. In fact, in [2J the authors observe that before their indexed list algorithm can be used in a general purpose simulation system an adaptive mechanism must be devised to set the parameters according to the operating conditions. Alternately we note that if the scheduling algorithms ,are robust, i.e. insensitive to a wide spectrum of operating conditions, their measured performance will remain constant (or nearly so) over a range of actual parameter values. One problem with previous approaches is the fact that worst case performance is identical to the simple linear list approach, and furthermore, for skewed distributions (which in real situations occur quite frequently) the performance rapidly deteriorates with an increase in n, the number of events in the list. In section II we pres...