research-article

The tasks with effects model for safe concurrency

Authors:

Stephen T. Heumann,

Vikram S. Adve,

Shengjie WangAuthors Info & Claims

ACM SIGPLAN Notices, Volume 48, Issue 8

Pages 239 - 250

https://doi.org/10.1145/2517327.2442540

Published: 23 February 2013 Publication History

Abstract

Today's widely-used concurrent programming models either provide weak safety guarantees, making it easy to write code with subtle errors, or are limited in the class of programs that they can express. We propose a new concurrent programming model based on tasks with effects that offers strong safety guarantees while still providing the flexibility needed to support the many ways that concurrency is used in complex applications. The core unit of work in our model is a dynamically-created task. The model's key feature is that each task has programmer-specified effects, and a run-time scheduler is used to ensure that two tasks are run concurrently only if they have non-interfering effects. Through the combination of statically verifying the declared effects of tasks and using an effect-aware run-time scheduler, our model is able to guarantee strong safety properties, including data race freedom and atomicity. It is also possible to use our model to write programs and computations that can be statically proven to behave deterministically. We describe the tasks with effects programming model and provide a formal dynamic semantics for it. We also describe our implementation of this model in an extended version of Java and evaluate its use in several programs exhibiting various patterns of concurrency.

References

[1]

M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of transactional memory and automatic mutual exclusion. In POPL, 2008.

Digital Library

[2]

S. V. Adve and K. Gharachorloo. Shared memory consistency models: A tutorial. IEEE Comp., Special Issue on Shared-Mem. Multiproc., pages 66--76, December 1996.

Digital Library

[3]

G. Agha. Actors: A model of concurrent computation in distributed systems. MIT Press, 1986.

Digital Library

[4]

M. D. Allen, S. Sridharan, and G. S. Sohi. Serialization sets: A dynamic dependence-based parallel execution model. In PPOPP, 2009.

Digital Library

[5]

Z. Anderson, D. Gay, R. Ennals, and E. Brewer. SharC: Checking data sharing strategies for multithreaded C. In PLDI, 2008.

Digital Library

[6]

Apple. Concurrency Programming Guide. http://developer.apple.com/library/mac/documentation/General/Conceptual/ConcurrencyProgrammingGuide/, Dec. 2012.

[7]

M. Bauer, S. Treichler, E. Slaughter, and A. Aiken. Legion: Expressing locality and independence with logical regions. In SC'12, 2012.

Digital Library

[8]

T. Bergan, O. Anderson, J. Devietti, L. Ceze, and D. Grossman. Core-Det: A compiler and runtime system for deterministic multithreaded execution. In ASPLOS, 2010.

Digital Library

[9]

E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe multithreaded programming for C/C++. In OOPSLA, 2009.

Digital Library

[10]

M. J. Best, S. Mottishaw, C. Mustard, M. Roth, A. Fedorova, and A. Brownsword. Synchronization via scheduling: Techniques for efficiently managing shared state. In PLDI, 2011.

Digital Library

[11]

R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An efficient multithreaded runtime system. In PPOPP, 1995.

Digital Library

[12]

R. L. Bocchino and V. S. Adve. Types, regions, and effects for safe programming with object-oriented parallel frameworks. In ECOOP, 2011.

Digital Library

[13]

R. L. Bocchino, V. S. Adve, D. Dig, S. V. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A type and effect system for Deterministic Parallel Java. In OOPSLA, 2009.

Digital Library

[14]

R. L. Bocchino, S. Heumann, N. Honarmand, S. V. Adve, V. S. Adve, A. Welc, and T. Shpeisman. Safe nondeterminism in a deterministicby-default parallel language. In POPL, 2011.

Digital Library

[15]

J. Canny. A computational approach to edge detection. IEEE Trans. Pattern Analysis and Machine Intelligence, 8(6):679--698, June 1986.

Digital Library

[16]

J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: Deterministic shared memory multiprocessing. In ASPLOS, 2009.

Digital Library

[17]

Y. h. Eom, S. Yang, J. C. Jenista, and B. Demsky. DOJ: Dynamically parallelizing object-oriented programs. In PPoPP, 2012.

Digital Library

[18]

