Periodic hierarchical load balancing for large supercomputers

Gengbin Zheng, Abhinav Bhatelé, Esteban Meneses, Laxmikant V. Kalé

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)371-385
Number of pages15
JournalInternational Journal of High Performance Computing Applications
Issue number4
StatePublished - Nov 2011


  • hierarchical algorithms
  • load balancing
  • parallel applications
  • performance study
  • scalability

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture


Dive into the research topics of 'Periodic hierarchical load balancing for large supercomputers'. Together they form a unique fingerprint.

Cite this