Update statistics in conservative parallel discrete event simulations of asynchronous systems

Abstract

We model the performance of an ideal closed chain of L processing elements that work in parallel in an asynchronous manner. Their state updates follow a generic conservative algorithm. The conservative update rule determines the growth of a virtual time surface. The physics of this growth is reflected in the utilization (the fraction of working processors) and in the interface width. We show that it is possible to nake an explicit connection between the utilization and the macroscopic structure of the virtual time interface. We exploit this connection to derive the theoretical probability distribution of updates in the system within an approximate model. It follows that the theoretical lower bound for the computational speed-up is s=(L+1)/4 for L>3. Our approach uses simple statistics to count distinct surface configuration classes consistent with the model growth rule. It enables one to compute analytically microscopic properties of an interface, which are unavailable by continuum methods.

15 pages, 12 figures

References in corpus (10)

• Dynamic Phase Transition, Universality, and Finite-size Scaling in the Two-dimensional Kinetic Ising Model in an Oscillating Field
• Suppressing Roughness of Virtual Times in Parallel Discrete-Event Simulations
• Absence of First-order Transition and Tri-critical Point in the Dynamic Phase Diagram of a Spatially Extended Bistable System in an Oscillating Field
• From Massively Parallel Algorithms and Fluctuating Time Horizons to Non-equilibrium Surface Growth
• Non-perturbative renormalization of the KPZ growth dynamics
• Parallelization of a Dynamic Monte Carlo Algorithm: a Partially Rejection-Free Conservative Approach
• Soft versus Hard Dynamics for Field-driven Solid-on-Solid Interfaces
• Microstructure and Velocity of Field-Driven SOS Interfaces: Analytic Approximations and Numerical Results
• Microstructure and velocity of field-driven Ising interfaces moving under a soft stochastic dynamic
• Algorithmic scalability in globally constrained conservative parallel discrete event simulations of asynchronous systems

Cited by in corpus (6)

• Synchronization Landscapes in Small-World-Connected Computer Networks
• Roughening of the (1+1) interfaces in two-component surface growth with an admixture of random deposition
• On the Evolution of Time Horizons in Parallel and Grid Simulations
• Discrete-Event Analytic Technique for Surface Growth Problems
• Desynchronization and Speedup in an Asynchronous Conservative Parallel Update Protocol
• Synchronization in Small-World-Connected Computer Networks