© 1997 by British Computer Society
| ||||||||||||||||||||||||||||||||||||||||||||||||||||
Unique Sets Oriented Parallelization of Loops with Non-uniform Dependences
Parallel and Distributed Computing Laboratory, Wayne State University, Detroit, MI 48202, USA Email: vipin{at}eng.wayne.edu
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 parallelized in rare instances, the performance is very poor. Our approach is based on the ‘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. 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 technique.
Received November 4, 1996. revised July 15, 1997.