A-CluB: Automated Cluster Breaking

Recent work shows that many real world programs contain large dependence clusters: knots of mutually dependent program statements. In a dependence cluster, every statement depends on every other statement. It is not hard to imagine the difficulties that large dependence clusters may produce. In order to understand any statement in a dependence cluster, it is possible that all other statements in the cluster need to be considered. It will be very hard to disentangle statements in a cluster to allow reuse of components, or refactoring of the system. Any potential change to an element of a cluster, will have an impact that is large and potentially far reaching, because it may affect any or all of the other statements in the cluster.This visiting fellow project builds on the previous work of Binkley and Harman (and others) on slice based dependence analysis. The aim is to better understand the empirically observed phenomenon of dependence clusters and to develop algorithms and techniques for decomposing these clusters. This will produce algorithms and methods for Automated Cluster Busting, thereby overcoming the problems that these clusters pose.