Dynamic scheduling parallel loops with variable iterate execution times
Abstract
© 2002 IEEE. 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.
Source or Periodical Title
Proceedings - International Parallel and Distributed Processing Symposium, IPDPS 2002
Page
239
Document Type
Article
Recommended Citation
Cariño, R. L. and Banicescu, I., "Dynamic scheduling parallel loops with variable iterate execution times" (2021). Journal Article. 3220.
https://www.ukdr.uplb.edu.ph/journal-articles/3220