research-article

Automatic atomic region identification in shared memory SPMD programs

Authors:

Gautam Upadhyaya,

Samuel P. Midkiff,

Vijay S. PaiAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 10

Pages 652 - 670

https://doi.org/10.1145/1932682.1869513

Published: 17 October 2010 Publication History

Abstract

This paper presents TransFinder, a compile-time tool that automatically determines which statements of an unsynchronized multithreaded program must be enclosed in atomic regions to enforce conflict-serializability. Unlike previous tools, TransFinder requires no programmer input (beyond the program) and is more efficient in both time and space.

Our implementation shows that the generated atomic regions range from being identical to, or smaller than, the programmer-specified transactions in the three Java Grande benchmarks considered, and in five of the eight STAMP benchmarks considered, while still providing identical synchronization semantics and results. The generated atomic regions are between 5 and 38 lines larger in the three remaining STAMP benchmarks. In the most conservative case, TransFinder can, based on the program structure, successfully identify and suggest an alternative that conforms exactly to the programmer-specified atomic regions. By generating small, highly-targeted, conflict-serializable atomic regions, TransFinder allows the programmer to focus further tuning efforts on only a small portion of the code (when further tuning is needed).

References

[1]

}}D. Agrawal, J. L. Bruno, A. El Abbadi, and V. Krishnaswamy. Relative serializability (extended abstract): an approach for relaxing the atomicity of transactions. In PODS '94: Proceedings of the ACM Symposium on Principles of Database Systems, pages 139--149, New York, NY, USA, 1994. ACM.

Digital Library

[2]

}}D. A. Bader and K. Madduri. Design and implementation of the hpcs graph analysis benchmark on symmetric multiprocessors. In HiPC '05: Proceedings of the High Performance Computing Conference, pages 465--476, 2005.

Digital Library

[3]

}}R. Bayer. Consistency of transactions and random batch. ACM Transactions on Database Systems, 11(4):397--404, 1986.

Digital Library

[4]

}}Brad Appleton. Sclc and Cdiff: Perl scripts for ClearCase. At http://www.cmcrossroads.com/broadapp/clearperl/sclc-cdiff.html.

[5]

}}M. J. Cahill, U. Röhm, and A. D. Fekete. Serializable isolation for snapshot databases. In SIGMOD '08: Proceedings of the ACM International Conference on Management of Data, pages 729--738, New York, NY, USA, 2008. ACM.

Digital Library

[6]

}}C. Cao Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC '08: Proceedings of The IEEE International Symposium on Workload Characterization, September 2008.

[7]

}}S. Cherem, T. M. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. In PLDI '08: Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 304--315, 2008.

Digital Library

[8]

}}J.-D. Choi, K. Lee, A. Loginov, R. O'Callahan, V. Sarkar, and M. Sridharan. Efficient and precise datarace detection for multithreaded object-oriented programs. In PLDI '02: Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 258--269, New York, NY, USA, 2002. ACM.

Digital Library

[9]

}}M. Christiaens and K. De Bosschere. Trade, a topological approach to on-the-fly race detection in Java programs. In JVM'01: Proceedings of the 2001 Symposium on JavaTM Virtual Machine Research and Technology Symposium, pages 15--15, Berkeley, CA, USA, 2001. USENIX Association.

Digital Library

[10]

}}R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems, 13(4):451--490, 1991.

Digital Library

[11]

}}D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In Proceedings of the International Symposium on Distributed Computing, pages 194--208, 2006.

Digital Library

[12]

}}A. Dragojević, R. Guerraoui, and M. Kapalka. Stretching transactional memory. In PLDI '09: Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 155--165, New York, NY, USA, 2009. ACM.

Digital Library

[13]

}}R. Elmasri and S. B. Navathe. Fundamentals of Database Systems (5th Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2006.

Digital Library

[14]

}}M. Emmi, J. S. Fischer, R. Jhala, and R. Majumdar. Lock allocation. In POPL '07: Proceedings of the ACM Symposium on Principles of Programming Languages, pages 291--296, New York, NY, USA, 2007. ACM.

