An efficient and scalable parallel algorithm for discrete-event simulation

Author

Prasad, Sushil ; Deo, Narsingh

Author_Institution

Dept. of Math. & Comput. Sci., Georgia State Univ., Atlanta, GA, USA

fYear

1991

fDate

8-11 Dec 1991

Firstpage

652

Lastpage

658

Abstract

The authors describe a novel parallel algorithm for discrete-event simulation on an exclusive-read exclusive-write parallel random-access machine (EREW PRAM). This algorithm is based on a recently developed parallel data structure, namely the parallel heap, which, when used as a parallel event-queue, allows deletion of O(p) earliest messages and insertion of O(p) new messages each in O(log n) time, using p processors, where n is the number of messages scheduled. The proposed algorithm can simulate up to p independent messages in O(log n) time, thus achieving O(p ) speedup. The number of processors, p, can be optimally varied in the range 1⩽p⩽n

Keywords

data structures; discrete event simulation; parallel algorithms; random-access storage; EREW PRAM; deletion; discrete-event simulation; exclusive-read exclusive-write parallel random-access machine; insertion; parallel data structure; parallel event-queue; scalable parallel algorithm; Computational modeling; Computer science; Computer simulation; Concurrent computing; Data structures; Discrete event simulation; Parallel algorithms; Parallel processing; Partitioning algorithms; Phase change random access memory;

fLanguage

English

Publisher

ieee

Conference_Titel

Simulation Conference, 1991. Proceedings., Winter

Conference_Location

Phoenix, AZ

Print_ISBN

0-7803-0181-1

Type

conf

DOI

10.1109/WSC.1991.185670

Filename

185670