Statistical properties of the simulated time horizon in conservative parallel discrete-event simulations

ABSTRACT

We investigate the universal characteristics of the simulated time horizon of the basic conservative parallel algorithm when implemented on regular lattices. This technique [1, 2] is generically applicable to various physical, biological, or chemical systems where the underlying dynamics is asynchronous. Employing direct simulations, and using standard tools and the concept of dynamic scaling from non-equilibrium surface/interface physics, we identify the universality class of the time horizon and determine its implications for the asymptotic scalability of the basic conservative scheme. Our main finding is that while the simulation converges to an asymptotic nonzero rate of progress, the statistical width of the time horizon diverges with the number of PEs in a power law fashion. This is in contrast with the findings of Ref. [3]. This information can be very useful, e.g., we utilize it to understand optimizing the size of a moving "time window" to enforce memory constraints.

REFERENCES

• 1: B. D. Lubachevsky. Efficient Parallel Simulations of Asynchronous Cellular Arrays. Complex Systems 1, 1099-1123 (1987).
• 2: Boris D. Lubachevsky, Efficient parallel simulations of dynamic Ising spin systems, Journal of Computational Physics, v.75 n.1, p.103-122, March 1988 [doi>10.1016/0021-9991(88)90101-5]
• 3: Albert G. Greenberg , S. Shenker , Alexander L. Stolyar, Asynchronous updates in large parallel systems, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.91-103, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 4: Richard M. Fujimoto, Parallel discrete event simulation, Communications of the ACM, v.33 n.10, p.30-53, Oct. 1990 [doi>10.1145/84537.84545]
• 5: D. M. Nicol and R. M. Fujimoto. Parallel Simulation Today. Annals of Operations Research53 249-285 (1994).
• 6: K. Binder and D. W. Heermann. Monte Carlo Simulation in Statistical Physics. an Introduction, 3rd ed. (Springer, Berlin, 1997).
• 7: K. M. Chandy and J. Misra. Distributed Simulation: a Case Study in Design and Verification of Distributed Programs. IEEE Trans. on Softw. Eng.SE-5, 440-452 (1979).
• 8: K. M. Chandy , J. Misra, Asynchronous distributed simulation via a sequence of parallel computations, Communications of the ACM, v.24 n.4, p.198-206, April 1981 [doi>10.1145/358598.358613]
• 9: R. J. Glauber. Time-Dependent Statistics of the Ising Model. J. Math. Phys.4, 294 (1963).
• 10: G. Korniss , M. A. Novotny , P. A. Rikvold, Parallelization of a dynamic Monte Carlo algorithm: a partially rejection-free conservative approach, Journal of Computational Physics, v.153 n.2, p.488-508, Aug. 10,1999 [doi>10.1006/jcph.1999.6291]
• 11: G. Korniss, C. J. White, P. A. Rikvold, and M. A. Novotny. "Dynamic Phase Transition, Universality, and Finite-Size Scaling in the Two-Dimensional Kinetic Ising Model in an Oscillating. Phys. Rev. E63, 016120 (2001).
• 12: A.-L. Barabási and H. E. Stanley. Fractal Concepts in Surface Growth. (Cambridge University Press, Cambridge, 1995)
• 13: Timothy Halpin-Healy and Yi-Cheng Zhang. Kinetic roughening phenomena, stochastic growth, directed polymers and all that. Aspects of multidisciplinary statistical mechanics. Phys. Rep.254 215-414 (1995).
• 14: J. Krug. Origins of scale invariance in growth processes. Adv. Phys.46, 139-282 (1997).
• 15: B. J. Overeinder. Distributed Event-driven Simulation: Scheduling Stategies and Resource Management. Ph.D. thesis, Universiteit van Amsterdam, 2000.
• 16: B. J. Overeinder, A. Schoneveld, and P. M. A. Sloot. Self-organized Criticality in Optimistic Simulation of Correlated Systems. J. Parallel and Distributed Computing, submitted.
• 17: B. J. Overeinder , A. Schoneveld , P. M. A. Sloot, Spatio-temporal correlations and rollback distributions in optimistic simulations, Proceedings of the fifteenth workshop on Parallel and distributed simulation, p.145-152, May 15-18, 2001, Lake Arrowhead, California, United States
• 18: Robert E. Felderman , Leonard Kleinrock, Bounds and approximations for self-initiating distributed simulation without lookahead, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.4, p.386-406, Oct. 1991 [doi>10.1145/130611.130615]
• 19: David M. Nicol, Performance bounds on parallel self-initiating discrete-event simulations, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.1 n.1, p.24-50, Jan. 1991 [doi>10.1145/102810.102812]
• 20: Jeff S. Steinman, Breathing Time Warp, Proceedings of the seventh workshop on Parallel and distributed simulation, p.109-118, May 16-19, 1993, San Diego, California, United States
• 21: Jeff S. Steinman, Discrete-event simulation and the event horizon, Proceedings of the eighth workshop on Parallel and distributed simulation, p.39-49, July 06-08, 1994, Edinburgh, Scotland, United Kingdom
• 22: Jeffrey S. Steinman, Discrete-event simulation and the event horizon part 2: event list management, Proceedings of the tenth workshop on Parallel and distributed simulation, p.170-178, May 22-24, 1996, Philadelphia, Pennsylvania, United States
• 23: F. Family and T. Vicsek. Scaling of the active zone in the Eden process on percolation networks and the ballistic deposition model. J. Phys. A 18, L75-81 (1985)
• 24: G. Korniss, Z. Toroczkai, M. A. Novotny, and P. A. Rikvold. From Massively Parallel Algorithms and Fluctuating Time Horizons to Non-equilibrium Surface Growth. Phys. Rev. Lett.84, 1351-1354 (2000).
• 25: M. Kardar, G. Parisi, and Y.-C. Zhang. Dynamic Scaling of Growing Interfaces. Phys. Rev. Lett.56, 889-892 (1986).
• 26: G. Korniss, M. A. Novotny, Z. Toroczkai, and P. A. Rikvold. Nonequilibrium Surface Growth and Scalability of Parallel Algorithms for Large Asynchronous Systems. in Computer Simulation Studies in Condensed Matter Physics XIII, Springer Proceedings in Physics, Vol. 86, editors D. P. Landau, S. P. Lewis, and H.-B. Schüttler (Springer-Verlag, Berlin, Heidelberg, 2001), p. 183-188.
• 27: Z. Toroczkai, G. Korniss, S. Das Sarma, and R. K. P. Zia. Extremal Point Densities of Interface Fluctuations. Phys. Rev. E62, 276 (2000).
• 28: J. Krug and P. Meakin. Universal Finite-Size Effects in the Rate of Growth Processes. J. Phys. A23, L987 (1990).
• 29: S. Raychaudhuri, M. Cranston, C. Przybyla, and Y. Shapir. Maximal Height Scaling of Kinetically Growing Surfaces. Phys. Rev. Lett.87, 136101 (2001).

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Discrete event

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Parallel

General Terms:
Algorithms, Experimentation, Theory

Keywords:
Monte Carlo, conservative parallel discrete-event simulation, non-equilibrium surface growth, scalability, stochastic processes