Digital Library

[15]

}}EPCC. The Java Grande Forum Benchmark Suite. At http://www.epcc.ed.ac.uk/research/java-grande/. Last accessed March 24, 2010.

[16]

}}P. Felber, C. Fetzer, and T. Riegel. Dynamic performance tuning of word-based software transactional memory. In PPoPP '08: Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming, pages 237--246, New York, NY, USA, 2008. ACM.

Digital Library

[17]

}}R. L. Halpert, C. J. Pickett, and C. Verbrugge. Component-based lock allocation. In PACT '07: Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, pages 353--364, Los Alamitos, CA, USA, 2007. IEEE Computer Society.

Digital Library

[18]

}}T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In PPoPP '05: Proceedings of the Tenth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 48--60, New York, NY, USA, 2005. ACM Press.

Digital Library

[19]

}}M. Herlihy, V. Luchangco, M. Moir, and W. N. Scherer. Software transactional memory for dynamic-sized data structures. In PODC '03: Proceedings of the Symposium on Principles of Distributed Computing, pages 92--101, New York, NY, USA, 2003. ACM Press.

Digital Library

[20]

}}M. Herlihy, J. E. B. Moss, J. Eliot, and B. Moss. Transactional memory: Architectural support for lock-free data structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture, pages 289--300, 1993.

Digital Library

[21]

}}M. Hicks, J. S. Foster, and P. Prattikakis. Lock inference for atomic sections. In Proceedings of the First ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, June 2006.

[22]

}}A. Krishnamurthy and K. Yelick. Analyses and optimizations for shared address space programs. Journal of Parallel and Distributed Computing, 38(2):130--144, 1996.

Digital Library

[23]

}}J. Lee, D. A. Padua, and S. P. Midkiff. Basic compiler algorithms for parallel programs. In PPoPP '99: Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pages 1--12, 1999.

Digital Library

[24]

}}O. Lhoták and L. Hendren. Scaling Java points-to analysis using Spark. In G. Hedin, editor, Proceedings of the International Conference on Compiler Construction, volume 2622 of LNCS, pages 153--169, Warsaw, Poland, April 2003. Springer.

Digital Library

[25]

}}B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL '06: Proceedings of the ACM Symposium on Principles of Programming Languages, pages 346--358, New York, NY, USA, 2006. ACM.

Digital Library

[26]

}}M. Moir, K. Moore, and D. Nussbaum. The adaptive transactional memory test platform: a tool for experimenting with transactional code for rock (poster). In SPAA '08: Proceedings of the Symposium on Parallelism in Algorithms and Architectures, pages 362--362, 2008.

Digital Library

[27]

}}M. Naik, A. Aiken, and J. Whaley. Effective static race detection for java. In PLDI '06: Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 308--319, New York, NY, USA, 2006. ACM.

Digital Library

[28]

}}R. O'Callahan and J.-D. Choi. Hybrid dynamic data race detection. In PPoPP '03: Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming, pages 167--178, New York, NY, USA, 2003. ACM.

Digital Library

[29]

}}M. C. Rinard and P. C. Diniz. Commutativity analysis: A new analysis technique for parallelizing compilers. ACM Transactions on Programming Languages and Systems, 19(6):1--47, 1997.

Digital Library

[30]

}}S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: a dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997.

Digital Library

[31]

}}D. Shasha, F. Llirbat, E. Simon, and P. Valduriez. Transaction chopping: algorithms and performance studies. ACM Transactions on Database Systems, 20(3):325--363, 1995.

Digital Library

[32]

}}D. Shasha and M. Snir. Efficient and correct execution of parallel programs that share memory. ACM Transactions on Programming Languages and Systems, 10(2):282--312, April 1988.

Digital Library

[33]

}}N. Shavit and D. Touitou. Software transactional memory. In Proceedings of the Symposium on Principles of Distributed Computing, pages 204--213, 1995.

