A dynamic scheduling method for irregular parallel programs
Steven E. Lucco · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · 1992
This paper develops a methodology for compiling and executing irregular parallel programs. Such programs implement parallel operations whose size and work distribution depend on input data. We show a fundamental relationship between three quantities that characterize an irregular parallel computation: the total available parallelism, the optimal grain size, and the statistical variance of execution times for individual tasks. This relationship yields a dynamic scheduling algorithm that substantially reduces the overhead of executing irregular parallel operations.
Cited by 69 works. doi:10.1145/143095.143134 Open-access PDF
Authors
References
- The Monte Carlo Method
- Optimizing supercompilers for supercomputers
- A data locality optimizing algorithm
- Computational Design of the Basic Dynamical Processes of the UCLA General Circulation Model
- An efficient method of computing static single assignment form
- A loop transformation theory and an algorithm to maximize parallelism
- Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel Supercomputers
- More iteration space tiling
- Automatic loop interchange
- Allocating Independent Subtasks on Parallel Processors