research-article

A type and effect system for deterministic parallel Java

Authors:

Robert L. Bocchino, Jr.,

Vikram S. Adve,

Sarita V. Adve,

Stephen Heumann,

Rakesh Komuravelli,

Jeffrey Overbey,

Patrick Simmons,

Mohsen VakilianAuthors Info & Claims

OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications

Pages 97 - 116

https://doi.org/10.1145/1640089.1640097

Published: 25 October 2009 Publication History

Abstract

Today's shared-memory parallel programming models are complex and error-prone.While many parallel programs are intended to be deterministic, unanticipated thread interleavings can lead to subtle bugs and nondeterministic semantics. In this paper, we demonstrate that a practical type and effect system can simplify parallel programming by guaranteeing deterministic semantics with modular, compile-time type checking even in a rich, concurrent object-oriented language such as Java. We describe an object-oriented type and effect system that provides several new capabilities over previous systems for expressing deterministic parallel algorithms.We also describe a language called Deterministic Parallel Java (DPJ) that incorporates the new type system features, and we show that a core subset of DPJ is sound. We describe an experimental validation showing thatDPJ can express a wide range of realistic parallel programs; that the new type system features are useful for such programs; and that the parallel programs exhibit good performance gains (coming close to or beating equivalent, nondeterministic multithreaded programs where those are available).

References

[1]

http://dpj.cs.uiuc.edu.

[2]

http://gee.cs.oswego.edu/dl/concurrency-interest.

[3]

M. Abadi, C. Flanagan, and S. N. Freund. Types for safe locking: Static race detection for Java. TOPLAS, 2006.

Digital Library

[4]

F. Aleen and N. Clark. Commutativity analysis for software parallelization: letting program transformations see the big picture. ASPLOS, 2009.

Digital Library

[5]

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

Digital Library

[6]

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

Digital Library

[7]

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

Digital Library

[8]

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

Digital Library

[9]

R. Bocchino, V. Adve, S. Adve, and M. Snir. Parallel programming must be deterministic by default. First USENIX Workshop on Hot Topics in Parallelism (HotPar), 2009.

Digital Library

[10]

R. L. Bocchino and V. S. Adve. Formal definition and proof of soundness for Core DPJ. Technical Report UIUCDCS-R-2008-2980, U. Illinois, 2008.

[11]

C. Boyapati, R. Lee, and M. Rinard. Ownership types for safe programming: Preventing data races and deadlocks. OOPSLA, 2002.

Digital Library

[12]

J. Boyland. The interdependence of effects and uniqueness. Workshop on Formal Techs. for Java Programs, 2001.

[13]

J. Boyland. Checking interference with fractional permissions. SAS, 2003.

Digital Library

[14]

N. R. Cameron, S. Drossopoulou, J. Noble, and M. J. Smith. Multiple ownership. OOPSLA, 2007.

Digital Library

[15]

P. Charles, C. Grothoff, V. Saraswat, C. Donawa, A. Kielstra, K. Ebcioglu, C. von Praun, and V. Sarkar. X10: An object-oriented approach to non-uniform cluster computing. OOPSLA, 2005.

Digital Library

[16]

D. Clarke and S. Drossopoulou. Ownership, encapsulation and the disjointness of type and effect. OOPSLA, 2002.

Digital Library

[17]

D. Clarke and T. Wrigstad. External uniqueness is unique enough. ECOOP, 2003.

[18]

D. G. Clarke, J. M. Potter, and J. Noble. Ownership types for flexible alias protection. OOPSLA, 1998.

Digital Library

[19]

J. Dennis. Keynote address. PPOPP, 2009.

[20]

J. DeSouza and L. V. Kalé. MSA: Multiphase specifically shared arrays. LCPC, 2004.

Digital Library

[21]

J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: Deterministic Shared Memory Multiprocessing. ASPLOS, 2009.

Digital Library

[22]

M. Feng and C. E. Leiserson. Efficient detection of determinacy races in Cilk programs. SPAA, 1997.

Digital Library

[23]

C. Flanagan and M. Felleisen. The semantics of future and its use in program optimization. POPL, 1995.

Digital Library

[24]

R. Ghiya, D. Lavery, and D. Sehr. On the importance of points-to analysis and other memory disambiguation methods for C programs. PLDI, 2001.

