UNIQUE SETS ORIENTED PARALLELIZATION OF LOOPS WITH NONUNIFORM 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 automatic parallelization of loops with non-uniform dependences. Such loops are normally not parallelized by existing parallelizing compilers and transformations. Even when pa rallelized in rare instances, the performance is very poor, Our approa ch is based on the 'convex hull' theory which has adequate information to handle non-uniform dependences. We introduce the concept of 'compl ete 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 a nd tail sets are derived. Depending on the relative placement of these unique sets, partitioning schemes are suggested for implementation of our technique. Implementation results of our scheme on the Cray J916 and comparison with other schemes show the superiority of our techniqu e.