Dynamic Scheduling of Parallel Loops with Variable Iterate Execution Times
Carino, R.L., & Banicescu, I. (2002). Dynamic Scheduling of Parallel Loops with Variable Iterate Execution Times. Proc. 16th International Parallel and Distributed Processing Symposium, 2002 CDROM. IEEE. 239-246.
Abstract
To improve performance of scientific applications in parallel
and distributed environments, dynamic scheduling algorithms
for parallel loops have been proposed. Such algorithms
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, algorithms 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 algorithms execute the iterates
in variable size chunks, where the sizes are determined such
that the chunks complete before the optimal time with a high
probability. These algorithms have successfully been implemented
in a number of scientific applications such as:
N-Body and Monte Carlo simulations, CFD, and radar signal
processing. This paper presents a comparative study
of the performance of various loop scheduling algorithms
in a message-passing environment. The algorithms have
been integrated into a tool for executing parallel loops, and
the tool applied in profiling quadrature routines that are often
used in scientific computations such as finite element
methods, particle physics, and multivariate statistics. Experimental
results reveal the effectiveness and robustness of
the latest developed scheduling algorithms over the previous
ones on loops with irregular iterate execution times.