Addressing the Stochastic Nature of Scientific Computations via Dynamic Loop Scheduling
Banicescu, I., & Carino, R.L. (2005). Addressing the Stochastic Nature of Scientific Computations via Dynamic Loop Scheduling. Electronic Transactions on Numerical Analysis. Kent State University. 21, 68-80.
In general, scientific applications are large, computationally
intensive, irregular and data-parallel. One of the main performance
degradation factors when running scientific applications in parallel and distributed environments is load imbalance that may rise from a wide range of characteristics, due to problem, algorithmic, and systemic factors. Moreover, due to the stochastic behavior of many scientific applications, the load imbalance can unexpectedly occur at runtime, leading to difficulties in making decision about optimal partitioning, allocation and scheduling. In recent years, since parallel loops are prevalent and a major source
of parallelism in scientific computations, many dynamic loop scheduling algorithms have been developed to improve performance via load balancing. These algorithms address the unpredictable behavior of computations, and many of these are based on probabilistic analyses. These have proven to be effective in improving performance of important applications used in scientific computing by addressing the entire spectrum of factors that lead to load imbalance. This paper proposes the use of a dynamic loop scheduling approach for
repartitioning in scientific applications that contain computationally intensive parallel loops. A new partition is computed and data is redistributed during the execution of a parallel loop. This approach addresses load imbalance factors as they arise during a computational step, in contrast to the traditional load balancing approach of determining a new partition and migrating data after a computational step.Preliminary performance tests of an application that implements
the proposed approach validate the feasibility and the effectiveness
of the approach.