There are many methods for nested loop partitioning exist; however, most of them perform poorly when they partition loops with non-uniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism which can exploit parallelism in nested loops with non-uniform dependences. Our approach based on the region partitioning technique divides the loop into variable size partitions. Furthermore, the proposed algorithm partitions a nested loop using the copy-renaming and optimized partitioning techniques so as to minimize the serial part of the iteration space. Thus, it out performs previous partition mechanisms for nested loops with non-uniform dependences. Compared with other popular techniques, our scheme shows dramatic improvement in preliminary performance results.

Keywords: compilers, non-uniform dependence, loop parallelization, parallel compiler, parallel processing, region partitioning technique

Retrieve PDF document (200105_07.pdf)

Received May 19, 1999; revised July 21, 1999; accepted November 15, 1999.
Communicated by Jang-Ping Sheu.