UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Efficient Identification of Linchpin Vertices in Dependence Clusters

Binkley, D; Gold, N; Harman, M; Islam, S; Krinke, J; Li, Z; (2013) Efficient Identification of Linchpin Vertices in Dependence Clusters. ACM Transactions on Programming Languages and Systems , 35 (2) , Article ARTN 7. 10.1145/2491522.2491524. Green open access

[img] PDF
toplas13.pdf

Download (753kB)

Abstract

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.

Type: Article
Title: Efficient Identification of Linchpin Vertices in Dependence Clusters
Open access status: An open access version is available from UCL Discovery
DOI: 10.1145/2491522.2491524
Publisher version: http://dx.doi.org/10.1145/2491522.2491524
Language: English
Additional information: © 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
Keywords: Algorithms, Performance, Slicing, Internal representation, Performance enhancement, Empirical study
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Pop Health Sciences > Institute of Health Informatics
UCL > Provost and Vice Provost Offices > School of Life and Medical Sciences > Faculty of Pop Health Sciences > Institute of Health Informatics > CHIME
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/1388948
Downloads since deposit
356Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item