Automated load balancing in SPEEDES

ABSTRACT

Parallel discrete event simulation offers the potential for significant speedup over sequential simulation. Unfortunately, high performance is often achieved only after rigorous fine tuning is used to obtain an efficient mapping of tasks to processors. In practice, good performance with minimal effort is often preferable to high performance with excessive effort. We discuss our research in adding automated load balancing to the SPEEDES simulation framework. Using simulation models of queuing networks and the National Airspace System, we demonstrate that using run time measurements, our automated load balancing scheme can achieve better performance than simple allocation methods that do not use run time measurements, particularly when large numbers of processors are used.

REFERENCES

• 1: 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
• 2: David Nicol , Philip Heidelberger, On extending parallelism to serial simulators, Proceedings of the ninth workshop on Parallel and distributed simulation, p.60-67, June 13-16, 1995, Lake Placid, New York, United States
• 3: David M. Nicol , Weizhen Mao, Automated parallelization of timed Petri-net simulations, Journal of Parallel and Distributed Computing, v.29 n.1, p.60-74, Aug. 15, 1995 [doi>10.1006/jpdc.1995.1106]
• 4: Steinman, J. 1991. SPEEDES: Synchronous Parallel Environment for Emulation and Discrete Event Simulation. Proceedings of the SCS Multiconference on Advances in Parallel and Distributed Simulation, SCS Simulation Series, Vol. 23, No. 1, pp. 95-103, January.
• 5: Steinman, J. 1992. SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation. International Journal in Computer Simulation, 2(3): 251-286.
• 6: 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
• 7: Frederick Wieland , Eric Blair , Tony Zukas, Parallel Discrete-Event Simulation (PDES): a case study in design, development, and performance using SPEEDES, Proceedings of the ninth workshop on Parallel and distributed simulation, p.103-110, June 13-16, 1995, Lake Placid, New York, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  G. Mathematics of Computing
  G.m MISCELLANEOUS
      Subjects: Queueing theory**

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.1 Simulation Theory
          Subjects: Model classification

General Terms:
Design, Performance