Unique sets oriented partitioning of nested loops with non-uniform dependences

Although many methods exist for nested loop partitioning, most of them perform poorly when parallelizing loops with non-uniform dependences. This paper addresses the issue of parallelizing nested loops with non-uniform dependences. The approach is based on convex hull theory, which has adequate information to handle non-uniform dependences. We introduce the concept of Complete Dependence Convex Hull, unique head and tail sets and abstract the dependence information into these sets. These sets form the basis of the iteration space partitions. The properties of the unique head and tail sets are derived using convex hull theory. Depending on the relative placement of these unique sets, the partitioning problem is grouped into several cases. Several partitioning schemes are also suggested for implementing the technique. Preliminary implementation results of the scheme on the Cray J916 and comparison with other schemes show a dramatic improvement in performance