Digital Library

[25]

A. Gotsman, J. Berdine, B. Cook, and M. Sagiv. Thread-modular shape analysis. PLDI, 2007.

Digital Library

[26]

A. Greenhouse and J. Boyland. An object-oriented effects system. ECOOP, 1999.

Digital Library

[27]

R. T. Hammel and D. K. Gifford. FX-87 performance measurements: Dataflow implementation. Technical Report MIT/LCS/TR-421, 1988.

Digital Library

[28]

B. Jacobs, F. Piessens, J. Smans, K. R. M. Leino, and W. Schulte. A programming model for concurrent object-oriented programs. TOPLAS, 2008.

Digital Library

[29]

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

Digital Library

[30]

K. R. M. Leino, A. Poetzsch-Heffter, and Y. Zhou. Using data groups to specify and check side effects. PLDI, 2002.

Digital Library

[31]

W. Liu, J. Tuck, L. Ceze, W. Ahn, K. Strauss, J. Renau, and J. Torrellas. POSH: a TLS compiler that exploits program structure. PPOPP, 2006.

Digital Library

[32]

Y. Lu and J. Potter. Protecting representation with effect encapsulation. POPL, 2006.

Digital Library

[33]

J. M. Lucassen and D. K. Gifford. Polymorphic effect systems. POPL, 1988.

Digital Library

[34]

C. C. Minh, J. Chung, C. Kozyrakis, and K. Olukotun. STAMP: Stanford transactional applications for multi-processing. IISWC, 2008.

[35]

P. W. O'Hearn. Resources, concurrency, and local reasoning. Theor. Comp. Sci., 2007.

Digital Library

[36]

M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: Efficient Deterministic Multithreading in Software. ASPLOS, 2009.

Digital Library

[37]

M. J. Parkinson and G. M. Bierman. Separation logic, abstraction and inheritance. POPL, 2008.

Digital Library

[38]

M. K. Prabhu and K. Olukotun. Using thread-level speculation to simplify manual parallelization. PPOPP, 2003.

Digital Library

[39]

M. Raza, C. Calcagno, and P. Gardner. Automatic parallelization with separation logic. ESOP, 2009.

Digital Library

[40]

J. C. Reynolds. Separation logic: A logic for shared mutable data structures. Symp. on Logic in Comp. Sci., 2002.

Digital Library

[41]

M. C. Rinard. The design, implementation and evaluation of Jade: a portable, implicitly parallel programming language. PhD thesis, Stanford University, 1994.

Digital Library

[42]

M. C. Rinard and P. C. Diniz. Commutativity analysis: A new analysis technique for parallelizing compilers. TOPLAS, 1997.

Digital Library

[43]

M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. TOPLAS, 1998.

Digital Library

[44]

C. Sadowski, S. N. Freund, and C. Flanagan. SingleTrack: A dynamic determinism checker for multithreaded programs. ESOP, 2009.

Digital Library

[45]

J. P. Singh, W.-D. Weber, and A. Gupta. SPLASH: Stanford parallel applications for shared--memory. Technical report, Stanford University, 1992.

[46]

M. Smith. Towards an effects system for ownership domains. ECOOP, 2005.

[47]

M. Snir. Parallel Programming Language 1 (PPL1), V0.9 - Draft. Technical Report UIUCDCS-R-2006-2969, U. Illinois, 2006.

[48]

T. Terauchi and A. Aiken. A capability calculus for concurrency and determinism. TOPLAS, 2008.

Digital Library

[49]

M. Vakilian, D. Dig, R. Bocchino, J. Overbey, V. Adve, and R. Johnson. Inferring Method Effect Summaries for Nested Heap Regions. ASE, 2009. To appear.

Digital Library

[50]

C. von Praun, L. Ceze, and C. Caşcaval. Implicit parallelism with ordered transactions. PPOPP, 2007.

Digital Library

[51]

A. Welc, S. Jagannathan, and A. Hosking. Safe futures for Java. OOPSLA, 2005.

Digital Library

[52]

K. Zee, V. Kuncak, and M. Rinard. Full functional verification of linked data structures. PLDI, 2008.

Digital Library

Cited By