C. Flanagan and S. N. Freund. Type-based race detection for Java. In PLDI, 2000.

Digital Library

[19]

T. Harris, J. Larus, and R. Rajwar. Transactional Memory, 2nd Edition (Synthesis Lectures on Comp. Arch.). Morgan & Claypool, 2010.

Digital Library

[20]

S. Heumann and V. Adve. Disciplined concurrent programming using tasks with effects. In HotPar, 2012.

Digital Library

[21]

S. Heumann and V. Adve. Tasks with effects: A model for disciplined concurrent programming. In WoDet, 2012.

[22]

Intel. Intel Thread Building Blocks Reference Manual. http://software.intel.com/sites/products/documentation/hpc/tbb/referencev2.pdf, Aug. 2011.

[23]

J. C. Jenista, Y. h. Eom, and B. C. Demsky. OoOJava: software out-of-order execution. In PPOPP, 2011.

Digital Library

[24]

R. K. Karmani, A. Shali, and G. Agha. Actor frameworks for the JVM platform: A comparative analysis. In Principles and Practice of Programming in Java (PPPJ), 2009.

Digital Library

[25]

C. Ke, L. Liu, C. Zhang, T. Bai, B. Jacobs, and C. Ding. Safe parallel programming using dynamic dependence hints. In OOPSLA, 2011.

Digital Library

[26]

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

Digital Library

[27]

Y. Long, S. L. Mooney, T. Sondag, and H. Rajan. Implicit invocation meets safe, implicit concurrency. In Generative Programming and Component Engineering (GPCE), 2010.

Digital Library

[28]

R. Lublinerman, J. Zhao, Z. Budimlić, S. Chaudhuri, and V. Sarkar. Delegated isolation. In OOPSLA, 2011.

Digital Library

[29]

Microsoft. Axum. http://msdn.microsoft.com/en-us/devlabs/dd795202.

[30]

Microsoft. Task Parallel Library (TPL). http://msdn.microsoft.com/en-us/library/dd460717.aspx.

[31]

M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: Efficient deterministic multithreading in software. In ASPLOS, 2009.

Digital Library

[32]

OpenMP Architecture Review Board. OpenMP Application Program Interface, Version 3.1. http://www.openmp.org/mp-documents/OpenMP3.1.pdf, 2011.

[33]

Oracle. Java Platform, Standard Edition 7 API specification. http://download.oracle.com/javase/7/docs/api/.

[34]

J. M. Perez, R. M. Badia, and J. Labarta. A dependency-aware taskbased programming environment for multi-core architectures. In IEEE International Conference on Cluster Computing, 2008.

[35]

M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. TOPLAS, 20(3):483--545, May 1998.

Digital Library

[36]

G. Rosu and T. F. Serbanuta. An overview of the K semantic framework. Journal of Logic and Algebraic Programming, 79(6), 2010.

[37]

J. Schafer and A. Poetzsch-Heffter. JCoBox: Generalizing active objects to concurrent components. In ECOOP, 2010.

Digital Library

Cited By

Roșu G(2015)From Rewriting Logic, to Programming Language Semantics, to Program VerificationLogic, Rewriting, and Concurrency10.1007/978-3-319-23165-5_28(598-616)Online publication date: 27-Aug-2015
https://doi.org/10.1007/978-3-319-23165-5_28
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Lifflander JMiller PSlattengren NMorales NStickney PPebay P(2020)Design and Implementation Techniques for an MPI-Oriented AMT Runtime2020 Workshop on Exascale MPI (ExaMPI)10.1109/ExaMPI52011.2020.00009(31-40)Online publication date: Nov-2020
https://doi.org/10.1109/ExaMPI52011.2020.00009
Show More Cited By

Index Terms

The tasks with effects model for safe concurrency
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Concurrent programming structures
      2. Language types
        Concurrent programming languages
        Distributed programming languages
        Parallel programming languages

Recommendations

The tasks with effects model for safe concurrency
PPoPP '13: Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming

Today's widely-used concurrent programming models either provide weak safety guarantees, making it easy to write code with subtle errors, or are limited in the class of programs that they can express. We propose a new concurrent programming model based ...
Safe nondeterminism in a deterministic-by-default parallel language
POPL '11

