Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations

2003/02/03 by G. Korniss, M. A. Novotny, H. Guclu +2
Physics and Astronomy · Computer Science · #cond-mat.stat-mech #cond-mat.dis-nn #cs.DC #physics.comp-ph

paper · pdf · doi:10.1126/science.1079382

published as Science 299, 677 (2003)

arxiv created 2003/02/03 · arxiv updated 2009/11/30

Abstract

In a parallel discrete-event simulation (PDES) scheme, tasks are distributed among processing elements (PEs), whose progress is controlled by a synchronization scheme. For lattice systems with short-range interactions, the progress of the conservative PDES scheme is governed by the Kardar-Parisi-Zhang equation from the theory of non-equilibrium surface growth. Although the simulated (virtual) times of the PEs progress at a nonzero rate, their standard deviation (spread) diverges with the number of PEs, hindering efficient data collection. We show that weak random interactions among the PEs can make this spread nondivergent. The PEs then progress at a nonzero, near-uniform rate without requiring global synchronizations.

Related

• Going through Rough Times: from Non-Equilibrium Surface Growth to Algorithmic Scalability
• From Massively Parallel Algorithms and Fluctuating Time Horizons to Nonequilibrium Surface Growth
• Non-equilibrium Surface Growth and Scalability of Parallel Algorithms for Large Asynchronous Systems
• Algorithmic scalability in globally constrained conservative parallel discrete event simulations of asynchronous systems
• Synchronization in Small-World-Connected Computer Networks