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

research-article

Compiler aided selective lock assignment for improving the performance of software transactional memory

Authors:

Sandya Mannarswamy,

Dhruva R. Chakrabarti,

Sujoy SaraswatiAuthors Info & Claims

ACM SIGPLAN Notices, Volume 45, Issue 5

Pages 37 - 46

https://doi.org/10.1145/1837853.1693460

Published: 09 January 2010 Publication History

Abstract

Atomic sections have been recently introduced as a language construct to improve the programmability of concurrent software. They simplify programming by not requiring the explicit specification of locks for shared data. Typically atomic sections are supported in software either through the use of optimistic concurrency by using transactional memory or through the use of pessimistic concurrency using compiler-assigned locks. As a software transactional memory (STM) system does not take advantage of the specific memory access patterns of an application it often suffers from false conflicts and high validation overheads. On the other hand, the compiler usually ends up assigning coarse grain locks as it relies on whole program points-to analysis which is conservative by nature. This adversely affects performance by limiting concurrency. In order to mitigate the disadvantages associated with STM's lock assignment scheme, we propose a hybrid approach which combines STM's lock assignment with a compiler aided selective lock assignment scheme (referred to as SCLA-STM). SCLA-STM overcomes the inefficiencies associated with a purely compile-time lock assignment approach by (i) using the underlying STM for shared variables where only a conservative analysis is possible by the compiler (e.g., in the presence of may-alias points to information) and (ii) being selective about the shared data chosen for the compiler-aided lock assignment. We describe our prototype SCLA-STM scheme implemented in the hp-ux IA-64 C/C++ compiler, using TL2 as our STM implementation. We show that SCLA-STM improves application performance for certain STAMP benchmarks from 1.68% to 37.13%.

References

[1]

Y. Zhang, V. Sreedhar, W. Zhu, V. Sarkar, and G. Gao. Optimized lock assignment and allocation: A method for exploiting concurrency among critical sections. TR-CAPSL-TM-065, University of Delaware, Newark, DE, 2007.

[2]

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

Digital Library

[3]

S. Cherem, T. Chilimbi, and S. Gulwani. Inferring locks for atomic sections. Technical Report MSR-TR-2007-111, MSR, August 2007.

[4]

M. Hicks, J. Foster, and P. Pratikakis. Lock inference for atomic sections. In TRANSACT'06: Proceedings of the 1st ACM SIGPLAN Workshop on Languages, Compilers, and Hardware Support for Transactional Computing, 2006.

[5]

R. L. Halpert, C. J. F. Pickett, and C. Verbrugge. Component-based lock allocation. In Proceedings of the International Conference on Parallel Architectures and Compilation Techniques, September 2007.

Digital Library

[6]

Y. Zhang, V.C. Sreedhar, W. Zhu, V. Sarkar, and G. R. Gao. 2008. Minimum Lock Assignment: A Method for Exploiting Concurrency among Critical Sections. In Languages and Compilers For Parallel Computing: 21th international Workshop, LCPC 2008, Edmonton, Canada, July 31 - August 2, 2008.

Digital Library

[7]

M. Herlihy and J. E. 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, May 1993.

Digital Library

[8]

N. Shavit and D. Touitou. Software transactional memory. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, Aug 1995.

Digital Library

[9]

M. Herlihy, V. Luchangco, M. Moir, and W. N.Scherer, III. Software transactional memory for dynamic-sized data structures. In PODC '03: Proc. 22nd ACM Symposium on Principles of Distributed Computing, July 2003.

Digital Library

[10]

M.F. Spear, V.J. Marathe, W.N. Scherer III, and M.L. Scott, "Conflict Detection and Validation Strategies for Software Transactional Memory," Proc. of the 20th Int'l Symp. on Distributed Computing, Stockholm, Sweden, Sept. 2006.

Digital Library

[11]

D. Dice, O. Shalev, and N. Shavit. Transactional locking II. In Proceedings of the 20th International Symposium on Distributed Computing (DISC), Stockholm, Sweeden, September 2006.

Digital Library

[12]

P. Felber, C. Fetzer, and T. Riegel,. 2008. Dynamic performance tuning of word-based software transactional memory. In Proceedings of the 13th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (Salt Lake City, UT, USA, February 20-23, 2008). PPoPP '08. ACM, New York, NY, 237--246.

Digital Library

[13]

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 Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, pages 26--37, NY, USA, 2006.

Digital Library

[14]

Zilles and R. Rajwar. Transactional Memory and the Birthday Paradox. In Proceedings of the Nineteenth ACM Symposium on Parallel Algorithms and Architectures, June 2007.

Digital Library

[15]

Zilles, and R. Rajwar,. 2007. Implications of False Conflict Rate Trends for Robust Software Transactional Memory. In Proceedings of the 2007 IEEE 10th international Symposium on Workload Characterization - Volume 00 (September 27-29, 2007). IISWC. IEEE Computer Society, Washington, DC, 15--24.

Digital Library

[16]

R. Yoo, Y. Ni, A. Welc, B. Saha, A. Adl--Tabatabai, and H.S. Lee. 2008. Kicking the tires of software transactional memory: why the going gets tough. In Proceedings of the Symposium on Parallelism in Algorithms and Architectures (Munich, Germany, June 14-16, 2008). SPAA '08. ACM, NY, 265--274.

Digital Library

[17]

C. Cascaval, C.Blundell, M. Michael, H. W. Cain, P. Wu, S. Chiras, and S. Chatterjee. 2008. Software Transactional Memory: Why Is It Only a Research Toy?. Queue 6, 5 (Sep. 2008), 46--58.

Digital Library

