A distributed dynamic load balancer for iterative applications

Harshitha Menon, Laxmikant V Kale

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

Abstract

For many applications, computation load varies over time. Such applications require dynamic load balancing to improve performance. Centralized load balancing schemes, which perform the load balancing decisions at a central location, are not scalable. In contrast, fully distributed strategies are scalable but typically do not produce a balanced work dis-tribution as they tend to consider only local information. This paper describes a fully distributed algorithm for load balancing that uses partial information about the global state of the system to perform load balancing. This algo-rithm, referred to as GrapevineLB, consists of two stages: global information propagation using a lightweight algo-rithm inspired by epidemic [21] algorithms, and work unit transfer using a randomized algorithm. We provide analysis of the algorithm along with detailed simulation and perfor-mance comparison with other load balancing strategies. We demonstrate the effectiveness of GrapevineLB for adaptive mesh refinement and molecular dynamics on up to 131,072 cores of BlueGene/Q.

Original languageEnglish (US)
Title of host publicationProceedings of SC 2013
Subtitle of host publicationThe International Conference for High Performance Computing, Networking, Storage and Analysis
PublisherIEEE Computer Society
ISBN (Print)9781450323789
DOIs
StatePublished - Jan 1 2013
Event2013 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2013 - Denver, CO, United States
Duration: Nov 17 2013Nov 22 2013

Publication series

NameInternational Conference for High Performance Computing, Networking, Storage and Analysis, SC
ISSN (Print)2167-4329
ISSN (Electronic)2167-4337

Other

Other2013 International Conference for High Performance Computing, Networking, Storage and Analysis, SC 2013
CountryUnited States
CityDenver, CO
Period11/17/1311/22/13

Keywords

  • Distributed load balancer
  • Epidemic algorithm
  • Load balancing

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Computer Science Applications
  • Hardware and Architecture
  • Software

Fingerprint Dive into the research topics of 'A distributed dynamic load balancer for iterative applications'. Together they form a unique fingerprint.

  • Cite this

    Menon, H., & Kale, L. V. (2013). A distributed dynamic load balancer for iterative applications. In Proceedings of SC 2013: The International Conference for High Performance Computing, Networking, Storage and Analysis [15] (International Conference for High Performance Computing, Networking, Storage and Analysis, SC). IEEE Computer Society. https://doi.org/10.1145/2503210.2503284