To model decompositions that change dynamically, we use
a * communication graph* .
The nodes in the graph correspond to the loop nests in the program.
The edges in the graph represent places in the program where data
reorganization communication can occur.

The edges in the graph are calculated using information that is
similar to the * reaching decompositions*[14,33]
used in the Fortran D compiler.
In Fortran D, the reaching decompositions are defined to be the set
of decomposition statements that may reach an
array reference that uses the decomposition.
In our case, all loop nests may define a decomposition.
Thus, the decomposition for an array in one loop nest
reaches another loop nest if it is possible for the values of the array
in the two loop nests to be the same.
This problem can be calculated in a manner similar to the standard reaching
definitions data flow problem.
The edges in the communication graph are the chains formed by the
reaching decompositions, and are not directed.
For simplicity of presentation, this discussion assumes
each array is both read and written in the loop nests that
access the array.

Associated with each edge is the probability that the decomposition in one loop nest will reach the other loop nest. Each loop node has a weight that is a function of the number of instructions in the loop and an estimate of the number of times the loop executes. Our implementation currently uses profile information to calculate the probabilities for the edge weights as well as the loop execution counts for the loop node weights.

Fri Apr 7 14:39:58 PDT 1995