Files in this item



application/pdfpaper.pdf (1MB)
(no description provided)PDF


Title:Applying Graph Partitioning Methods in Measurement-based Dynamic Load Balancing
Author(s):Menon, Harshitha; Bhatele, Abhinav; Fourestier, Sebastien; Kale, Laxmikant; Pellegrini, Francois
load balancing
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.
Issue Date:2015
Genre:Technical Report
Date Available in IDEALS:2015-05-05

This item appears in the following Collection(s)

Item Statistics