TRANSITIVE CLOSURE OF INFINITE-GRAPHS AND ITS APPLICATIONS

Integer tuple relations can concisely summarize many types of informat ion gathered from analysis of scientific codes. For example, they can be used to precisely describe which iterations of a statement are data dependent of which other iterations. It is generally not possible to represent these tuple relations by enumerating the related pairs of tu ples. For example, it is impossible to enumerate the related pairs of tuples in relation {[i] --> [i + 2]\1 less than or equal to i less tha n or equal to n - 2}. Even when it is possible to enumerate the relate d pairs of tuples, such as for the relation {[i, j] --> [i', j']\1 les s than or equal to i, j, i', j' less than or equal to 100}, it is ofte n not practical to do so. We instead use a closed form description by specifying a predicate consisting of affine constraints on the related pairs of tuples. As we just saw; these affine constraints can be para meterized, so what we are really describing are infinite families of r elations (or graphs!. Many of our applications of tuple relations rely heavily on an operation called transitive closure. Computing the tran sitive closure of these ''infinite graphs'' is very different from the traditional problem of computing the transitive closure of a graph wh ose edges can be enumerated. For example, the transitive closure of th e first relation above is the relation {[i] --> [i']\There Exists beta s.t. i' - i = 2 beta boolean AND 1 less than or equal to i less than or equal to i' less than or equal to n}. As we will prove, transitive closure is not comutable in the general case. We have developed algori thms that produce exact results in most commonly occuring cases and pr oduce upper of lower bounds (as necessary! in the other cases. This pa per will describe ou algorithms for computing transitive closure and s ome of its applications such as determining which inter-processor sync hronizations are redundant.