Termination detection in parallel loop nests with while loops

One central problem in the execution of parallel nested loops with non-affi ne bounds is the precise scanning (i.e., enumeration) of the points in thei r iteration space and the detection of their termination. Scanning schemes have been proposed for both shared-memory and distributed-memory implementa tions. However, these schemes work only for perfectly nested while loops. W e propose a scheme which also works for not perfectly nested while loops on shared memory. This scheme has been incorporated in our loop parallelizer LooPo. (C) 1999 Elsevier Science B.V. All rights reserved.