Title :
Almost linear speed-up of distributed discrete event simulations
Author :
Lubachevsky, Boris D.
Author_Institution :
Bell Labs., Murray Hill, NJ, USA
Abstract :
A distributed simulation algorithm is presented which explores the topology of the simulated system using precomputed minimum propagation delays between subsystems. The algorithm also uses opaque periods which are the delays caused by the nonpreemptive states these subsystems can enter. The algorithm achieves Θ(N/log N) speed-up when run on an appropriate physically realizable N-processor parallel computer. No other algorithm for distributed discrete event simulation has been theoretically shown to achieve this level of efficiency. Experiments show speed-ups of greater than 20 on 25 processors of a shared memory MIMD computer and greater than 1900 on 214 processors of a SIMD computer
Keywords :
digital simulation; parallel algorithms; N-processor parallel computer; SIMD computer; almost linear speedup; distributed discrete event simulations; nonpreemptive states; precomputed minimum propagation delays; shared memory MIMD computer; Algorithm design and analysis; Computational modeling; Concurrent computing; Discrete event simulation; History; Network servers; Physics computing; Propagation delay; System recovery; Topology;
Conference_Titel :
Frontiers of Massively Parallel Computation, 1988. Proceedings., 2nd Symposium on the Frontiers of
Conference_Location :
Fairfax, VA
Print_ISBN :
0-8186-5892-4
DOI :
10.1109/FMPC.1988.47471