More Web Proxy on the site http://driver.im/

research-article

Using data structure knowledge for efficient lock generation and strong atomicity

Authors:

Gautam Upadhyaya,

Samuel P. Midkiff,

Vijay S. PaiAuthors Info & Claims

PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Pages 281 - 292

https://doi.org/10.1145/1693453.1693490

Published: 09 January 2010 Publication History

Abstract

To achieve high-performance on multicore systems, sharedmemory parallel languages must efficiently implement atomic operations. The commonly used and studied paradigms for atomicity are fine-grained locking, which is both difficult to program and error-prone; optimistic software transactions, which require substantial overhead to detect and recover from atomicity violations; and compiler-generation of locks from programmer-specified atomic sections, which leads to serialization whenever imprecise pointer analysis suggests the mere possibility of a conflicting operation. This paper presents a new strategy for compiler-generated locking that uses data structure knowledge to facilitate more precise alias and lock generation analyses and reduce unnecessary serialization. Implementing and evaluating these ideas in the Java language shows that the new strategy achieves eight-thread speedups of 0.83 to 5.9 for the five STAMP benchmarks studied, outperforming software transactions on all but one benchmark, and nearly matching programmer-specified fine-grained locks on all but one benchmark. The results also indicate that compiler knowledge of data structures improves the effectiveness of compiler analysis, boosting eight-thread performance by up to 300%. Further, the new analysis allows for software support of strong atomicity with less than 1% overhead for two benchmarks and less than 20% for three others.The strategy also nearly matches the performance of programmer-specified fine-grained locks for the SPECjbb2000 benchmark, which has traditionally not been amenable to static analyses.

References

[1]

C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: preventing data races and deadlocks. In OOPSLA '02: Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, pages 211--230, New York, NY, USA, 2002. ACM.

Digital Library

[2]

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.

[3]

B. D. Carlstrom, A. McDonald, H. Chafi, J. Chung, C. C. Minh, C. Kozyrakis, and K. Olukotun. The Atomos transactional programming language. SIGPLAN Not., 41(6):1--13, 2006.

Digital Library

[4]

S. Cherem, T. M. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. In R. Gupta and S. P. Amarasinghe, editors, Proceedings of the 2008 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI '08), pages 304--315. ACM, 2008.

Digital Library

[5]

D. Dice, O. Shalev, and N. Shavit. Transactional Locking II. In 20th International Symposium on Distributed Computing, pages 194--208, 2006.

Digital Library

[6]

M. Emmi, J. S. Fischer, R. Jhala, and R. Majumdar. Lock allocation. In POPL '07: Proceedings of the 34th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 291--296, New York, NY, USA, 2007. ACM.

Digital Library

[7]

J. N. Gray, R. A. Lorie, G. R. Putzolu, and I. L. Traiger. Granularity of locks and degrees of consistency in a shared data base. In Readings in database systems (2nd ed.), pages 181--208. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1994.

Digital Library

[8]

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

Digital Library

[9]

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

[10]

M. Herlihy and E. Koskinen. Transactional boosting: a methodology for highly-concurrent transactional objects. In PPoPP '08: Proceedings of the 13th ACM SIGPLAN Symposium on Principles and practice of parallel programming, pages 207--216, New York, NY, USA, 2008. ACM.

Digital Library

[11]

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

Digital Library

[12]

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.

[13]

O. S. Hofmann, C. J. Rossbach, and E. Witchel. Maximum benefit from a minimal htm. In ASPLOS '09: Proceeding of the 14th international conference on Architectural support for programming languages and operating systems, pages 145--156, New York, NY, USA, 2009. ACM.

Digital Library

[14]

Jikes RVM web page on magic functions. http://jikesrvm.org/Magic, last accessed Nov. 12, 2008.

[15]

D. Lea. Concurrent Programming in Java: Design Principles and Patterns. Addison-Wesley, second edition, November 1999.

Digital Library

[16]

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

Digital Library

[17]

B. McCloskey, F. Zhou, D. Gay, and E. Brewer. Autolocker: synchronization inference for atomic sections. In POPL '06: Conference record of the 33rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 346--358, New York, NY, USA, 2006. ACM.

Digital Library

[18]

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 twentieth annual symposium on Parallelism in algorithms and architectures, pages 362--362, 2008.

Digital Library

[19]

F. T. Schneider, V. Menon, T. Shpeisman, and A.-R. Adl-Tabatabai. Dynamic optimization for efficient strong atomicity. SIGPLAN Not., 43(10):181--194, 2008.

Digital Library

[20]

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

Digital Library

[21]

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 STM. In PLDI '07: Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation, pages 78--88, New York, NY, USA, 2007.

Digital Library

[22]

The Standard Performance Evaluation Corporation. SPECjbb2000 Benchmark. At http://www.spec.org/jbb2000, 2000.

[23]

P. Wu, S. P. Midkiff, J. E. Moreira, and M. Gupta. Efficient support for complex numbers in Java. In Proceedings of the 1999 ACM Java Grande Conference, pages 109--118, 1999. IBM Research Report RC21393.

Digital Library

