Compile time partitioning of nested loop iteration spaces with non-uniform dependences

In this paper we address the problem of partitioning nested loops with non-uniform (irregular) depen-dence vectors. Parallelizing and partitioning of nested loops requires efficient inter-iteration depen-dence analysis. Although many methods exist for nested loop partitioning, most of these perform poorly when parallelizing nested loops with irregular dependences. Unlike the case of nested loops with uni-form dependences these will have a complicated dependence pattern which forms a non-uniform depen-dence vector set. We apply the results of classical convex theory and principles of linear programming to iteration spaces and show the correspondence between minimum dependence distance computation and iteration space tiling. Cross-iteration dependences are analyzed by forming an Integer Depen-dence Convex Hull (IDCH). Every integer point in this IDCH corresponds to a dependence vector in the iteration space of the nested loops. A simple way to compute minimum dependence distances from the dependence distance vectors of the extreme points of the IDCH is presented. Using these minimum dependence distances the iteration space can be tiled. Iterations within a tile can be executed in par-allel and the different tiles can then be executed with proper synchronization. We demonstrate that our technique gives much better speedup and extracts more parallelism than the existing techniques.