Synchronous relaxation for parallel Ising spin simulations

ABSTRACT

A new parallel algorithm for simulating Ising spin systems is presented. The sequential prototype is the n-fold way algorithm [2], which is efficient but is hard to parallelize using conservative methods. Our parallel algorithm is optimistic. Unlike other optimistic algorithms, e.g., Time Warp, our algorithm is synchronous. It also belongs to the class of simulations known as “relaxation” [3]; hence it is named “synchronous relaxation.” We derive performance guarantees for this algorithm. If N is the number of PEs, then under weak assumptions we show that the number of correct events processed per unit of time is, on average, at least of order N/ log N. All communication delays, processing time, and busy waits are taken into account.

REFERENCES

• 1: S. Borst, S. Grandhi, Kahn, K. Kumaran, B.D. Lubachevsky, D. Sand Wireless Simulation and Self-Organizing Spectrum Management. Bell Labs Tech. J., V.2, No.3, 1997, pp.81-98. http://www.lucent, com/minds/techjournal /summer_97/pd}/paperO6.pd}
• 2: A.B. Bortz, M.H. Kalos, J.L. Lebowitz, "A New Algorithm for Monte Carlo Simulation of Ising Spin Systems," J. Comput. Phys. 17, No. 1, pp. 10-18, 1975.
• 3: K.M Chandy and R. Sherman, "Space-Time and Simulation," Proc. SCS Multiconference on Distributed Simulation, March 1989, Tampa, Florida, (SCS Simulation Series, v.21, No.2), pp.53-57.
• 4: Stephen G. Eick , Albert G. Greenberg , Boris D. Lubachevsky , Alan Weiss, Synchronous relaxation for parallel simulations with applications to circuit-switched networks, ACM Transactions on Modeling and Computer Simulation (TOMACS), v.3 n.4, p.287-314, Oct. 1993 [doi>10.1145/159737.159744]
• 5: R.J. Glauber, "Time-Dependent Statistics of the Ising Model," J. Math. Physics 4, 2, pp. 294-307, 1963.
• 6: P. Heidelberger , D. M. Nicol, Conservative Parallel Simulation of Continuous Time Markov Chains Using Uniformization, IEEE Transactions on Parallel and Distributed Systems, v.4 n.8, p.906-921, August 1993 [doi>10.1109/71.238625 ]
• 7: F. Ising, "Beitag zur theorie des ferromagnetismus," Z. Physik, 31, pp. 253-258, 1925.
• 8: David R. Jefferson, Virtual time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.3, p.404-425, July 1985 [doi>10.1145/3916.3988]
• 9: G. Korniss, G. Brown, M.A. Novotny, and P.A.Rikvold, Hard simulation problems in the modeling of magnetic materials: Parallelization and Langevin micromagnetics," in Computer Simulation Studies in Condensed Matter Physics XI, D..P. Landau and H.-B. Schuttler eds. (Springer-Verlag, New York, 1998) http : //xxx. lanl. gov/abs /cond- mat/9803118
• 10: P.B. Linhart, B.D. Lubachevsky, R. Radner, and M.J. Meurer, "'Friends and Family' and Related Pricing Strategies," Proc. 2nd Russian-Swedish Control Conference, Aug. 1995, St.Petersburg State Technical University, Russia, p. 192-196.
• 11: B.D. Lubachevsky, "Efficient Parallel Simulations of Asynchronous Cellular Arrays," Complex Systems 1 (1987), pp. 1099-1123.
• 12: 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]
• 13: B. Lubachevsky and A. Weiss, "Efficiency study of a new parallel Ising spin simulation algorithm," In preparation.
• 14: N.C. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller, "Equation of State Calculations by Fast Computing Machines," J. Chemical Physics 21, No. 6, 1953.
• 15: David M. Nicol , Philip Heidelberger, Optimistic parallel simulation of continuous time Markov chains using uniformization, Journal of Parallel and Distributed Computing, v.18 n.4, p.395-410, Aug. 1993 [doi>10.1006/jpdc.1993.1073 ]
• 16: P. Nielaba, V. Privman, and J.-S. Wang, "Irreversible Multilayer Adsorption," in Computer Simulation Studies in Condensed-Matter Physics V-- (D.P. Landau, K..K Mon, and H- B. Schiittler, Eds.), Proceedings in Physics, Vol 76 (Springer-Verlag, Berlin, 1993), p.143.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Metropolis algorithm, computational physics, conservative simulation, optimistic simulation