In this paper, a dependence cluster is defined to be a set of program statements, all of which are mutually interdependent. While dependence clusters have been studied at higher levels of abstraction (for example, at the function and module levels), this is the first attempt to study them at the statement level.
In order to provide an efficient means of computing dependence clusters, the authors postulate that these can be approximated by considering all program slices of the same size as representing components of a cluster. The size of the cluster is measured in terms of nodes of the system dependence graph (SDG) of the program. This approach is conservative in that, at worst, it will admit false negatives. By visualizing the slice sizes as a monotonically increasing profile, a group of slices of similar size appears as a clear plateau.
Forty-five C programs from a variety of application areas and totaling around 900,000 noncomment, nonblank lines were used as a test bed for study. The results presented support the use of slice sizes to construct good approximations to dependence clusters. In addition, close to 90 percent of the programs used included clusters consisting of between 10 and 70 percent of the program.
Further analysis showed that, for many of the programs considered, a small number of nodes of the SDG exerted a strong effect on the size of the dependence cluster. These nodes were all predicate nodes. Identification of these nodes could provide a good pointer to how the software might be refactored to reduce cluster size.
Finally, there is a discussion of how the detection of large dependence clusters may impact areas such as program comprehension, testing, maintenance, reuse, and parallelization.
The paper contains a large number of graphs and a detailed discussion of the analysis of the accuracy of using program slice sizes to approximate the construction of the dependence clusters. There is also an assumption that the reader is familiar with program slicing. For these reasons, the paper is most suited to researchers in the area of practical program analysis.