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.

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.