Scheduling Sequential Loops on Parallel Processors
Ashfaq A. Munshi, Barbara B. Simons · SIAM Journal on Computing · 1990
Automatic parallelization of code written in a sequential language such as FORTRAN is of great importance for compilers for parallel computers. First, the problem of automatically parallelizing iterative loops on multiprocessors is discussed, and then a scheduling problem involving precedence constraints that models a technique for the automatic parallelization is derived. Polynomial time algorithms are presented for some special cases of this scheduling problem together with an upper bound on a naive algorithm for the general case. Using one of the polynomial time algorithms, a heuristic for the original compiler problem is obtained. Finally, test results obtained by applying our heuristic to EISPACK, a well-known umerical analysis FORTRAN package, are presented. In these tests the amount of parallelism obtained always equals and frequently surpasses that obtained by the best known techniques in the literature. This approach represents one of the first attempts at understanding the complexity theoretic aspects of loop parallelization.