Experiments in automated load balancing

ABSTRACT

One of the promises of parallelized discrete-event simulation is that it might provide significant speedups over sequential simulation. In reality, high performance cannot be achieved unless the system is fine-tuned to balance computation, communication, and synchronization requirements. In this paper, we discuss our experiments in automated load balancing using the SPEEDES simulation framework. Specifically, we examine three mapping algorithms that use run-time measurements. Using simulation models of queuing networks and the National Airspace System, we investigate (i) the use of run-time data to guide mapping, (ii) the utility of considering communication costs in a mapping algorithm, (iii) the degree to which computational ``hot-spots'' ought to be broken up in the linearization, and (iv) the relative execution costs of the different algorithms. We compare the performance of the three algorithms using results from the Intel Paragon.

REFERENCES

• 1: Jack Vedder Briner, Jr. , Gershon Kedem , John L. Ellis, Parallel mixed-level simulation of digital circuits using virtual time, 1990
• 2: R. L. Graham, "Bounds on Multiprocessing Timing Anomalies", SIAM Journal of Apphed Mathematics, Vol. 17, No. 2, pp. 416-419, March 1969.
• 3: B. Nandy and W. Loucks, "An Algorithm for Partitioning and Mapping Conservative Parallel Simulation onto Multicomputers", Proceedings of the 6th Workshop on Parallel and Distributed Simulation (PADS '92), pp. 139-146, January 1992.
• 4: David M. Nicol, The automated partitioning of simulations for parallel execution (computation), 1985
• 5: 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
• 6: 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]
• 7: Peter L. Reiher , David Jefferson, Dynamic load management in the time warp operating system, Transactions of the Society for Computer Simulation International, v.7 n.2, p.91-120, Jun. 1990
• 8: Rolf Schlagenhaft , Martin Ruhwandl , Christian Sporrer , Herbert Bauer, Dynamic load balancing of a multi-cluster simulator on a network of workstations, Proceedings of the ninth workshop on Parallel and distributed simulation, p.175-180, June 13-16, 1995, Lake Placid, New York, United States
• 9: 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
• 10: J. Steinman, "SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation", International Journal in Computer Szmulation, 2(3): 251-286, 1992.
• 11: Jeffrey S. Steinman , Craig A. Lee , Linda F. Wilson , David M. Nicol, Global Virtual Time and distributed synchronization, Proceedings of the ninth workshop on Parallel and distributed simulation, p.139-148, June 13-16, 1995, Lake Placid, New York, United States
• 12: 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
• 13: Linda F. Wilson , David M. Nicol, Automated load balancing in SPEEDES, Proceedings of the 27th conference on Winter simulation, p.590-596, December 03-06, 1995, Arlington, Virginia, United States [doi>10.1145/224401.224691]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Measurement, Performance, Theory

Keywords:
discrete-event simulation, parallel computing, load balancing, performance analysis