Efficient distributed event-driven simulations of multiple-loop networks

ABSTRACT

Simulating asynchronous multiple-loop networks is commonly considered a difficult task for parallel programming. Two examples of asynchronous multiple-loop networks are presented in this article: a stylized queuing system and an Ising model. In both cases, the network is an n × n grid on a torus and includes at least an order of n2 feedback loops. A new distributed simulation algorithm is demonstrated on these two examples. The algorithm combines three elements: (1) the bounded lag restriction; (2) minimum propagation delays; and (3) the so-called opaque periods. We prove that if N processing elements (PEs) execute the algorithm in parallel and the simulated system exhibits sufficient density of events, then, on average, processing one event would require O(log N) instructions of one PE. Experiments on a shared memory MIMD bus computer (Sequent's Balance) and on a SIMD computer (Connection Machine) show speed-ups greater than 16 on 25 PEs of a Balance and greater than1900 on 214 PEs of a Connection Machine.

REFERENCES

• 1: Binder, K. (ed.). Monte Carlo methods is statistical physics, Springer- Verlag, New York, N.Y., 1986.
• 2: Bortz, A.B., Kalos, M.H., and Lebowitz, J.L. A new algorithm for Monte-Carlo simulation of Ising spin systems, J. Comp. Physics, 17, 1 (Jan. 1975), 10-18.
• 3: Chandy, K.M., and Misra, J. Distributed simulation: A case study in design and verification of distributed programs, IEEE Trans. Software Eng., SE-5, 5 Sept. 1979. 440-452.
• 4: 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]
• 5: Friedberg, R., and Cameron, J.E. Test of the Monte Carlo method: Fast Simulation of a Small Ising Lattice, J. Chem. Physics 52, 12 (1970), 6049-6058.
• 6: Fujimoto, R.M. Performance measurements of distributed simulation strategies. In Proceedings of the 1988 SCS Multiconference (San Diego, Feb. 3-5, 1988). Simulation Series, SCS 19, 3, 14-20.
• 7: Gafni, A., Berry, O., and Jefferson, D. Optimized virtual synchronization. In Proceedings of the 2d International Workshop on Applied Mathematics and Performance/Reliability Models (Rome, Italy, May 25-29, 1987). Univ. of Rome II (1987), 229-244.
• 8: Glauber, R.J. Time-dependent statistics of the Ising model. J. Math. Physics 4, 2 (1963), 294-307.
• 9: Bojan Grošelj , Carl Tropper, Pseudosimulation: an algorithm for distributed similation with limited memory, International Journal of Parallel Programming, v.15 n.5, p.413-456, Oct. 1986 [doi>10.1007/BF01414465]
• 10: Victor Paul Holmes, Parallel algorithms for multiple processor architectures., 1978
• 11: 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]
• 12: Douglas W. Jones, Concurrent simulation: an alternative to distributed simulation, Proceedings of the 18th conference on Winter simulation, p.417-423, December 08-10, 1986, Washington, D.C., United States [doi>10.1145/318242.318468]
• 13: Lubachevsky, B.D. Efficient parallel simulations of asynchronous cellular arrays. Complex Systems 1, 6 (Dec. 1987), 1099-1123.
• 14: 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]
• 15: Lubachevsky, B.D. Bounded lag distributed discrete event simulalion, Bell Laboratories Tech. Rep., 1986, submitted for publication, (shortened version). In Proceedings of the 1988 SCS Multiconference. Simulation Series, SCS, 19, 3, 183-191.
• 16: Metropolis, N., et al. Equation of state calculations by fast computing machines, J. Chem. Physics, 21, 6 (June 1953), 1087-1092.
• 17: Jayadev Misra, Distributed discrete-event simulation, ACM Computing Surveys (CSUR), v.18 n.1, p.39-65, March 1986 [doi>10.1145/6462.6485]
• 18: Nicol, D.M. Synchronizing network performance. M.S. dissertation, School of Eng. and Appl. Science, Univ. of Virginia, (1984).
• 19: David M. Nicol, Parallel discrete-event simulation of FCFS stochastic queueing networks, Proceedings of the ACM/SIGPLAN conference on Parallel programming: experience with applications, languages and systems, p.124-137, July 19-21, 1988, New Haven, Connecticut, United States
• 20: David M. Nicol , Paul F. Reynolds, Jr., Problem oriented protocol design, Proceedings of the 16th conference on Winter simulation, p.470-474, December 28-30, 1984, Dallas, TX
• 21: David M. Nicol , Paul F. Reynolds, Jr., An optimal repartitioning decision policy, Proceedings of the 17th conference on Winter simulation, p.493-497, December 11-13, 1985, San Francisco, California, United States [doi>10.1145/21850.253429]
• 22: Peacock, J.K., Wong, J.W., and Manning, E.G. Distributed simulation using a network of processors, In Proceedings of the 3d Berkeley Workshop on Distributed Data Managements and Comp. Networks (1978) and Computer Networks 3, 1 (1979}.
• 23: Daniel A. Reed , Allen D. Malony , Bradley McCredie, Parallel Discrete Event Simulation Using Shared Memory, IEEE Transactions on Software Engineering, v.14 n.4, p.541-553, April 1988 [doi>10.1109/32.4677]
• 24: Sokol, L.M., Briscoe, D.P., and Wieland, A.P. MTW: a strategy for scheduling discrete simulation events for concurrent execution. In Proceedings of the 1988 SCS Multiconference (San Diego, Calif., Feb. 3-8, 1989). Simulation Series, SCS, 19, 3, 34-42.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Design, Performance, Theory