Efficient parallel algorithms and data structures for discrete-event simulation
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.
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 downloading and filling out the Internet Distribution Consent Agreement. You may also contact the project coordinator Kerri Bottorff for more information.
Doctor of Philosophy (Ph.D.)
College of Arts and Sciences
Length of Campus-only Access
Doctoral Dissertation (Open Access)
Arts and Sciences -- Dissertations, Academic; Dissertations, Academic -- Arts and Sciences
Prasad, Sushil Kumar, "Efficient parallel algorithms and data structures for discrete-event simulation" (1990). Retrospective Theses and Dissertations. 4064.