[18]

B. Steensgaard. Points-to analysis in almost linear time. In Proceedings of the ACM Symposium on the Principles of Programming Languages, St. Petersburg Beach, FL, Jan 1996.

Digital Library

[19]

M. Burke and R. Cytron. 1986. Interprocedural dependence analysis and parallelization. SIGPLAN Not. 21, 7 (Jul. 1986), 162--175.

Digital Library

[20]

C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. In IISWC '08: Proc. IEEE International Symposium on Workload Characterization, pages 35--46, Sep 2008.

[21]

G. Chaitin. 2004. Register allocation and spilling via graph coloring. SIGPLAN Not. 39, 4 (Apr. 2004), 66--74.

Digital Library

[22]

T. Riegel C. Fetzer, and P. Felber. 2008. Automatic data partitioning in software transactional memories. In Proceedings of the Twentieth Annual Symposium on Parallelism in Algorithms and Architectures (Munich, Germany, June 14-16, 2008). SPAA '08. ACM, New York, NY, 152--159.

Digital Library

[23]

T. Harris and K. Fraser. 2003. Language support for lightweight transactions. In Proceedings of the ACM SIGPLAN Conference on Object--Oriented Programing, Systems, Languages, and Applications (Anaheim, California, USA, October 26-30, 2003). OOPSLA '03. ACM, New York, NY, 388--402.

Digital Library

[24]

R. Hundt, "HP Caliper: A framework for performance analysis tools," IEEE Concurrency, vol. 8, no. 4, pp. 64--71, 2000.

Digital Library

[25]

R. Hundt, S. Mannarswamy, and D. Chakrabarti, "Practical structure layout optimization and advice," in Proceedings of the International Symposium on Code Generation and Optimization, (Washington, DC, USA), pp. 233--244, IEEE Computer Society, 2006.

Digital Library

[26]

D. Dice and N. Shavit. 2007. Understanding Tradeoffs in Software Transactional Memory. In Proceedings of the international Symposium on Code Generation and Optimization (March 11-14, 2007). Washington, DC, 21--33.

Digital Library

[27]

S. Moon, X. D. Li, R. Hundt, D. R. Chakrabarti, L. A. Lozano, U. Srinivasan, and S.-M. Liu, "Syzygy - a framework for scalable cross-module ipo," in CGO '04: Proceedings of the international symposium on Code generation and optimization, (Washington, DC, USA), p. 65, IEEE Computer Society, 2004.

Digital Library

[28]

Manuvir Das, Unification-based pointer analysis with directional assignments. In Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation, pages 35--46, Vancouver, British Columbia, June 18-21, 2000.

Digital Library

Cited By

Diegues NRomano PRodrigues LAmaral JTorrellas J(2014)Virtues and limitations of commodity hardware transactional memoryProceedings of the 23rd international conference on Parallel architectures and compilation10.1145/2628071.2628080(3-14)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2628071.2628080
Diegues NRomano PRodrigues LAmaral JTorrellas J(2014)Virtues and limitations of commodity hardware transactional memoryProceedings of the 23rd international conference on Parallel architectures and compilation10.1145/2628071.2628080(3-14)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2628071.2628080
Sreeram JPande S(2012)Hybrid TransactionsProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.109(1192-1203)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.109
Show More Cited By

Index Terms

Compiler aided selective lock assignment for improving the performance of software transactional memory
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

Compiler aided selective lock assignment for improving the performance of software transactional memory
PPoPP '10: Proceedings of the 15th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Atomic sections have been recently introduced as a language construct to improve the programmability of concurrent software. They simplify programming by not requiring the explicit specification of locks for shared data. Typically atomic sections are ...
Improving performance of software transactional memory through contention locality

In this paper, we introduce contention locality in Transactional Memory (TM) which describes the likelihood that a previously aborted transaction conflicts again in the future. We find that conflicts are highly predictable in TMs and we propose two ...
An efficient lock-aware transactional memory implementation
ICOOOLPS '09: Proceedings of the 4th workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages and Programming Systems

Transactional memory (TM) is an emerging concurrency control mechanism that provides a simple and composable programming model. Unfortunately, transactions violate the semantics of mutual exclusion locks when they execute concurrently. Due to the ...

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 5

PPoPP '10

May 2010

346 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/1837853

Issue’s Table of Contents

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

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: 09 January 2010

Published in SIGPLAN Volume 45, Issue 5

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
466
Total Downloads

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

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Diegues NRomano PRodrigues LAmaral JTorrellas J(2014)Virtues and limitations of commodity hardware transactional memoryProceedings of the 23rd international conference on Parallel architectures and compilation10.1145/2628071.2628080(3-14)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2628071.2628080
Diegues NRomano PRodrigues LAmaral JTorrellas J(2014)Virtues and limitations of commodity hardware transactional memoryProceedings of the 23rd international conference on Parallel architectures and compilation10.1145/2628071.2628080(3-14)Online publication date: 24-Aug-2014
https://dl.acm.org/doi/10.1145/2628071.2628080
Sreeram JPande S(2012)Hybrid TransactionsProceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium10.1109/IPDPS.2012.109(1192-1203)Online publication date: 21-May-2012
https://dl.acm.org/doi/10.1109/IPDPS.2012.109
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
Mannarswamy SGovindarajan R(2010)Handling Conflicts with Compiler's Help in Software Transactional Memory SystemsProceedings of the 2010 39th International Conference on Parallel Processing10.1109/ICPP.2010.56(482-491)Online publication date: 13-Sep-2010
https://dl.acm.org/doi/10.1109/ICPP.2010.56

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 Issue’s Table of Contents