| Abstract: | For a compiler, dependence direction vectors are the key structure for many loop parallelizing transformations. More powerful transformations require knowing the values of the associated distances. However, this generally involves solving many problems. In this paper, we consider a hierarchical set of problems which differ only in direction vectors, as in the framework introduced by Burke and Cytron. Firstly, we solve the basic problem of the existence of a dependence without direction constraints, using a fast and exact algorithm composed of a pre-processing phase of reduction and of an integer simplex resolution. We propose a new “basic” algorithm. Secondly, if a solution exists, we define three new problems, each of them being obtained by adding a constraint associated with one of the three possible direction vectors relative to the first loop index. For each of these problems, if a solution exists, we define three enlarged similar problems involved by the second loop index, and so forth until the last index. The amount of computation for each new problem is very low. Information on the values of the distances is provided. The Janus Test, implemented at INRIA, has been embedded in the parallelizer built within the esprit project Compare and in the PARTITA tool of the EUREKA project EUROTOPS. Due to its robustness, it could be applied to more complex problems in data dependence and data flow analysis. |
