Several compile time transformations of loops with simple dependencies have been developed in order to expose possible parallelism in these loops. However, once an irregular data dependence is detected, no attempt is usually made to extract any parallel thread from the loop. In this paper, we present the parallel region execution, a new compile time approach for improving the execution of loops with complex dependencies. It consists of dividing the iteration space of the loop into parallel regions and serial regions, where all the iterations in the parallel regions can be fully executed in parallel. Our parallel region execution technique has been tested on the MasPar machine for various examples and generally resulted in a large speedup.

Traditional dependence analysis techniques usually attempt to recognize the existence of dependencies between iterations of a loop and, in some cases, characterize these dependencies by finding direction vectors or distance vectors. A more general form of data dependence called hyperplane dependence is introduced. It is a dependence whose source and destination are subspaces of the iteration space. This dependence form can be useful mainly for expressing dependencies across loop-nests, and consequently better understand the interaction between the loops. In order to be able to express across loop dependencies and analyze all loops in the code simultaneously, a global iteration space for all loops in the code is formed. Hyperplane dependence analysis is used to improve automatic generation of communication statements across loops and index alignment for n-dimensional grid target machines.>

Partitioning the iteration space can significantly affect the execution time of a loop. The authors propose an improvement over previous partitioning methods for single loops with uniform data dependencies. For distributed memory systems, partitioning each loop separately does not guarantee an efficient execution of the code because of across loop data dependence. As a result, a global iteration space is formed so that all loops in a program are considered when partitioning the global space. In addition, a new and general form of data dependence called hyperplane dependence is introduced and used in the partitioning. It is a dependence whose source and destination are subspaces (of any dimension) of the global iteration space.