PARTITIONING AND LABELING OF LOOPS BY UNIMODULAR TRANSFORMATIONS

In a nested loop the indexes form an index vector and the index vectors of all iterations form the index set. The dependencies between the loop iterations are represented by dependence vectors, which are stored as the columns of the dependence matrix. Parallel execution of the independent subsets of the index set requires no communication or synchronization and is therefore quite efficient. A general method for the identification of the independent subsets in loops with constant dependence vectors is presented. First it is shown that the dependence relation remains invariant under a unimodular transformation. Then a unimodular transformation is used to bring the dependence matrix into a form where the independent subsets are obtained by a direct and inexpensive partitioning algorithm. This leads to a procedure for the automatic conversion of a serial loop into a nest of parallel DO-ALL loops. Another unimodular transformation results in an algorithm to label the dependent iterations of an n-fold nested loop in O(n2) time. This provides a multithreaded dynamic scheduling scheme requiring only one fork and one join primitive.