Title :
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
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;
Conference_Titel :
Simulation Conference, 1991. Proceedings., Winter
Conference_Location :
Phoenix, AZ
Print_ISBN :
0-7803-0181-1
DOI :
10.1109/WSC.1991.185670
