A type and effect system for deterministic parallel Java

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A type and effect system for deterministic parallel Java

Full text

Pdf (569 KB)

Source

Conference on Object Oriented Programming Systems Languages and Applications archive
Proceeding of the 24th ACM SIGPLAN conference on Object oriented programming systems languages and applications table of contents

Orlando, Florida, USA

SESSION: Concurrency table of contents

Pages 97-116

Year of Publication: 2009

ISBN:978-1-60558-766-0

Also published in ...

Authors

Robert L. Bocchino, Jr.	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Vikram S. Adve	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Danny Dig	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Sarita V. Adve	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Stephen Heumann	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Rakesh Komuravelli	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Jeffrey Overbey	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Patrick Simmons	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Hyojin Sung	University of Illinois at Urbana-Champaign, Urbana, IL, USA
Mohsen Vakilian	University of Illinois at Urbana-Champaign, Urbana, IL, USA

Sponsor

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 42, Downloads (12 Months): 42, Citation Count: 0

Additional Information:

abstract references index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1640089.1640097 What is a DOI?

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

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked 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.
	4	F. Aleen and N. Clark. Commutativity analysis for software parallelization: letting program transformations see the big picture. ASPLOS, 2009.
	5	M. D. Allen, S. Sridharan, and G. S. Sohi. Serialization sets: A dynamic dependence-based parallel execution model. PPOPP, 2009.
	6	Z. Anderson, D. Gay, R. Ennals, and E. Brewer. SharC: Checking data sharing strategies for multithreaded C. PLDI, 2008.
	7	E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe Multithreaded Programming for C/C++. OOPSLA, 2009.
	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.
	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.
	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.
	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.
	14	N. R. Cameron, S. Drossopoulou, J. Noble, and M. J. Smith. Multiple ownership. OOPSLA, 2007.
	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.
	16	D. Clarke and S. Drossopoulou. Ownership, encapsulation and the disjointness of type and effect. OOPSLA, 2002.
	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.
	19	J. Dennis. Keynote address. PPOPP, 2009.
	20	J. DeSouza and L. V. Kalé. MSA: Multiphase specifically shared arrays. LCPC, 2004.
	21	J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: Deterministic Shared Memory Multiprocessing. ASPLOS, 2009.
	22	M. Feng and C. E. Leiserson. Efficient detection of determinacy races in Cilk programs. SPAA, 1997.
	23	C. Flanagan and M. Felleisen. The semantics of future and its use in program optimization. POPL, 1995.
	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.
	25	A. Gotsman, J. Berdine, B. Cook, and M. Sagiv. Thread-modular shape analysis. PLDI, 2007.
	26	A. Greenhouse and J. Boyland. An object-oriented effects system. ECOOP, 1999.
	27	R. T. Hammel and D. K. Gifford. FX-87 performance measurements: Dataflow implementation. Technical Report MIT/LCS/TR-421, 1988.
	28	B. Jacobs, F. Piessens, J. Smans, K. R. M. Leino, and W. Schulte. A programming model for concurrent object-oriented programs. TOPLAS, 2008.
	29	M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic parallelism requires abstractions. PLDI, 2007.
	30	K. R. M. Leino, A. Poetzsch-Heffter, and Y. Zhou. Using data groups to specify and check side effects. PLDI, 2002.
	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.
	32	Y. Lu and J. Potter. Protecting representation with effect encapsulation. POPL, 2006.
	33	J. M. Lucassen and D. K. Gifford. Polymorphic effect systems. POPL, 1988.
	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.
	36	M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: Efficient Deterministic Multithreading in Software. ASPLOS, 2009.
	37	M. J. Parkinson and G. M. Bierman. Separation logic, abstraction and inheritance. POPL, 2008.
	38	M. K. Prabhu and K. Olukotun. Using thread-level speculation to simplify manual parallelization. PPOPP, 2003.
	39	M. Raza, C. Calcagno, and P. Gardner. Automatic parallelization with separation logic. ESOP, 2009.
	40	J. C. Reynolds. Separation logic: A logic for shared mutable data structures. Symp. on Logic in Comp. Sci., 2002.
	41	M. C. Rinard. The design, implementation and evaluation of Jade: a portable, implicitly parallel programming language. PhD thesis, Stanford University, 1994.
	42	M. C. Rinard and P. C. Diniz. Commutativity analysis: A new analysis technique for parallelizing compilers. TOPLAS, 1997.
	43	M. C. Rinard and M. S. Lam. The design, implementation, and evaluation of Jade. TOPLAS, 1998.
	44	C. Sadowski, S. N. Freund, and C. Flanagan. SingleTrack: A dynamic determinism checker for multithreaded programs. ESOP, 2009.
	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.
	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.
	50	C. von Praun, L. Ceze, and C. Caşcaval. Implicit parallelism with ordered transactions. PPOPP, 2007.
	51	A. Welc, S. Jagannathan, and A. Hosking. Safe futures for Java. OOPSLA, 2005.
	52	K. Zee, V. Kuncak, and M. Rinard. Full functional verification of linked data structures. PLDI, 2008.