An optimized dependence convex hull partitioning technique to maximize parallelism of nested loops with non-uniform dependences

Abstract

There are many methods existing for nested loop partitioning; however most of them perform poorly when partitioning loops with non-uniform dependences. This paper proposes a generalized and optimized loop partitioning mechanism to exploit parallelism from nested loops with non-uniform dependences. Our approach based on the dependence convex theory will divide the loop into variable size partitions. Furthermore, the proposed algorithm partitions a nested loop by using the copy-renaming and the optimized partitioning techniques to minimize the number of parallel regions of the iteration space, outperforming the other previous partition mechanisms of nested loops with non-uniform dependences.