research-article

A shape analysis for optimizing parallel graph programs

Authors:

Dimitrios Prountzos,

Roman Manevich,

Keshav Pingali,

Kathryn S. McKinleyAuthors Info & Claims

POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

Pages 159 - 172

https://doi.org/10.1145/1926385.1926405

Published: 26 January 2011 Publication History

Abstract

Computations on unstructured graphs are challenging to parallelize because dependences in the underlying algorithms are usually complex functions of runtime data values, thwarting static parallelization. One promising general-purpose parallelization strategy for these algorithms is optimistic parallelization.

This paper identifies the optimization of optimistically parallelized graph programs as a new application area, and develops the first shape analysis for addressing this problem. Our shape analysis identifies failsafe points in the program after which the execution is guaranteed not to abort and backup copies of modified data are not needed; additionally, the analysis can be used to eliminate redundant conflict checking. It uses two key ideas: a novel top-down heap abstraction that controls state space explosion, and a strategy for predicate discovery that exploits common patterns of data structure usage.

We implemented the shape analysis in TVLA, and used it to optimize benchmarks from the Lonestar suite. The optimized programs were executed on the Galois system. The analysis was successful in eliminating all costs related to rollback logging for our benchmarks. Additionally, it reduced the number of lock acquisitions by a factor ranging from 10x to 50x, depending on the application and the number of threads. These optimizations were effective in reducing the running times of the benchmarks by factors of 2x to 12x.

Supplementary Material

MP4 File (15-mpeg-4.mp4)

Download
106.24 MB

References

[1]

A. Adl-Tabatabai, B. T. Lewis, V. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and runtime support for efficient software transactional memory. In PLDI. ACM, 2006.

Digital Library

[2]

A. Braunstein, M. Mézard, and R. Zecchina. Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms, 27(2):201--226, 2005.

Digital Library

[3]

C. Calcagno, D. Distefano, P. W. O'Hearn, and H. Yang. Footprint analysis: A shape analysis that discovers preconditions. In SAS, 2007.

Digital Library

[4]

S. Cherem, T. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. In PLDI. ACM, 2008.

Digital Library

[5]

T. Cormen, C. Leiserson, R. Rivest, and C. Stein, editors. Introduction to Algorithms. MIT Press, 2001.

Digital Library

[6]

A. Dragojevic, Y. Ni, and A. Adl-Tabatabai. Optimizing transactions for captured memory. In SPAA, 2009.

Digital Library

[7]

D. Eppstein. Spanning trees and spanners, pages 425--461. Elsevier, 1999.

[8]

I. Filipovic, P. W. O'Hearn, N. Rinetzky, and H. Yang. Abstraction for concurrent objects. In ESOP, 2009.

Digital Library

[9]

T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA '03, 2003.

Digital Library

[10]

T. L. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing memory transactions. In PLDI. ACM, 2006.

Digital Library

[11]

M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPOPP. ACM, 2008.

Digital Library

[12]

M. Herlihy and J. Eliot B. Moss. Transactional memory: architectural support for lock-free data structures. In ISCA, 1993.

Digital Library

[13]

M. Hicks, J. S. Foster, and P. Pratikakis. Lock inference for atomic sections. In TRANSACT, June 2006.

[14]

D. Jackson. Software Abstractions: Logic, Language, and Analysis. The MIT Press, 2006.

Digital Library

[15]

M. Kulkarni, M. Burtscher, C. Cascaval, and K. Pingali. Lonestar: A suite of parallel irregular programs. In ISPASS, 2009.

[16]

M. Kulkarni, P. Carribault, K. Pingali, G. Ramanarayanan, B. Walter, K. Bala, and L. P. Chew. Scheduling strategies for optimistic parallel execution of irregular programs. In SPAA '08, 2008.

Digital Library

[17]

M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. In PLDI. ACM, 2007.

Digital Library

[18]