Digital Library

[34]

}}T. Shpeisman, V. Menon, A.-R. Adl-Tabatabai, S. Balensiefer, D. Grossman, R. L. Hudson, K. F. Moore, and B. Saha. Enforcing isolation and ordering in S™. In PLDI '07: Proceedings of the ACM Conference on Programming Language Design and Implementation, pages 78--88, New York, NY, USA, 2007.

Digital Library

[35]

}}G. Upadhyaya, S. P. Midkiff, and V. S. Pai. Using data structure knowledge for efficient lock generation and strong atomicity. In PPoPP '10: Proceedings of the ACM Symposium on Principles and Practice Of Parallel Programming, pages 281--292, 2010.

Digital Library

[36]

}}R. Vallee-Rai, E. Gagnon, L. J. Hendren, P. Lam, P. Pominville, and V. Sundaresan. Optimizing Java bytecode using the Soot framework: Is it feasible? In Proceedings of the International Conference on Compiler Construction (CC '09), pages 18--34, 2000.

Digital Library

[37]

}}M. T. Vechev, E. Yahav, and G. Yorsh. Inferring synchronization under limited observability. In TACAS '09: Proceedings of the International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 139--154, 2009.

Digital Library

[38]

}}M. T. Vechev, E. Yahav, and G. Yorsh. Abstraction-guided synthesis of synchronization. In POPL '10: Proceegings of the ACM Symposium on Principles of Programming Languages, pages 327--338, 2010.

Digital Library

[39]

}}H. Volos, N. Goyal, and M. Swift. Pathological interaction of locks with transactional memory. In Proceedings of the ACM Workshop on Transactional Computing (TRANSACT) '08, 2008. article available at http://www.unine.ch/transact08/papers/Volos-Pathological.pdf. URL last checked on Nov. 19, 2009.

[40]

}}O. Wolfson. The virtues of locking by symbolic names. Journal of Algorithms, 8(4):536--556, 1987.

Digital Library

[41]

}}Y. Zhang, V. C. Sreedhar, W. Zhu, V. Sarkar, and G. R. Gao. Minimum lock assignment: A method for exploiting concurrency among critical sections. In Proceedings of the 21st Annual Workshop on Languages and Compilers for Parallel Computing (LCPC '08), 2008.

Digital Library

[42]

}}L. Ziarek, A. Welc, A.-R. Adl-Tabatabai, V. Menon, T. Shpeisman, and S. Jagannathan. A uniform transactional execution environment for Java. In ECOOP '08: Proceedings of the European Conference on Object-Oriented Programming, pages 129--154, 2008.

Digital Library

Cited By

Lin YDig D(2015)A study and toolkit of CHECK-THEN-ACT idioms of Java concurrent collectionsSoftware Testing, Verification & Reliability10.1002/stvr.156725:4(397-425)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1002/stvr.1567
Chang XDou WGao YWang JWei JHuang TAtlee JBultan TWhittle J(2019)Detecting atomicity violations for event-driven Node.js applicationsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00073(631-642)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00073
Dean DWang PGu XEnck WJin G(2015)Automatic Server Hang Bug DiagnosisProceedings of the 2015 IEEE International Conference on Autonomic Computing10.1109/ICAC.2015.52(127-132)Online publication date: 7-Jul-2015
https://dl.acm.org/doi/10.1109/ICAC.2015.52
Show More Cited By

Index Terms

Automatic atomic region identification in shared memory SPMD 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

Automatic atomic region identification in shared memory SPMD programs
OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications

This paper presents TransFinder, a compile-time tool that automatically determines which statements of an unsynchronized multithreaded program must be enclosed in atomic regions to enforce conflict-serializability. Unlike previous tools, TransFinder ...
Hardware Support for Relaxed Concurrency Control in Transactional Memory
MICRO '43: Proceedings of the 2010 43rd Annual IEEE/ACM International Symposium on Microarchitecture

