Work stealing and persistence-based load balancers for iterative overdecomposed applications

Jonathan Lifflander, Sriram Krishnamoorthy, Laxmikant V. Kale

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Applications often involve iterative execution of identical or slowly evolving calculations. Such applications require incremental rebalancing to improve load balance across iterations. In this paper, we consider the design and evaluation of two distinct approaches to addressing this challenge: persistence-based load balancing and work stealing. The work to be performed is overdecomposed into tasks, enabling automatic rebalancing by the middleware. We present a hierarchical persistence-based rebalancing algorithm that performs localized incremental rebalancing. We also present an active-message-based retentive work stealing algorithm optimized for iterative applications on distributed memory machines. We demonstrate low overheads and high efficiencies on the full NERSC Hopper (146,400 cores) and ALCF Intrepid systems (163,840 cores), and on up to 128,000 cores on OLCF Titan.

Original languageEnglish (US)
Title of host publicationHPDC '12 - Proceedings of the 21st ACM Symposium on High-Performance Parallel and Distributed Computing
Pages137-148
Number of pages12
DOIs
StatePublished - Jul 23 2012
Event21st ACM Symposium on High-Performance Parallel and Distributed Computing, HPDC '12 - Delft, Netherlands
Duration: Jun 18 2012Jun 22 2012

Publication series

NameHPDC '12 - Proceedings of the 21st ACM Symposium on High-Performance Parallel and Distributed Computing

Other

Other21st ACM Symposium on High-Performance Parallel and Distributed Computing, HPDC '12
CountryNetherlands
CityDelft
Period6/18/126/22/12

Keywords

  • Dynamic load balancing
  • Hierarchical load balancer
  • Iterative applications
  • Persistence
  • Task scheduling
  • Work stealing

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Work stealing and persistence-based load balancers for iterative overdecomposed applications'. Together they form a unique fingerprint.

Cite this