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

摘要

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 dependence convex theory, divides a loop into variable-size partitions. Furthermore, the proposed algorithm partitions a nested loop by using the copy-renaming and optimized partitioning techniques in order to minimize the number of parallel regions of the iteration space, outperforming other previous mechanisms for partitioning nested loops with non-uniform dependences.