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.
![[thumbnail of toplas13.pdf]](https://discovery.ucl.ac.uk/style/images/fileicons/application_pdf.png) |
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 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: | https://discovery.ucl.ac.uk/id/eprint/1388948 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
