Dynamic scheduling of DOACROSS loops for multiprocessors

The authors address the problem of parallel execution of DOACROSS loops with complex inter-iteration dependences. Rather than treat the scheduling of such loops and their synchronization as distinct and separable issues, the authors treat synchronization and scheduling in a unified framework. The resulting approach is referred to as presynchronized scheduling. The approach is illustrated in the context of DOACROSS loops with regular inter-iteration dependences, as well as with loops that have irregular dependence patterns determinable only at runtime. The scheme is evaluated by implementing a sparse triangular solver on an Encore Multimax shared-memory multiprocessor