Transitive Closure of Infinite Graphs and its Applications

Transitive Closure of Infinite Graphs and its Applications

##### Files

##### Publication or External Link

##### Date

1998-10-15

##### Authors

Kelly, Wayne

Pugh, William

Rosser, Evan

Shpeisman, Tatiana

##### Advisor

##### Citation

##### DRUM DOI

##### Abstract

Integer tuple relations can concisely summarize many types of
information 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 tuples. For example, it is impossible to enumerate the
related pairs of tuples in the relation {[i] -> [i+2] | 1 <= i <=
n-2}. Even when it is possible to enumerate the related pairs of
tuples, such as for the relation {[i,j] -> [i',j'] | 1 <= i,j,i',j' <=
100}, it is often 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 parameterized, so what we are really describing are
infinite families of relations (or graphs). Many of our applications
of tuple relations rely heavily on an operation called transitive
closure. Computing the transitive closure of these "infinite graphs"
is very different from the traditional problem of computing the
transitive closure of a graph whose edges can be enumerated. For
example, the transitive closure of the first relation above is the
relation {[i] -> [i'] | exists beta s.t. i'-i = 2beta and 1 <= i <= i'
<= n}. As we will prove, this computation is not computable in the
general case. We have developed algorithms that produce exact results
in most commonly occurring cases and produce upper or lower bounds (as
necessary) in the other cases. This paper will describe our algorithms
for computing transitive closure and some of its applications such as
determining which inter-processor synchronizations are redundant.
(Also cross-referenced as UMIACS-TR-95-48)