V. Kuncak and M. C. Rinard. Decision procedures for set-valued fields. Electr. Notes Theor. Comput. Sci., 131, 2005.

Digital Library

[19]

V. Kuncak and M. C. Rinard. An overview of the jahob analysis system: project goals and current status. In IPDPS, 2006.

Digital Library

[20]

S. K. Lahiri and R. E. Bryant. Predicate abstraction with indexed predicates. ACM Trans. Comput. Log., 9(1), 2007.

Digital Library

[21]

P. Lam, V. Kuncak, and M. C. Rinard. Generalized typestate checking using set interfaces and pluggable analyses. SIGPLAN Notices, 39(3), 2004.

Digital Library

[22]

T. Lev-Ami and M. Sagiv. TVLA: A framework for implementing static analyses. In SAS, 2000.

Digital Library

[23]

R. Manevich, S. Sagiv, G. Ramalingam, and J. Field. Partially disjunctive heap abstraction. In SAS, 2004.

[24]

M. Marron, D. Stefanovic, D. Kapur, and M. V. Hermenegildo. Identification of heap-carried data dependence via explicit store heap models. In LCPC, pages 94--108, 2008.

Digital Library

[25]

B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL. ACM, 2006.

Digital Library

[26]

M. Meéndez-Lojo, D. Nguyen, D. Prountzos, X. Sui, M. A. Hassaan, M. Kulkarni, M. Burtscher, and K. Pingali. Structure-driven optimizations for amorphous data-parallel programs. In PPOPP. ACM, 2010.

Digital Library

[27]

K. Pingali, M. Kulkarni, D. Nguyen, M. Burtscher, M. Mendez-Lojo, D. Prountzos, X. Sui, and Z. Zhong. Amorphous data-parallelism in irregular algorithms. regular tech report TR-09-05, The University of Texas at Austin, 2009.

[28]

A. Podelski and T. Wies. Boolean heaps. In SAS, 2005.

Digital Library

[29]

P. Prabhu, G. Ramalingam, and K. Vaswani. Safe programmable speculative parallelism. In PLDI, 2010.

Digital Library

[30]

D. Prountzos, R. Manevich, K. Pingali, and K. S. McKinley. A shape analysis for optimizing parallel graph programs. Technical Report TR-10--27, UT Austin, http://userweb.cs.utexas.edu/users/ dprountz/UTCS-TR-10-27.pdf,Jul 2010.

[31]

L. Rauchwerger and D. A. Padua. The LRPD test: Speculative runtime parallelization of loops with privatization and reduction parallelization. IEEE Trans. Parallel Distrib. Syst., 10(2):160--180, 1999.

Digital Library

[32]

M. Sagiv, T. Reps, and R. Wilhelm. Parametric shape analysis via 3-valued logic. ACM Trans. Program. Lang. Syst., 24(3), 2002.

Digital Library

[33]

A. Salcianu and M. C. Rinard. Purity and side effect analysis for java programs. In VMCAI, 2005.

Digital Library

[34]

K. Zee, V. Kuncak, and M. Rinard. Full functional verification of linked data structures. In PPOPP. ACM, 2008.

Digital Library

Cited By

Lu YPingali K(2017)Can Parallel Programming Revolutionize EDA Tools?Advanced Logic Synthesis10.1007/978-3-319-67295-3_2(21-41)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-67295-3_2
Ferrara PTripp OLiu PKoskinen E(2017)Using Abstract Interpretation to Correct Synchronization FaultsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-319-52234-0_11(187-208)Online publication date: 12-Jan-2017
https://doi.org/10.1007/978-3-319-52234-0_11
Nicolay JStiévenart QDe Meuter WDe Roover C(2017)Purity analysis for JavaScript through abstract interpretationJournal of Software: Evolution and Process10.1002/smr.188929:12Online publication date: 25-Aug-2017
https://doi.org/10.1002/smr.1889
Show More Cited By

Index Terms

A shape analysis for optimizing parallel graph programs
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language types
        Parallel programming languages

