research-article

JANUS: exploiting parallelism via hindsight

Authors:

Roman Manevich,

Mooly SagivAuthors Info & Claims

PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

Pages 145 - 156

https://doi.org/10.1145/2254064.2254083

Published: 11 June 2012 Publication History

Abstract

This paper addresses the problem of reducing unnecessary conflicts in optimistic synchronization. Optimistic synchronization must ensure that any two concurrently executing transactions that commit are properly synchronized. Conflict detection is an approximate check for this condition. For efficiency, the traditional approach to conflict detection conservatively checks that the memory locations mutually accessed by two concurrent transactions are accessed only for reading.

We present JANUS, a parallelization system that performs conflict detection by considering sequences of operations and their composite effect on the system's state. This is done efficiently, such that the runtime overhead due to conflict detection is on a par with that of write-conflict-based detection. In certain common scenarios, this mode of refinement dramatically improves the precision of conflict detection, thereby reducing the number of false conflicts.

Our empirical evaluation of JANUS shows that this precision gain reduces the abort rate by an order of magnitude (22x on average), and achieves a speedup of up to 2.5x, on a suite of real-world benchmarks where no parallelism is exploited by the standard approach.

References

[1]

The chord analysis framework. http://code.google.com/p/jchord/.

[2]

The jfilesync utility. http://jfilesync.sourceforge.net.

[3]

The jgrapht java graph library. http://www.jgrapht.org.

[4]

Pmd java source code scanner. http://pmd.sourceforge.net.

[5]

The sat4j sat solver. http://www.sat4j.org/.

[6]

The sourceforge code repository. http://sourceforge.net/.

[7]

The weka machine-learning library. http://weka.sourceforge.net.

[8]

A. Bernstein. Analysis of programs for parallel processing. IEEE Transactions on Electronic Computers, pages 757--762, 1966.

[9]

S. Chiba and M. Nishizawa. An easy-to-use toolkit for efficient java bytecode translators. In Proceedings of the 2nd international conference on Generative programming and component engineering, pages 364--376, 2003.

Digital Library

[10]

J. R. Driscoll, N. Sarnak, D. D. Sleator, and R. E. Tarjan. Making data structures persistent. J. Comput. Syst. Sci., 38:86--124, 1989.

Digital Library

[11]

P. Felber, V. Gramoli, and R. Guerraoui. Elastic transactions. In DISC, pages 93--107, 2009.

Digital Library

[12]

T. Harris, S. Marlow, S. Peyton-Jones, and M. Herlihy. Composable memory transactions. In Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, pages 48--60, 2005.

Digital Library

[13]

T. Harris and S. Stipic. Abstract nested transactions. The 2nd ACM SIGPLAN Workshop on Transactional Computing, 2007.

[14]

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

Digital Library

[15]

M. Herlihy, V. Luchangco, P. A. Martin, and M. Moir. Nonblocking memory management support for dynamic-sized data structures. ACM Trans. Comput. Syst., 23(2):146--196, 2005.

Digital Library

[16]

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

Digital Library

[17]

E. Koskinen and M. Herlihy. Checkpoints and continuations instead of nested transactions. In SPAA, pages 160--168, 2008.

Digital Library

[18]

E. Koskinen, M. J. Parkinson, and M. Herlihy. Coarse-grained transactions. In POPL, pages 19--30, 2010.

Digital Library

[19]

M. Kulkarni, D. Nguyen, D. Prountzos, X. Sui, and K. Pingali. Exploiting the commutativity lattice. In PLDI, 2011.

Digital Library

[20]

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

Digital Library

[21]

H. E. Ramadan, I. Roy, M. Herlihy, and E. Witchel. Committing conflicting transactions in an stm. In PPOPP, pages 163--172, 2009.

Digital Library

[22]

O. Tripp, R. Manevich, J. Field, and M. Sagiv. JANUS: Exploiting parallelism via hindsight. Technical report, Tel Aviv University, 2012.

[23]

O. Tripp, G. Yorsh, J. Field, and M. Sagiv. Hawkeye: effective discovery of dataflow impediments to parallelization. In OOPSLA, pages 207--224, 2011.

Digital Library

[24]

A. Udupa, K. Rajan, and W. Thies. Alter: exploiting breakable dependences for parallelization. In Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation, pages 480--491, 2011.

Digital Library

[25]

J. Whaley. Joeq: A virtual machine and compiler infrastructure. Sci. Comput. Program., 57:339--356, 2005.

Digital Library

Cited By

