Scheduling sequential loops on parallel processors. (English) Zbl 0697.68028

Summary: 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 numerical 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.


68N99 Theory of software
68Q25 Analysis of algorithms and problem complexity
68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
68R10 Graph theory (including graph drawing) in computer science


Full Text: DOI