Expressing cross-loop dependencies through hyperplane data dependence analysis

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