Hierarchical Load Balancing for Charm++ Applications on Large Supercomputers
Authors:
- Gengbin ZhengGZGengbin Zheng
- Esteban MenesesEMEsteban Meneses
- Abhinav BhateleABAbhinav Bhatele
- Laxmikant V. KaleLKLaxmikant V. Kale
- 1 September 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 436-444
Abstract
Large parallel machines with hundreds of thousands of processors are being built. Recent studies have shown that ensuring good load balance is critical for scaling certain classes of parallel applications on even thousands of processors. Centralized load balancing algorithms suffer from scalability problems, especially on machines with relatively small amount of memory. Fully distributed load balancing algorithms, on the other hand, tend to yield poor load balance on very large machines. In this paper, we present an automatic dynamic hierarchical load balancing method that overcomes the scalability challenges of centralized schemes and poor solutions of traditional distributed schemes. This is done by creating multiple levels of aggressive load balancing domains which form a tree. This hierarchical method is demonstrated within a measurement-based load balancing framework in Charm++. We present techniques to deal with scalability challenges of load balancing at very large scale. We show performance data of the hierarchical load balancing method on up to 16,384 cores of Ranger (at TACC) for a synthetic benchmark. We also demonstrate the successful deployment of the method in a scientific application, NAMD with results on the Blue Gene/P machine at ANL.Keywords
This publication has 19 references indexed in Scilit:
- Scalable work stealing2009
- Dynamic topology aware load balancing algorithms for molecular dynamics applications2009
- Massively parallel cosmological simulations with ChaNGa2008 IEEE International Symposium on Parallel and Distributed Processing, 2008
- Overcoming scaling challenges in biomolecular simulations across multiple platforms2008 IEEE International Symposium on Parallel and Distributed Processing, 2008
- New challenges in dynamic load balancingApplied Numerical Mathematics, 2005
- A load balancing strategy for prioritized execution of tasks2002
- A semi distributed task allocation strategy for large hypercube supercomputers2002
- The implementation of the Cilk-5 multithreaded language1998
- A TLAS1996
- Strategies for dynamic load balancing on highly parallel computersIEEE Transactions on Parallel and Distributed Systems, 1993