Arora JMuller SAcar U(2024)Disentanglement with Futures, State, and InteractionProceedings of the ACM on Programming Languages10.1145/36328958:POPL(1569-1599)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632895
Westrick SFluet MRainey MAcar U(2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632880
Abdi JPosluns GZhang GWang BJeffrey MAgrawal KPetrank E(2024)When Is Parallelism Fearless and Zero-Cost with Rust?Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659966(27-40)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659966
Show More Cited By

Index Terms

A type and effect system for deterministic parallel Java
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
        Concurrent programming languages
        Distributed programming languages
        Parallel programming languages

Recommendations

A type and effect system for deterministic parallel Java
OOPSLA '09

Today's shared-memory parallel programming models are complex and error-prone.While many parallel programs are intended to be deterministic, unanticipated thread interleavings can lead to subtle bugs and nondeterministic semantics. In this paper, we ...
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 Conferences

OOPSLA '09: Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications

October 2009

590 pages

ISBN:9781605587660

DOI:10.1145/1640089

General Chair:
Shail Arora
Adayana, Inc.
,
Program Chair:
Gary Leavens
University of Central Florida

ACM SIGPLAN Notices Volume 44, Issue 10
OOPSLA '09
October 2009
554 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/1639949
Issue’s Table of Contents

Copyright © 2009 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: 25 October 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

OOPSLA09

Sponsor:

SIGPLAN

OOPSLA09: ACM SIGPLAN Object Oriented Programming Systems and Applications Conference

October 25 - 29, 2009

Florida, Orlando, USA

Acceptance Rates

OOPSLA '09 Paper Acceptance Rate 25 of 144 submissions, 17%;

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

349
Total Citations
View Citations
1,358
Total Downloads

Downloads (Last 12 months)48
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Arora JMuller SAcar U(2024)Disentanglement with Futures, State, and InteractionProceedings of the ACM on Programming Languages10.1145/36328958:POPL(1569-1599)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632895
Westrick SFluet MRainey MAcar U(2024)Automatic Parallelism ManagementProceedings of the ACM on Programming Languages10.1145/36328808:POPL(1118-1149)Online publication date: 5-Jan-2024
https://dl.acm.org/doi/10.1145/3632880
Abdi JPosluns GZhang GWang BJeffrey MAgrawal KPetrank E(2024)When Is Parallelism Fearless and Zero-Cost with Rust?Proceedings of the 36th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3626183.3659966(27-40)Online publication date: 17-Jun-2024
https://dl.acm.org/doi/10.1145/3626183.3659966
Wilkins MWestrick SKandiah VBernat ASuchy BDeiana ECampanoni SAcar UDinda PHardavellas NDubach CBruening DHardekopf B(2023)WARDen: Specializing Cache Coherence for High-Level Parallel LanguagesProceedings of the 21st ACM/IEEE International Symposium on Code Generation and Optimization10.1145/3579990.3580013(122-135)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3579990.3580013
Gonnord LHenrio LMorel LRadanne G(2023)A Survey on Parallelism and DeterminismACM Computing Surveys10.1145/356452955:10(1-28)Online publication date: 2-Feb-2023
https://dl.acm.org/doi/10.1145/3564529
Abdi JZhang GJeffrey MAgrawal KShun J(2023)Brief Announcement: Is the Problem-Based Benchmark Suite Fearless with Rust?Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591313(303-305)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591313
Gordon CYun C(2023)Error Localization for Sequential Effect SystemsStatic Analysis10.1007/978-3-031-44245-2_16(343-370)Online publication date: 22-Oct-2023
https://dl.acm.org/doi/10.1007/978-3-031-44245-2_16
Chen AFathololumi PKoskinen EPincus J(2022)Veracity: declarative multicore programming with commutativityProceedings of the ACM on Programming Languages10.1145/35633496:OOPSLA2(1726-1756)Online publication date: 31-Oct-2022
https://dl.acm.org/doi/10.1145/3563349
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
Melicher DXu AZhao VPotanin AAldrich J(2022)Bounded Abstract EffectsACM Transactions on Programming Languages and Systems10.1145/349242744:1(1-48)Online publication date: 12-Jan-2022
https://dl.acm.org/doi/10.1145/3492427
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 Table of Contents