Authors: Olga Pearce, Todd Gamblin, Bronis R. de Supinski, Martin Schulz, Nancy M. Amato

Venue: International Conference on Supercomputing (ICS)
DOI: 10.1145/2304576.2304601
Link to Publication

Abstract:
Load balance is critical for performance in large parallel applications. An imbalance on today's fastest supercomputers can force hundreds of thousands of cores to idle, and on future exascale machines this cost will increase by over a factor of a thousand. Improving load balance requires a detailed understanding of the amount of computational load per process and an application's simulated domain, but no existing metrics sufficiently account for both factors. Current load balance mechanisms are often integrated into applications and make implicit assumptions about the load. Some strategies place the burden of providing accurate load information, including the decision on when to balance, on the application. Existing application-independent mechanisms simply measure the application load without any knowledge of application elements, which limits them to identifying imbalance without correcting it. Our novel load model couples abstract application information with scalable measurements to derive accurate and actionable load metrics. Using these metrics, we develop a cost model for correcting load imbalance. Our model enables comparisons of the effectiveness of load balancing algorithms in any specific imbalance scenario. Our model correctly selects the algorithm that achieves the lowest runtime in up to 96% of the cases, and can achieve a 19% gain over selecting a single balancing algorithm for all cases. 

@inproceedings{Pearce-qteolb-2012, 
 author = {Olga Pearce and 
Todd Gamblin and 
Bronis R. de Supinski and 
Martin Schulz and 
Nancy M. Amato}, 
 bibsource = {dblp computer science bibliography, https://dblp.org}, 
 biburl = {https://dblp.org/rec/conf/ics/PearceGSSA12.bib}, 
 booktitle = {International Conference on Supercomputing, ICS'12, Venice, Italy, 
June 25-29, 2012}, 
 doi = {10.1145/2304576.2304601}, 
 editor = {Utpal Banerjee and 
Kyle A. Gallivan and 
Gianfranco Bilardi and 
Manolis Katevenis}, 
 pages = {185--194}, 
 publisher = {{ACM}}, 
 timestamp = {Tue, 06 Nov 2018 11:07:02 +0100}, 
 title = {Quantifying the effectiveness of load balance algorithms}, 
 url = {https://doi.org/10.1145/2304576.2304601}, 
 year = {2012} 
}