University of Illinois Urbana-Champaign

Applying Graph Partitioning Methods in Measurement-based Dynamic Load Balancing

Menon, Harshitha; Bhatele, Abhinav; Fourestier, Sebastien; Kale, Laxmikant; Pellegrini, Francois

Permalink

https://hdl.handle.net/2142/75950

Description

Title
Applying Graph Partitioning Methods in Measurement-based Dynamic Load Balancing
Author(s)
  • Menon, Harshitha
  • Bhatele, Abhinav
  • Fourestier, Sebastien
  • Kale, Laxmikant
  • Pellegrini, Francois
Issue Date
2015
Keyword(s)
  • HPC
  • load balancing
  • performance
  • graph partitioning
Abstract
Load imbalance in an application can lead to degradation of performance and a significant drop in system utilization. Achieving the best parallel efficiency for a program requires optimal load balancing which is an NP-hard problem. This paper explores the use of graph partitioning algorithms, traditionally used for partitioning physical domains/meshes, for measurement-based dynamic load balancing of parallel applica- tions. In particular, we present repartitioning methods that consider the previous mapping to minimize dynamic migration costs. We also discuss the use of a greedy algorithm in conjunction with iterative graph partitioning algorithms to reduce the load imbalance for graphs with heavily skewed load distributions. These algorithms are implemented in a graph partitioning toolbox called SCOTCH and we use CHARM++, a migratable objects based programming model, to experiment with various load balancing scenarios. To compare with different load balancing strategies based on graph partitioners, we have implemented METIS and ZOLTAN-based load balancers in CHARM++. We demonstrate the effectiveness of the new algorithms de- veloped in SCOTCH in the context of the NAS BT solver and two micro-benchmarks. We show that SCOTCH based strategies lead to better performance compared to other existing partitioners, both in terms of the application execution time and fewer number of objects migrated.
Type of Resource
  • text
  • image
Language
en
Permalink
http://hdl.handle.net/2142/75950

Owning Collections

Research and Tech Reports - Computer Science PRIMARY