Recommendations

A shape analysis for optimizing parallel graph programs
POPL '11

Computations on unstructured graphs are challenging to parallelize because dependences in the underlying algorithms are usually complex functions of runtime data values, thwarting static parallelization. One promising general-purpose parallelization ...
Structure-driven optimizations for amorphous data-parallel programs
PPoPP '10

Irregular algorithms are organized around pointer-based data structures such as graphs and trees, and they are ubiquitous in applications. Recent work by the Galois project has provided a systematic approach for parallelizing irregular applications ...
Structure-driven optimizations for amorphous data-parallel programs
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Irregular algorithms are organized around pointer-based data structures such as graphs and trees, and they are ubiquitous in applications. Recent work by the Galois project has provided a systematic approach for parallelizing irregular applications ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

January 2011

652 pages

ISBN:9781450304900

DOI:10.1145/1926385

General Chair:
Thomas Ball
Microsoft Research, USA
,
Program Chair:
Mooly Sagiv
Tel Aviv University, Israel

ACM SIGPLAN Notices Volume 46, Issue 1
POPL '11
January 2011
624 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1925844
Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 26 January 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

POPL '11

Sponsor:

SIGPLAN

POPL '11: The 38th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

January 26 - 28, 2011

Texas, Austin, USA

Acceptance Rates

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
535
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lu YPingali K(2017)Can Parallel Programming Revolutionize EDA Tools?Advanced Logic Synthesis10.1007/978-3-319-67295-3_2(21-41)Online publication date: 16-Nov-2017
https://doi.org/10.1007/978-3-319-67295-3_2
Ferrara PTripp OLiu PKoskinen E(2017)Using Abstract Interpretation to Correct Synchronization FaultsVerification, Model Checking, and Abstract Interpretation10.1007/978-3-319-52234-0_11(187-208)Online publication date: 12-Jan-2017
https://doi.org/10.1007/978-3-319-52234-0_11
Nicolay JStiévenart QDe Meuter WDe Roover C(2017)Purity analysis for JavaScript through abstract interpretationJournal of Software: Evolution and Process10.1002/smr.188929:12Online publication date: 25-Aug-2017
https://doi.org/10.1002/smr.1889
Estebanez ALlanos DGonzalez-Escribano A(2016)A Survey on Thread-Level Speculation TechniquesACM Computing Surveys10.1145/293836949:2(1-39)Online publication date: 30-Jun-2016
https://dl.acm.org/doi/10.1145/2938369
Liu PTripp OZhang X(2014)FlintACM SIGPLAN Notices10.1145/2714064.266021749:10(543-560)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2714064.2660217
Liu PTripp OZhang XBlack AMillstein T(2014)FlintProceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages & Applications10.1145/2660193.2660217(543-560)Online publication date: 15-Oct-2014
https://dl.acm.org/doi/10.1145/2660193.2660217
Wu JHu GTang YYang JMeyer BBaresi LMezini M(2013)Effective dynamic detection of alias analysis errorsProceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering10.1145/2491411.2491439(279-289)Online publication date: 18-Aug-2013
https://dl.acm.org/doi/10.1145/2491411.2491439
Lublinerman RZhao JBudimlić ZChaudhuri SSarkar V(2011)Delegated isolationACM SIGPLAN Notices10.1145/2076021.204813346:10(885-902)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2076021.2048133
Lublinerman RZhao JBudimlić ZChaudhuri SSarkar VLopes CFisher K(2011)Delegated isolationProceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications10.1145/2048066.2048133(885-902)Online publication date: 22-Oct-2011
https://dl.acm.org/doi/10.1145/2048066.2048133
Pingali KNguyen DKulkarni MBurtscher MHassaan MKaleem RLee TLenharth AManevich RMéndez-Lojo MPrountzos DSui XHall MPadua D(2011)The tao of parallelism in algorithmsProceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/1993498.1993501(12-25)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/1993498.1993501
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents