On the parallelization of loop nests containing while loops
Christian Lengauer, Martin Griebl · 2002
Recently, efforts have been made to devise automatic methods, based on a mathematical model, for the parallelization of loop nests with while loops. These methods are extensions of methods for the parallelization of nested for loops. As we present the theory, the parallelization of a nest of d loops is guaranteed to lay out one loop in time and d-l loops in space (one can trade off additional dimensions from space to time). The spacetime complexity of the target loop nest is equal to the time complexity of the source loop nest (whose space complexity is constant).>