Automated Load Balancing of a Missile Defense Simulation Using Domain Knowledge

Abstract

For discrete-event simulations with a large number of objects, parallelization provides an opportunity for improved performance. However, if simulation objects are not placed carefully, the additional communication costs can outweigh the performance gain from adding CPUs. For many simulations, the large number of objects makes manual placement of objects impractical. We present two new algorithms for static load balancing that, using a small amount of domain knowledge and run-time measurements, automatically discover objects of different classes that communicate frequently and place these objects on the same processor. We compare results obtained from a missile defense simulation implemented in SPEEDES using our algorithms to those obtained with previously published load-balancing algorithms.

Keywords

Static load balancing missile defense SPEEDES domain knowledge genetic algorithms

Get full access to this article

View all access options for this article.

References

1. Stone, H.S. 1977. Multiprocessor Scheduling with the Aid of Network Flow Algorithms. January 1977 IEEE Transactions on Software Engineering, Vol. SE-3, No. 1, 85–93.

2. Sanders, P. On the Competitive Analysis of Randomized Static Load Balancing. Available at http://citeseer.nj.nec.com/79406.html

3. Steinman, J. 1992. SPEEDES: A Multiple-Synchronization Environment for Parallel Discrete-Event Simulation. In International Journal in Computer Simulation, Vol. 2, No. 3, 251–286.

4. Wilson, L.F., D.M. Nicol. 1995. Experiments in Automated Load Balancing. In NASA CR-198241, ICASE Report #95–80.

5. Ballistic Missile Defense Organization. Theater Missile Defense Systems. Available at http://www.acq.osd.mil/bmdo/bmdolink/html/tmd.html.

6. Sedgewick, R. 1988. Algorithms, Second Edition. Reading, MA: Addison-Wesley.

7. Baase, S. , A. Van Gelder. 2000. Computer Algorithms: Introduction to Design and Analysis, Third Edition. Reading, MA: Addison-Wesley.

8. Ballistic Missile Defense Organization. National Missile Defense. Available at http://www.acq.osd.mil/bmdo/bmdolink/html/nmd.html.

9. Som, T. , R. Sargent.

2000

Model structure and load balancing in optimistic parallel discrete event simulation. In Proceedings of the 2000 Workshop on Parallel and Distributed Simulation (PADS), IEEE, 147–154.

10.

10. Gan, B. P. , Y.H. Low , S.J. Turner , W. Cai , W.J. Hsu , S.Y. Huang. 2000. Load Balancing for Conservative Simulation on Shared Memory Multiprocessor Systems. Proceedings of the 2000 Workshop on Parallel and Distributed Simulation (PADS), IEEE, 139–146.

11.

11. Bäck, T. , H.P. Schwefel. 1993. An Overview of Evolutionary Algorithms for Parameter Optimization. Evolutionary Computation, Vol. 1, No. 1, 1–23.

12.

12. Merkle, L.D. , G.B. Lamont. 1997. A Random Function Based Framework for Evolutionary Algorithms. In Proceedings of the Seventh International Conference on Genetic Algorithms, Thomas Bäck (ed.), 105–112.

13.

13. Langdon, W. B. , et al., editors. 2000. Proceedings of the Genetic and Evolutionary Computation Conference. San Franciso, CA: Morgan Kauffman Publishers.

14.

14. Pellegrini, F. , J. Roman. 1996. SCOTCH: A Software Package for Static Mapping by Dual Recursive Bipartitioning of Process and Architecture Graphs. In Proceedings of HPCN ′96. Brussels, Belgium: LNCS 1067, Springer, 493–498.

15.

15. Vee, V.Y. , W.J. Hus. 2000. Locality-preserving load-balancing mechanisms for synchronous simulations on shared-memory multiprocessors. Proceedings of the 2000 Workshop on Parallel and Distributed Simulation (PADS), IEEE, 131–138.

16.

16. Karypis, G. , V. Kumar. 1995. Multilevel Graph Partition and Sparse Matrix Ordering. International Conference on Parallel Processing.

17.

17. Boukerche, A. C. Tropper. 1994. A Static Partitioning and Mapping Algorithm for Conservative Parallel Simulations. In Proceedings of the 8th Workshop on Parallel and Distributed Simulation (PADS), IEEE, 164–172.

18.

18. Nutaro, J. 2003. Parallel Discrete Event Simulation with Application to Continuous Systems. Ph.D. Dissertation, University of Arizona.