An Abelian group model of commutative data dependence relations for the iteration space slicing

摘要

In loop parallelization, data dependence relations are used to decide which pair of statement instances should be allocated to a same processor or should have a synchronization communication. However, in existing researches, little attention has been paid to the widespread symmetrical patterns of data dependence implied in the loop iteration. These patterns are usually induced by the regular expressions as array indices. If these expressions are all of the same type, the transitive calculations of them are always commutative. In this paper, we introduce a permutation group model to represent data dependences and discuss the application of the model. We focus on three issues: 1) the basic permutation model and the symmetrical patterns 2) the application of Abelian group theory for commutative relations such as some uniform (addition) relations, multiplication relations and hybrids relations, and 3) an approach to obtaining the iteration slices for parallelization based on previous analyses.