Deterministic Parallel Java: Towards Deterministic-by-default Parallel Programming

January 12, 2009
Robert Bocchino | University of Illinois

One important feature of a parallel programming model is deterministic semantics: that is, a program produces the same output on every execution with a given input, regardless of the parallel schedule chosen. Determinism makes parallel programs much easier to write, understand, debug, and maintain. Further, many (though not all) parallel programs are, in fact, intended to have deterministic semantics. However, general-purpose languages, particularly those that allow arbitrary updates to shared data, typically do not guarantee determinism, leaving the burden on the programmer to ensure that the program is correctly synchronized.

In this talk, I will present Deterministic Parallel Java (DPJ), an extension of the Java programming language that guarantees deterministic semantics in the presence of aliasing and updates to shared mutable objects. An important consequence of deterministic semantics is that a working sequential program needs no further testing after parallelization with DPJ. In DPJ, the programmer partitions the heap into regions and annotates method definitions with read and write effects on those regions. The programmer also explicitly marks parallel tasks and synchronization points. The compiler checks that the method effects are correctly summarized, and that the program is correctly synchronized to ensure determinism. I will describe the core language features, illustrate them with examples, and describe the results of an initial evaluation of the language. I will also describe ongoing work, including features we plan to add to the language.

Speaker Details

Rob Bocchino is a Ph.D. student at the University of Illinois at Urbana-Champaign. His research focuses on language, compiler, and runtime techniques for making parallel programming easier and safer, while retaining high performance. Currently he is the lead graduate student on the Deterministic Parallel Java project at the University of Illinois (http://dpj.cs.uiuc.edu). He has also published in the areas of vector parallelism, multimedia compression algorithms, and software transactional memory for large-scale “shared nothing” clusters. Rob has been recognized as an Excellent Teaching Assistant while at Illinois. He holds an A.B. cum laude in mathematics from Harvard College. Rob also holds a J.D. from Harvard Law School and worked as a technology lawyer in Boston before attending graduate school.