Large parallel machines with hundreds of thousands of processors are becoming more prevalent. 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 a relatively small amount of memory. Fully distributed load balancing algorithms, on the other hand, tend to take longer to arrive at good solutions. In this paper, we present an automatic dynamic hierarchical load balancing method that overcomes the scalability challenges of centralized schemes and longer running times of traditional distributed schemes. Our solution overcomes these issues by creating multiple levels of load balancing domains which form a tree. This hierarchical method is demonstrated within a measurement-based load balancing framework in Charm++. We discuss techniques to deal with scalability challenges of load balancing at very large scale. We present performance data of the hierarchical load balancing method on up to 16,384 cores of Ranger (at the Texas Advanced Computing Center) and 65,536 cores of Intrepid (the Blue Gene/P at Argonne National Laboratory) for a synthetic benchmark. We also demonstrate the successful deployment of the method in a scientific application, NAMD, with results on Intrepid.
AhmadIGhafoorA (1990) A semi distributed task allocation strategy for large hypercube supercomputers. In: Proceedings of the 1990 conference on Supercomputing. New York: IEEE Computer Society Press, 898–907.
2.
BaldeschwielerJEBlumofeRDBrewerEA (1996) Atlas: an infrastructure for global computing. In: EW 7: Proceedings of the 7th workshop on ACM SIGOPS European workshop. New York: ACM, 165–72.
3.
BhateléABohmEKaléLV (2010) Optimizing communication for Charm++ applications by reducing network contention. Concurrency and Computation: Practice and Experience.
4.
BhateléAKaléLVKumarS (2009) Dynamic topology aware load balancing algorithms for molecular dynamics applications. In: 23rd ACM International Conference on Supercomputing, 110–6.
5.
BhateléAKumarSMeiCPhillipsJCZhengGKaléLV (2008) Overcoming scaling challenges in biomolecular simulations across multiple platforms. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium 2008, 1–12.
6.
CatalyurekUBomanEDevineKBozdagDHeaphyRRiesenL (2007) Hypergraph-based dynamic load balancing for adaptive scientific computations. In: Proc. of 21st International Parallel and Distributed Processing Symposium (IPDPS'07). IEEE. Best Algorithms Paper Award, 1–11.
7.
CatlettC. (2007) TeraGrid: Analysis of Organization, System Architecture, and Middleware Enabling New Types of Applications. In: GrandinettiL (ed.) HPC and Grids in Action. Amsterdam: IOS Press. 16: 225–49.
DevineKDBomanEGHeaphyRTHendricksonBATerescoJDFaikJ. (2005) New challenges in dynamic load balancing. Appl. Numer. Math.52(2–3): 133–52.
10.
DinanJLarkinsDBSadayappanPKrishnamoorthySieplochaJ (2009) Scalable work stealing. In: SC ‘09: Proceedings of the Conference on High Performance Computing Networking, Storage and Analysis. New York: ACM, 1–11.
11.
FrigoMLeisersonCERandallKH (1998) The Implementation of the Cilk-5 Multithreaded Language. In: ACM SIGPLAN ‘98 Conference on Programming Language Design and Implementation (PLDI), volume 33 of ACM Sigplan Notices. Montreal, 212–23.
12.
FuruichiMTakiKIchiyoshiN (1990) A multi-level load balancing scheme for or-parallel exhaustive search programs on the multi-psi. In: Second ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, 50–9.
13.
Ha'cAJinX (1987) Dynamic load balancing in distributed system using a decentralized algorithm. In: Proc. of 7-th Intl. Conf. on Distributed Computing Systems, 170–7.
14.
JetleyPGioachinFMendesCKaleLVQuinnTR (2008) Massively parallel cosmological simulations with ChaNGa. In: Proceedings of IEEE International Parallel and Distributed Processing Symposium2008, 1–12.
15.
KaléLKrishnanS (1993) CHARM++: A Portable Concurrent Object Oriented System Based on C++. In: PaepckeA (ed.) Proceedings of OOPSLA'93. ACM Press, 91–108.
16.
KaléLV (1988) Comparing the performance of two dynamic load distribution methods. In: Proceedings of the 1988 International Conference on Parallel Processing, St. Charles, IL. 8–11.
17.
KaléLVBhandarkarMBrunnerR (1998) Load balancing in parallel molecular dynamics. In: Fifth International Symposium on Solving Irregularly Structured Problems in Parallel, volume 1457 of Lecture Notes in Computer Science, 251–61.
LawlorOChakravortySWilmarthTChoudhuryNDooleyIZhengG. (2006) Parfum: A parallel framework for unstructured meshes for scalable dynamic physics applications. Engineering with Computers22(3–4): 215–35.
20.
LawlorOSKaléLV (2003) Supporting dynamic parallel object arrays. Concurrency and Computation: Practice and Experience15: 371–93.
21.
MangalaSWilmarthTChakravortySChoudhuryNKaleLVGeubellePH (2007) Parallel adaptive simulations of dynamic fracture events. Engineering with Computers24: 341–58.
22.
NieuwpoortRVVKielmannTBalHE (2000) Satin: Efficient parallel divide-and-conquer in java. In: Lecture Notes in Computer Science. Springer. 1900/2000: 690–9.
23.
PhillipsJCZhengGKumarSKaléLV (2002) NAMD: Biomolecular simulation on thousands of processors. In: Proceedings of the 2002 ACM/IEEE conference on Supercomputing, Baltimore, MD. 1–18.
24.
ShuWWKaléLV (1989) A dynamic load balancing strategy for the Chare Kernel system. In: Proceedings of Supercomputing ‘89, 389–98.
25.
SinhaAKaléL (1993) A load balancing strategy for prioritized execution of tasks. In: International Parallel Processing Symposium, New Port Beach, CA. 230–7.
26.
WeirsGDwarkadasVPlewaTTomkinsCMarr-LyonM (2005) Validating the Flash code: vortex-dominated flows. In: Astrophysics and Space Science, 298: 341–6.
27.
Willebeek-LeMairMHReevesAP (1993) Strategies for dynamic load balancing on highly parallel computers. In: IEEE Transactions on Parallel and Distributed Systems, 4: 979–93.
28.
ZhengG (2005) Achieving high performance on extremely large parallel machines: performance prediction and load balancing. PhD thesis, Department of Computer Science, University of Illinois at Urbana-Champaign.
