A FAST HEURISTIC FOR LOOP PARALLELIZATION
Richard Anderson, Barbara B. Simons · Parallel Processing Letters · 1994
We present a fast loop parallelization heuristic that assigns separate invocations of a loop to different processors. If the loop contains data dependences between iterations, later iterations can be delayed while awaiting a result computed in an earlier iteration. In this paper we study a scheduling problem, called the Delay Problem, that approximates the problem of minimizing the delay in the start time of loops with loop-carried dependences. Our major result is a fast (O(n log 2 n)) time algorithm for the case where the precedence constraints are a forest of in-trees or a forest of out-trees. Since most graphs for the Delay Problem that arise in practice are sparse and consist of such a forest with possibly a few additional edges, this is an important case. We prove that the Delay Problem becomes NP-Complete when the precedence constraints are a set of arbitrary trees. We also prove that the Delay Problem becomes NP-Complete for independent chains when it is generalized to allow either non-unit execution times or release times and deadlines.