The DOI matches its Crossref record; 43 of the 43 references it cites were found in a registry or an index.
A type and effect system for deterministic parallel Java
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).
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Separation logic: a logic for shared mutable data structures
Reynolds, J. C. (2003) · Proceedings 17th Annual IEEE Symposium on Logic in Computer Science · doi:10.1109/lics.2002.1029817 · Cited by 2,156
X10: an object-oriented approach to non-uniform cluster computing
Charles, P., Grothoff, C., Saraswat, V., Donawa, C., Kielstra, A., Ebcioglu, K., von Praun, C., & Sarkar, V. (2005) · Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/1094811.1094852 · Cited by 1,268
Cilk: an efficient multithreaded runtime system
Blumofe, R. D., Joerg, C. F., Kuszmaul, B. C., Leiserson, C. E., Randall, K. H., & Zhou, Y. (1995) · Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/209936.209958 · Cited by 1,021
SPLASH: Stanford parallel applications for shared-memory
Singh, J. P., Weber, W.-D., & Gupta, A. (1992) · ACM SIGARCH Computer Architecture News · doi:10.1145/130823.130824 · Cited by 925
STAMP: Stanford Transactional Applications for Multi-Processing
Minh, C. C., Chung, J., Kozyrakis, C., & Olukotun, K. (2008) · 2008 IEEE International Symposium on Workload Characterization · doi:10.1109/iiswc.2008.4636089 · Cited by 873
Ownership types for flexible alias protection
Clarke, D. G., Potter, J. M., & Noble, J. (1998) · Proceedings of the 13th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/286936.286947 · Cited by 580
Ownership types for safe programming: preventing data races and deadlocks
Boyapati, C., Lee, R., & Rinard, M. (2002) · Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications - OOPSLA '02 · doi:10.1145/582419.582440 · Cited by 570
Resources, concurrency, and local reasoning
O’Hearn, P. W. (2007) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.12.035 · Cited by 552
Lucassen, J. M., & Gifford, D. K. (1988) · Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '88 · doi:10.1145/73560.73564 · Cited by 481
Optimistic parallelism requires abstractions
Kulkarni, M., Pingali, K., Walter, B., Ramanarayanan, G., Bala, K., & Chew, L. P. (2007) · Proceedings of the 28th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1250734.1250759 · Cited by 441
Checking interference with fractional permissions
Boyland, J. (2003) · Cited by 382
Kendo: efficient deterministic multithreading in software
Olszewski, M., Ansel, J., & Amarasinghe, S. (2009) · Proceedings of the 14th international conference on Architectural support for programming languages and operating systems · doi:10.1145/1508244.1508256 · Cited by 380
DMP: deterministic shared memory multiprocessing
Devietti, J., Lucia, B., Ceze, L., & Oskin, M. (2009) · Proceedings of the 14th international conference on Architectural support for programming languages and operating systems · doi:10.1145/1508244.1508255 · Cited by 328
Ownership, encapsulation and the disjointness of type and effect
Clarke, D., & Drossopoulou, S. (2002) · Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications - OOPSLA '02 · doi:10.1145/582419.582447 · Cited by 257
Grace: safe multithreaded programming for C/C++
Berger, E. D., Yang, T., Liu, T., & Novark, G. (2009) · ACM SIGPLAN Notices · doi:10.1145/1639949.1640096 · Cited by 241
Types for safe locking: Static race detection for Java
Abadi, M., Flanagan, C., & Freund, S. N. (2006) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1119479.1119480 · Cited by 222
POSH: a TLS compiler that exploits program structure
Liu, W., Tuck, J., Ceze, L., Ahn, W., Strauss, K., Renau, J., & Torrellas, J. (2006) · Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming · doi:10.1145/1122971.1122997 · Cited by 215
Full functional verification of linked data structures
Zee, K., Kuncak, V., & Rinard, M. (2008) · Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/1375581.1375624 · Cited by 203
The design, implementation, and evaluation of Jade
Rinard, M. C., & Lam, M. S. (1998) · ACM Transactions on Programming Languages and Systems · doi:10.1145/291889.291893 · Cited by 198
Welc, A., Jagannathan, S., & Hosking, A. (2005) · Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications · doi:10.1145/1094811.1094845 · Cited by 181
Grace: safe multithreaded programming for C/C++
Berger, E. D., Yang, T., Liu, T., & Novark, G. (2009) · Proceedings of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications · doi:10.1145/1640089.1640096 · Cited by 176
Parallel Programming Must Be Deterministic by Default
Bocchino, R. L., Adve, V., Adve, S. V., & Snir, M. (2018) · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · doi:10.1184/r1/6625115 · Cited by 170
Self-citationCommutativity analysis: a new analysis technique for parallelizing compilers
Rinard, M., & Diniz, P. C. (1997) · ACM Transactions on Programming Languages and Systems · doi:10.1145/267959.269969 · Cited by 168
External Uniqueness Is Unique Enough
Clarke, D., & Wrigstad, T. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45070-2_9 · Cited by 163
Separation logic, abstraction and inheritance
Parkinson, M., & Bierman, G. M. (2008) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/1328438.1328451 · Cited by 139
Implicit parallelism with ordered transactions
von Praun, C., Ceze, L., & Caşcaval, C. (2007) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1229428.1229443 · Cited by 119
Efficient detection of determinacy races in Cilk programs
Feng, M. D., & Leiserson, C. E. (1997) · ACM Symposium on Parallel Algorithms and Architectures (SPAA) · doi:10.1145/258492.258493 · Cited by 117
Using data groups to specify and check side effects
Leino, K. R. M., Poetzsch‐Heffter, A., & Zhou, Y. (2002) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/512529.512559 · Cited by 114
Gotsman, A., Berdine, J., Cook, B., & Sagiv, M. (2007) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1250734.1250765 · Cited by 109
A programming model for concurrent object-oriented programs
Jacobs, B., Piessens, F., Smans, J., Leino, K. R. M., & Schulte, W. (2008) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1452044.1452045 · Cited by 106
Using thread-level speculation to simplify manual parallelization
Prabhu, M. K., & Olukotun, K. (2003) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/781498.781500 · Cited by 94
On the importance of points-to analysis and other memory disambiguation methods for C programs
Ghiya, R., Lavery, D., & Sehr, D. C. (2001) · Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/378795.378806 · Cited by 92
The semantics of future and its use in program optimization
Cormac Flanagan, A., & Felleisen, M. (1995) · ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL) · doi:10.1145/199448.199484 · Cited by 91
Cameron, N. R., Drossopoulou, S., Noble, J., & Smith, M. J. (2007) · Conference on Object-Oriented Programming Systems, Languages, and Applications · doi:10.1145/1297027.1297060 · Cited by 73
Anderson, Z., Gay, D. E., Ennals, R., & Brewer, E. A. (2008) · ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) · doi:10.1145/1375581.1375600 · Cited by 69
SingleTrack: A Dynamic Determinism Checker for Multithreaded Programs
Sadowski, C., Freund, S. N., & Cormac Flanagan, A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00590-9_28 · Cited by 68
Serialization sets: a dynamic dependence-based parallel execution model
Allen, M. D., Sridharan, S., & Sohi, G. S. (2009) · ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming · doi:10.1145/1504176.1504190 · Cited by 66
Protecting representation with effect encapsulation
Lu, Y., & Potter, J. (2006) · doi:10.1145/1111037.1111069 · Cited by 51
Aleen, F., & Clark, N. (2009) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/1508244.1508273 · Cited by 47
Automatic Parallelization with Separation Logic
Raza, M., Calcagno, C., & Gardner, P. A. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00590-9_25 · Cited by 40
Inferring Method Effect Summaries for Nested Heap Regions
Vakilian, M., Dig, D., Bocchino, R. L., Overbey, J. L., Adve, V., & Johnson, R. E. (2009) · IEEE/ACM International Conference on Automated Software Engineering (ASE) · doi:10.1109/ase.2009.68 · Cited by 40
Self-citationA capability calculus for concurrency and determinism
Terauchi, T., & Aiken, A. (2008) · ACM Transactions on Programming Languages and Systems · doi:10.1145/1387673.1387676 · Cited by 37
MSA: Multiphase Specifically Shared Arrays
DeSouza, J., & Kalé, L. V. (2005) · Lecture notes in computer science · doi:10.1007/11532378_20 · Cited by 25
Cited by
Legion: expressing locality and independence with logical regions
Bauer, M., Treichler, S., Slaughter, E., & Aiken, A. (2012) · doi:10.5555/2388996.2389086 · Cited by 357
Kuper, L., Turon, A., Krishnaswami, N. R., & Newton, R. R. (2014) · Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages · doi:10.1145/2535838.2535842 · Cited by 46
Navarro Leija, O. S., Shiptoski, K., Scott, R. G., Wang, B., Renner, N., Newton, R. R., & Devietti, J. (2020) · Proceedings of the Twenty-Fifth International Conference on Architectural Support for Programming Languages and Operating Systems · doi:10.1145/3373376.3378519 · Cited by 22
Taming the parallel effect zoo
Kuper, L., Todd, A., Tobin-Hochstadt, S., & Newton, R. R. (2014) · Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation · doi:10.1145/2594291.2594312 · Cited by 19
Metadata
- Authors
- Bocchino, R. L., Adve, V. S., Dig, D., Adve, S. V., Heumann, S., Komuravelli, R., Overbey, J., Simmons, P., Sung, H., & Vakilian, M.
- Venue
- ACM SIGPLAN Notices
- Published
- 2009-10-25
- Volume
- 44
- Issue
- 10
- Pages
- 97-116
- ISSN
- 0362-1340 (ISSN-L)
- 1558-1160
- OpenAlex
- W2096403564
- Cited by
- 295
- References
- 43
- FWCI
- 45.54
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.