We are inviting IDEALS users, both people looking for materials in IDEALS and those who want to deposit their work, to give us feedback on improving this service through an interview. Participants will receive a $20 VISA gift card. Please sign up via https://forms.illinois.edu/sec/4069811

Files in this item

FilesDescriptionFormat

application/pdf

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

Description

Title:Applying Graph Partitioning Methods in Measurement-based Dynamic Load Balancing
Author(s):Menon, Harshitha; Bhatele, Abhinav; Fourestier, Sebastien; Kale, Laxmikant; Pellegrini, Francois
Subject(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.
Issue Date:2015
Genre:Technical Report
Type:Text
Image
Language:English
URI:http://hdl.handle.net/2142/75950
Date Available in IDEALS:2015-05-05


This item appears in the following Collection(s)

Item Statistics