A number of deterministic parallel programming models with strong safety guarantees are emerging, but similar support for nondeterministic algorithms, such as branch and bound search, remains an open question. We present a language together with a type ...
Safe nondeterminism in a deterministic-by-default parallel language
POPL '11: Proceedings of the 38th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

A number of deterministic parallel programming models with strong safety guarantees are emerging, but similar support for nondeterministic algorithms, such as branch and bound search, remains an open question. We present a language together with a type ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 48, Issue 8

PPoPP '13

August 2013

309 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/2517327

Issue’s Table of Contents

PPoPP '13: Proceedings of the 18th ACM SIGPLAN symposium on Principles and practice of parallel programming
February 2013
332 pages
ISBN:9781450319225
DOI:10.1145/2442516
General Chairs:
Alex Nicolau
University of California, Irvine, USA
,
Xiaowei Shen
IBM Research, China
,
Program Chairs:
Saman Amarasinghe
Massachusetts Institute of Technology, USA
,
Richard Vuduc
Georgia Institute of Technology, USA

Copyright © 2013 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: 23 February 2013

Published in SIGPLAN Volume 48, Issue 8

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
350
Total Downloads

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

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roșu G(2015)From Rewriting Logic, to Programming Language Semantics, to Program VerificationLogic, Rewriting, and Concurrency10.1007/978-3-319-23165-5_28(598-616)Online publication date: 27-Aug-2015
https://doi.org/10.1007/978-3-319-23165-5_28
Zhao QQiu ZShao SHui XKhan HJin GKloeckner AMoreira J(2022)Understanding and Reaching the Performance Limit of Schedule Tuning on Stable Synchronization DeterminismProceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1145/3559009.3569669(223-238)Online publication date: 8-Oct-2022
https://dl.acm.org/doi/10.1145/3559009.3569669
Lifflander JMiller PSlattengren NMorales NStickney PPebay P(2020)Design and Implementation Techniques for an MPI-Oriented AMT Runtime2020 Workshop on Exascale MPI (ExaMPI)10.1109/ExaMPI52011.2020.00009(31-40)Online publication date: Nov-2020
https://doi.org/10.1109/ExaMPI52011.2020.00009
Merrifield TRoghanchi SDevietti JEriksson JBahar IHerlihy MWitchel ELebeck A(2019)Lazy Determinism for Faster Deterministic MultithreadingProceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3297858.3304047(879-891)Online publication date: 4-Apr-2019
https://dl.acm.org/doi/10.1145/3297858.3304047
Faes MGross T(2019)Parallel Roles for Practical Deterministic Parallel ProgrammingLanguages and Compilers for Parallel Computing10.1007/978-3-030-35225-7_12(163-181)Online publication date: 15-Nov-2019
https://doi.org/10.1007/978-3-030-35225-7_12
Faes MGross T(2018)Concurrency-aware object-oriented programming with rolesProceedings of the ACM on Programming Languages10.1145/32765002:OOPSLA(1-30)Online publication date: 24-Oct-2018
https://dl.acm.org/doi/10.1145/3276500
Bianchi FMargara APezze M(2018)A Survey of Recent Trends in Testing Concurrent Software SystemsIEEE Transactions on Software Engineering10.1109/TSE.2017.270708944:8(747-783)Online publication date: 1-Aug-2018
https://dl.acm.org/doi/10.1109/TSE.2017.2707089
Bättig MGross T(2017)Synchronized-by-Default Concurrency for Shared-Memory SystemsACM SIGPLAN Notices10.1145/3155284.301874752:8(299-312)Online publication date: 26-Jan-2017
https://dl.acm.org/doi/10.1145/3155284.3018747
Lifflander JKrishnamoorthy S(2017)Cache locality optimization for recursive programsACM SIGPLAN Notices10.1145/3140587.306238552:6(1-16)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3140587.3062385
Lifflander JKrishnamoorthy SCohen AVechev M(2017)Cache locality optimization for recursive programsProceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3062341.3062385(1-16)Online publication date: 14-Jun-2017
https://dl.acm.org/doi/10.1145/3062341.3062385
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 Issue’s Table of Contents