[24]

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 21st Annual Workshop on Languages and Compilers for Parallel Computing (LCPC '08), 2008.

Digital Library

[25]

J. Zhu and S. Calman. Symbolic pointer analysis revisited. In PLDI '04: Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, pages 145--157, New York, NY, USA, 2004. ACM.

Digital Library

Cited By

Mururu GGavrilovska APande S(2019)Quantifying and Reducing Execution Variance in STM via Model Driven Commit Optimization2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2019.8661179(109-121)Online publication date: Feb-2019
https://doi.org/10.1109/CGO.2019.8661179
Liu PZhang CJalote PBriand LHoek A(2014)Unleashing concurrency for irregular data structuresProceedings of the 36th International Conference on Software Engineering10.1145/2568225.2568277(480-490)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2568225.2568277
Liu PZhang CGlinz MMurphy GPezzè M(2012)Axis: automatically fixing atomicity violations through solving control constraintsProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337259(299-309)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337259
Show More Cited By

Index Terms

Using data structure knowledge for efficient lock generation and strong atomicity
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

Using data structure knowledge for efficient lock generation and strong atomicity
PPoPP '10

To achieve high-performance on multicore systems, sharedmemory parallel languages must efficiently implement atomic operations. The commonly used and studied paradigms for atomicity are fine-grained locking, which is both difficult to program and error-...
An effective hybrid transactional memory system with strong isolation guarantees
ISCA '07: Proceedings of the 34th annual international symposium on Computer architecture

We propose signature-accelerated transactional memory (SigTM), ahybrid TM system that reduces the overhead of software transactions. SigTM uses hardware signatures to track the read-set and write-set forpending transactions and perform conflict ...
An effective hybrid transactional memory system with strong isolation guarantees

We propose signature-accelerated transactional memory (SigTM), ahybrid TM system that reduces the overhead of software transactions. SigTM uses hardware signatures to track the read-set and write-set forpending transactions and perform conflict ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

January 2010

372 pages

ISBN:9781605588773

DOI:10.1145/1693453

General Chairs:
R. Govindarajan
Indian Institute of Science
,
David Padua
UIUC
,
Program Chair:
Mary Hall
University of Utah

ACM SIGPLAN Notices Volume 45, Issue 5
PPoPP '10
May 2010
346 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1837853
Issue’s Table of Contents

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 January 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PPoPP '10

Sponsor:

SIGPLAN

PPoPP '10: ACM SIGPLAN Principles and Practice of Parallel Computing

January 9 - 14, 2010

Bangalore, India

Acceptance Rates

Overall Acceptance Rate 230 of 1,014 submissions, 23%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
523
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)2

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mururu GGavrilovska APande S(2019)Quantifying and Reducing Execution Variance in STM via Model Driven Commit Optimization2019 IEEE/ACM International Symposium on Code Generation and Optimization (CGO)10.1109/CGO.2019.8661179(109-121)Online publication date: Feb-2019
https://doi.org/10.1109/CGO.2019.8661179
Liu PZhang CJalote PBriand LHoek A(2014)Unleashing concurrency for irregular data structuresProceedings of the 36th International Conference on Software Engineering10.1145/2568225.2568277(480-490)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2568225.2568277
Liu PZhang CGlinz MMurphy GPezzè M(2012)Axis: automatically fixing atomicity violations through solving control constraintsProceedings of the 34th International Conference on Software Engineering10.5555/2337223.2337259(299-309)Online publication date: 2-Jun-2012
https://dl.acm.org/doi/10.5555/2337223.2337259
Fan XJin HZhu LLiao XYe CTu XGuo MHuang Z(2012)Function flowProceedings of the 2012 International Workshop on Programming Models and Applications for Multicores and Manycores10.1145/2141702.2141711(74-82)Online publication date: 26-Feb-2012
https://dl.acm.org/doi/10.1145/2141702.2141711
Liu PZhang C(2012)Axis: Automatically fixing atomicity violations through solving control constraints2012 34th International Conference on Software Engineering (ICSE)10.1109/ICSE.2012.6227184(299-309)Online publication date: Jun-2012
https://doi.org/10.1109/ICSE.2012.6227184
Upadhyaya GMidkiff SPai V(2010)Automatic atomic region identification in shared memory SPMD programsACM SIGPLAN Notices10.1145/1932682.186951345:10(652-670)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1932682.1869513
Upadhyaya GMidkiff SPai VCook WClarke SRinard MSullivan KSteinberg D(2010)Automatic atomic region identification in shared memory SPMD programsProceedings of the ACM international conference on Object oriented programming systems languages and applications10.1145/1869459.1869513(652-670)Online publication date: 17-Oct-2010
https://dl.acm.org/doi/10.1145/1869459.1869513
Midkiff S(2012)Automatic Parallelization: An Overview of Fundamental Compiler TechniquesSynthesis Lectures on Computer Architecture10.2200/S00340ED1V01Y201201CAC0197:1(1-169)Online publication date: 28-Jan-2012
https://doi.org/10.2200/S00340ED1V01Y201201CAC019
Mannarswamy SGovindarajan R(2011)Variable Granularity Access Tracking Scheme for Improving the Performance of Software Transactional MemoryProceedings of the 2011 IEEE International Parallel & Distributed Processing Symposium10.1109/IPDPS.2011.51(455-466)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.1109/IPDPS.2011.51

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