Termination detection in parallel loop nests with while loops

摘要

One central problem in the execution of parallel nested loops with non-affine bounds is the precise scanning (i.e., enumeration) of the points in their iteration space and the detection of their termination. Scanning schemes have been proposed for both shared-memory and dis- tributed-memory implementations. However, these schemes work only for perfectly nested while loops. We propose a scheme which also works for not perfectly nested while loops on shared memory. This scheme has been incorporated in our loop parallelizer Loop.