TY  - JOUR
ID  - discovery1388948
UR  - http://dx.doi.org/10.1145/2491522.2491524
IS  - 2
N2  - Several authors have found evidence of large dependence clusters in the source code of a diverse range of systems, domains, and programming languages. This raises the question of how we might efficiently locate the fragments of code that give rise to large dependence clusters. We introduce an algorithm for the identification of linchpin vertices, which hold together large dependence clusters, and prove correctness properties for the algorithm?s primary innovations. We also report the results of an empirical study concerning the reduction in analysis time that our algorithm yields over its predecessor using a collection of 38 programs containing almost half a million lines of code. Our empirical findings indicate improvements of almost two orders of magnitude, making it possible to process larger programs for which it would have previously been impractical.
AV  - public
SN  - 0164-0925
Y1  - 2013/07//
TI  - Efficient Identification of Linchpin Vertices in Dependence Clusters
A1  - Binkley, D
A1  - Gold, N
A1  - Harman, M
A1  - Islam, S
A1  - Krinke, J
A1  - Li, Z
JF  - ACM Transactions on Programming Languages and Systems
KW  - Algorithms
KW  -  Performance
KW  -  Slicing
KW  -  Internal representation
KW  -  Performance enhancement
KW  -  Empirical study
VL  - 35
N1  - © ACM, 2013. This is the authors? version of the work. It is posted here by permission of ACM for your personal use. Not
for redistribution. The definitive version was published in ACM Transactions on Programming Languages and Systems, 35,
2, (July 2013) http://dx.doi.org/10.1145/2491522.2491524
ER  -