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.