Efficient parallel algorithms and data structures for discrete-event simulation

Abstract

Discrete-event simulation, which is a major tool for analysis, prediction, and training, has been demanding increasingly high computational resources. It has continued to defy an efficient parallel solution. A long-st anding serial bottleneck in parallelizing event-driven simulation ,va.s the shared data structure - event-queue which holds all thP future events. The event-queue is an instance of the abstract data structure~ priority queue. \Ve have developed a noYel parallel data structure called parallel heap for exclusive-read exclusive-write parallel randon1-access 1nachines (ER.EvV PRA11). The parallel heap is the first such data structure to provide an optimal in1plen1entation of the priority quPues. Using p processors, it a.llows deletion of O(p) highest priority items and insertion of O(p) ne,v items, each in O(log n) time, where n is size of the parallel heap. The number of processors can be optimally varied from l through n. Employing th~ parallel heap as the underlying data structure~ we have developed four efficient ERE\\' PR.AN! algorithms for discrete-event simulation. Our three algorithms can sitnula.te O(p) events in O(log n) time using p processors, 1 < p < n, where n is the number of events scheduled in a parallf'l heap. All of our algorithms ensure balanced computational load among the procPssors. Thus .. they are superior to the existing parallel simulation algorith1ns which do not have the advantage of a parallel heap. The parallel h('a.p data structure seems ·applicable in a variety of other application areas also including branch-and-bound algorithms .. nutltiprocessor scheduling, and shortest-pa.th a.lgorithn1s. To explore the experimental aspects of simulation. a parallel time-driven battlefield simulation program has been i1nplemented on an Intel's iPSC-1 simulator. This program is being used to study dynamic sharing of a processor's computational load among its immediate neighbors.

Notes

This item is only available in print in the UCF Libraries. If this is your thesis or dissertation, you can help us make it available online for use by researchers around the world by STARS for more information.

Graduation Date

1990

Semester

Summer

Advisor

Deo, Narsingh

Degree

Doctor of Philosophy (Ph.D.)

College

College of Arts and Sciences

Department

Computer Science

Format

PDF

Pages

124 p.

Language

English

Length of Campus-only Access

None

Access Status

Doctoral Dissertation (Open Access)

Identifier

DP0027729

Subjects

Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences

Accessibility Status

Searchable text

This document is currently not available here.

Share

COinS