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