Dynamic Load Balancing of Unbalanced Computations Using Message Passing

Citations Over TimeTop 18% of 2007 papers

Abstract

This paper examines MPI's ability to support continuous, dynamic load balancing for unbalanced parallel applications. We use an unbalanced tree search benchmark (UTS) to compare two approaches, 1) work sharing using a centralized work queue, and 2) work stealing using explicit polling to handle steal requests. Experiments indicate that in addition to a parameter defining the granularity of load balancing, message-passing paradigms require additional parameters such as polling intervals to manage runtime overhead. Using these additional parameters, we observed an improvement of up to 2times in parallel performance. Overall we found that while work sharing may achieve better peak performance on certain workloads, work stealing achieves comparable if not better performance across a wider range of chunk sizes and workloads.

Related Papers

• → A load balancing model for grid environment(2007)33 cited
• → A Clustered Approach for Load Balancing in Distributed Systems(2021)9 cited
• → A QoS Based Load Balancing Framework for Large Scale Elastic Distributed Systems(2011)6 cited
• → Nature Inspired Load Balancing Algorithms- A Review(2019)2 cited
• → Distributed Dynamic Load Balancing in P2P Grid Systems(2011)