Today's transactional memory systems implement the two-phase-locking (2PL) algorithm which aborts transactions every time a conflict happens. 2PL is a simple algorithm that provides fast transactional operations. However, it limits concurrency in ...
Unbounded page-based transactional memory
Proceedings of the 2006 ASPLOS Conference

Exploiting thread level parallelism is paramount in the multicore era. Transactions enable programmers to expose such parallelism by greatly simplifying the multi-threaded programming model. Virtualized transactions (unbounded in space and time) are ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 45, Issue 10

OOPSLA '10

October 2010

957 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1932682

Issue’s Table of Contents

OOPSLA '10: Proceedings of the ACM international conference on Object oriented programming systems languages and applications
October 2010
984 pages
ISBN:9781450302036
DOI:10.1145/1869459
General Chairs:
William R. Cook
University of Texas at Austin
,
Siobhán Clarke
Trinity College Dublin
,
Program Chairs:
Martin Rinard
MIT
,
Kevin J. Sullivan
University of Virginia
,
Daniel H. Steinberg
Dim Sum Thinking Inc.

Copyright © 2010 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2010

Published in SIGPLAN Volume 45, Issue 10

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
255
Total Downloads

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

Reflects downloads up to 11 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lin YDig D(2015)A study and toolkit of CHECK-THEN-ACT idioms of Java concurrent collectionsSoftware Testing, Verification & Reliability10.1002/stvr.156725:4(397-425)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1002/stvr.1567
Chang XDou WGao YWang JWei JHuang TAtlee JBultan TWhittle J(2019)Detecting atomicity violations for event-driven Node.js applicationsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00073(631-642)Online publication date: 25-May-2019
https://dl.acm.org/doi/10.1109/ICSE.2019.00073
Dean DWang PGu XEnck WJin G(2015)Automatic Server Hang Bug DiagnosisProceedings of the 2015 IEEE International Conference on Autonomic Computing10.1109/ICAC.2015.52(127-132)Online publication date: 7-Jul-2015
https://dl.acm.org/doi/10.1109/ICAC.2015.52
Deng DJin Gde Kruijf MLi ALiblit BLu SQi SRen JSankaralingam KSong LWu YZhang MZhang WZheng W(2015)Fixing, preventing, and recovering from concurrency bugsScience China Information Sciences10.1007/s11432-015-5315-958:5(1-18)Online publication date: 10-Apr-2015
https://doi.org/10.1007/s11432-015-5315-9
Lin YDig D(2015)A study and toolkit of CHECK-THEN-ACT idioms of Java concurrent collectionsSoftware Testing, Verification & Reliability10.1002/stvr.156725:4(397-425)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1002/stvr.1567
Zhang Wde Kruijf MLi ALu SSankaralingam K(2013)ConAirACM SIGPLAN Notices10.1145/2499368.245112948:4(113-126)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2499368.2451129
Liu PDolby JZhang CMeyer BBaresi LMezini M(2013)Finding incorrect compositions of atomicityProceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering10.1145/2491411.2491435(158-168)Online publication date: 18-Aug-2013
https://dl.acm.org/doi/10.1145/2491411.2491435
Zhang Wde Kruijf MLi ALu SSankaralingam K(2013)ConAirACM SIGARCH Computer Architecture News10.1145/2490301.245112941:1(113-126)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2490301.2451129
Zhang Wde Kruijf MLi ALu SSankaralingam KSarkar VBodik R(2013)ConAirProceedings of the eighteenth international conference on Architectural support for programming languages and operating systems10.1145/2451116.2451129(113-126)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1145/2451116.2451129
Jin GZhang WDeng DLiblit BLu SVahdat AThekkath C(2012)Automated concurrency-bug fixingProceedings of the 10th USENIX conference on Operating Systems Design and Implementation10.5555/2387880.2387902(221-236)Online publication date: 8-Oct-2012
https://dl.acm.org/doi/10.5555/2387880.2387902
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.

Figures

Tables

Media

View Issue’s Table of Contents