Group Theory Based Data Dependence Model For Loop Parallelization

Along with the development of quantum computing,photon computing,biological computing model,and a variety of hybrid computing mode,directed parallel programming will become more complex and more expensive.So the strong demand for automatic parallelization is naturally increasing.However,this area is still developed slowly and constraint by the complex of the program structure,the fuzzy of semantic information,the development of the platforms,the random state of runtime and so on.This dissertation focuses on the parallelization of iteration space slicing,which is a sub field of automatic parallelization.The basic idea is to partition the loop iteration space with data dependence constraints and divide it into different subsets named slices to execute in parallel on different processors.The goal of slicing parallel is to achieve no synchronization(dependence)or weak synchronization(dependence)parallelism among slices.The existing approaches are usually based on the graph theory,and use matrix multiplications to compute the transitive closure of data dependence(connected subgraphs),which are obviously expensive.This dissertation is based on permutation(or transformation)group,and takes a data dependence relation as a group element's action on a basic set,and takes the transitive closure of the data dependence as an orbit of group.Then the traditional slicing problem is transformed into the solution of group orbits in iteration space.Employing the characteristic of symmetry,we can obtain a concise representation of an orbit,which is similar to a coset of a group.Based on this,we can quickly slicing the iteration space and obtain the slices,and then perform code scanning within each slice.Further,employing the theory of group structure,we can modeling a hierarchical mode for the actions of multiple data dependence relations,which may be different types.This will enable whether the slices of synchronization-free,or the slices of synchronization constrained by multiple conditions,can be effectively obtained.Whether this makes synchronization sections under multiple constraint conditions,no synchronization section,can be effectively obtained.We first classify the data dependence,for different types of data dependences,construct different group representation model.While the actions of different data dependences will lead to the merge of orbits.Then,we take the orbits as slices directly,and add the properties of lexicographic order to elements of slices in order to scan and execute each iteration withinthe slices.The classification our basic method,and it embodies in each model and each chapter of the dissertation.The following is the main content:(1)we built an Abelian group model framework for commutative relations,which include a non-uniform relation and uniform relation models and their algorithms.For the multidimensional uniform relations,we built a translation group model.(2)For the affine data dependence,we proposed a framework to decompose the original orbit into several sub orbits in order to solve it easily,and then combine them into a solution.In this framework,the affine dependence is classified according to the non full rank and full rank,as well as one-dimensional and multidimensional two angles,and is divided into several types.Then,we proposed different methods according to the different types.For one-dimensional affine dependence,we proposed the model to decompose them to basic hyperplane and then merge them by some relations.For the affine dependence with full rank,we use all the threads to detect the slice,but only the first thread within a slice perform scanning.Each thread can recognize its position and do its action.For the cooperative work of the threads,we call it self organization.These methods(including the methods of translation group)for different dependences are incorporated into the framework as a subspace processing approach.(3)For the branch structure embedded in a nested loop,we built an iteration space decomposition model,and classify the branch condition into several types: affine,periodic,monotone,probabilistic,and so on.Then,for each type of branch condition,study geometry and topology structures of iteration space.On this basis,we combined with the corresponding data dependent delineation based on iteration space.For each of the above approaches,relevant experimental comparisons have been made and good results have been obtained.