Applying Graph Partitioning Methods in Measurement-based Dynamic Load Balancing
| Harshitha Menon | Abhinav Bhatele | Sébastien Fourestier | Laxmikant Kale | François Pellegrini
Illinois Research and Technical Reports - Computer Science (CS Res. & Tech. Report) 2014
Publication Type: Paper
Repository URL: papers/201107_ScotchCharm
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 par- titioning physical domains/meshes, for measurement-based dynamic load balancing of parallel applications. In particular, we present repartitioning methods that consider the previous mapping to minimize dynamic migration costs. We also discuss a new imbalance reduction algorithm 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 developed 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.
TextRef
People
Research Areas