Dynamic Load Balancing With Adaptive Factoring Methods in Scientific Applications
Carino, R.L., & Banicescu, I. (2007). Dynamic Load Balancing With Adaptive Factoring Methods in Scientific Applications. In Hamid R. Arabnia (Ed.), Journal of Supercomputing. Springer. Online.
Abstract
To improve the performance of scientific applications with parallel
loops, dynamic loop scheduling methods have been proposed.
Such methods address performance degradations due to
load imbalance caused by predictable phenomena like nonuniform
data distribution or algorithmic variance, and unpredictable
phenomena such as data access latency or operating system
interference.
In particular, methods such as factoring, weighted factoring,
adaptive weighted factoring, and adaptive factoring have been
developed based on a probabilistic analysis of parallel loop iterates
with variable running times.
These methods have been successfully implemented in a number of applications
such as: N-Body and Monte Carlo simulations, computational fluid
dynamics, and radar signal processing.
The focus of this paper is on adaptive weighted factoring (AWF),
a method that was designed for scheduling parallel loops in
time-stepping scientific applications. The main contribution of the paper
is to relax the time-stepping requirement, a modification that
allows the AWF to be used in any application with a parallel loop.
Results of experiments to compare the performance of the modified AWF
with the performance of the other loop scheduling methods in the
context of three nontrivial applications reveal that the performance of the
modified method is comparable to, and in some cases, superior to the
performance of the most recently introduced adaptive factoring method.