Ranjan NShang ZKrishnan SElmore A(2021)Version Reconciliation for Collaborative DatabasesProceedings of the ACM Symposium on Cloud Computing10.1145/3472883.3486980(473-488)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3472883.3486980
Albert EGrossman SRinetzky NRodríguez-Núñez CRubio ASagiv M(2020)Taming callbacks for smart contract modularityProceedings of the ACM on Programming Languages10.1145/34282774:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428277
Bansal KKoskinen ETripp O(2020)Synthesizing Precise and Useful Commutativity ConditionsJournal of Automated Reasoning10.1007/s10817-020-09573-wOnline publication date: 29-Aug-2020
https://doi.org/10.1007/s10817-020-09573-w
Show More Cited By

Index Terms

JANUS: exploiting parallelism via hindsight
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

JANUS: exploiting parallelism via hindsight
PLDI '12

This paper addresses the problem of reducing unnecessary conflicts in optimistic synchronization. Optimistic synchronization must ensure that any two concurrently executing transactions that commit are properly synchronized. Conflict detection is an ...
Transactional Read-Modify-Write Without Aborts

Language-level transactions are said to provide “atomicity,” implying that the order of operations within a transaction should be invisible to concurrent transactions and thus that independent operations within a transaction should be safe to execute in ...
On the impact of serializing contention management on STM performance

Transactional memory (TM) is an emerging concurrent programming abstraction. Numerous software-based transactional memory (STM) implementations have been developed in recent years. STM implementations must guarantee transaction atomicity and isolation. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation

June 2012

572 pages

ISBN:9781450312059

DOI:10.1145/2254064

General Chairs:
Jan Vitek
Purdue University
,
Haibo Lin
Microsoft China
,
Program Chair:
Frank Tip
IBM T.J. Watson Research Center

ACM SIGPLAN Notices Volume 47, Issue 6
PLDI '12
June 2012
534 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2345156
Issue’s Table of Contents

Copyright © 2012 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: 11 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PLDI '12

Sponsor:

SIGPLAN

PLDI '12: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 11 - 16, 2012

Beijing, China

Acceptance Rates

PLDI '12 Paper Acceptance Rate 48 of 255 submissions, 19%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
446
Total Downloads

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

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ranjan NShang ZKrishnan SElmore A(2021)Version Reconciliation for Collaborative DatabasesProceedings of the ACM Symposium on Cloud Computing10.1145/3472883.3486980(473-488)Online publication date: 1-Nov-2021
https://dl.acm.org/doi/10.1145/3472883.3486980
Albert EGrossman SRinetzky NRodríguez-Núñez CRubio ASagiv M(2020)Taming callbacks for smart contract modularityProceedings of the ACM on Programming Languages10.1145/34282774:OOPSLA(1-30)Online publication date: 13-Nov-2020
https://dl.acm.org/doi/10.1145/3428277
Bansal KKoskinen ETripp O(2020)Synthesizing Precise and Useful Commutativity ConditionsJournal of Automated Reasoning10.1007/s10817-020-09573-wOnline publication date: 29-Aug-2020
https://doi.org/10.1007/s10817-020-09573-w
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
Gramoli VGuerraoui R(2014)Reusable Concurrent Data TypesProceedings of the 28th European Conference on ECOOP 2014 --- Object-Oriented Programming - Volume 858610.1007/978-3-662-44202-9_8(182-206)Online publication date: 1-Aug-2014
https://dl.acm.org/doi/10.1007/978-3-662-44202-9_8
Tripp OKoskinen ESagiv M(2013)Turning nondeterminism into parallelismACM SIGPLAN Notices10.1145/2544173.250953348:10(589-604)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2544173.2509533
Tripp OKoskinen ESagiv MHosking AEugster PLopes C(2013)Turning nondeterminism into parallelismProceedings of the 2013 ACM SIGPLAN international conference on Object oriented programming systems languages & applications10.1145/2509136.2509533(589-604)Online publication date: 29-Oct-2013
https://dl.acm.org/doi/10.1145/2509136.2509533
Tripp ORinetzky NMeyer BBaresi LMezini M(2013)Tightfit: adaptive parallelization with foresightProceedings of the 2013 9th Joint Meeting on Foundations of Software Engineering10.1145/2491411.2491443(169-179)Online publication date: 18-Aug-2013
https://dl.acm.org/doi/10.1145/2491411.2491443
Koskinen EBansal K(2021)Decomposing Data Structure Commutativity Proofs with $$m\!n$$-DifferencingVerification, Model Checking, and Abstract Interpretation10.1007/978-3-030-67067-2_5(81-103)Online publication date: 12-Jan-2021
https://doi.org/10.1007/978-3-030-67067-2_5
Show More Cited By

View Options

Get Access

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