Research Abstracts - 2006

JCilk -- A Java-Based Multithreaded Programming Language

I-Ting Angelina Lee & Charles E. Leiserson

Introduction

JCilk is a Java-based multithreaded language for parallel programming that extends the semantics of Java by introducing "Cilk-like" [4][10] linguistic constructs for parallel control. The original Cilk language provides a dynamic multithreading model that supports call-return semantics in a C language context. The Cilk system also includes a provably good scheduler that guarantees programs can take full advantage of the resources available at runtime. Cilk, as an extension of C, lacks support for such modern language features as objects and exceptions. Java, on the other hand, provides many desirable modern language features such as automated memory management, an exception-handling mechanism, and inheritance, but it lacks a good dynamic threading model. Java's built-in threading is static, that is, threads are created explicitly to execute code specified by the user at compile time, with no correlation between the number of threads created by the running program and the resources available to it. Java's threading model also does not support the passing of exceptions or return values from one thread back to its "parent" thread. JCilk supplies Java with a dynamic threading model and the ability for methods to be executed in parallel and return their results to the methods that called them.

Language Design and Features

JCilk introduces three keywords into Java: cilk, spawn, and sync. The keyword cilk is used as a method modifier to declare a method to be a Cilk method, which means that it can be spawned to execute it in parallel. When a parent method spawns a child method (by preceding a method call with the spawn keyword), the parent can continue to execute in parallel with its spawned child method. The sync keyword acts as a local synchronization barrier. Program control cannot go beyond a sync statement until all previously spawned children have terminated. In general, until a Cilk method executes a sync statement, it cannot safely use results returned by previously spawned children.

Since Java allows a method to signal an exception rather than return normally, JCilk's semantics must extend the Cilk semantics to handle this possibility. A method generally throws an exception to indicate that it has completed abnormally or unsuccessfully. When this happens in Java, control is passed to the nearest dynamically enclosing catch clause, and all intervening dynamically enclosing blocks are abruptly completed (pp. 210-220 [6]). In JCilk, we extend this notion of abrupt completion to implicitly abort any side computations that have been spawned off from inside a block which is being abruptly completed. The implicit aborting of side computations yields a clean semantics in which only a single exception from the enclosing try block is handled. A method which is signaled to abort will eventually interrupt its normal execution by throwing a CilkAbort exception. It turns out that, this exception-based abort mechanism allow programs with speculative computations to be expressed succinctly: we are able to obviate the need for Cilk's inlet and abort constructs and still able to program speculative computations easily.

Aborting might cause a computation to be interrupted asynchronously, causing havoc in programmer understanding of code behavior, however. To simplify the reasoning of program states when abort occurs, JCilk only permits the CilkAbort to be thrown only at certain points in the method when parallel operations would be occurring. In addition, the programmer may catch the CilkAbort to clean up partially completed work, without interrupting the abort process. The JCilk system ensures that the abort process continues, and the stacks unwind structurally up to the point where the abort process is initiated. Interested readers can check out [3] for more details on JCilk's exception semantics.

Implementation Platform

The JCilk system consists of two components: a runtime system and a compiler. JCilk's runtime system implements a Cilk-like work-stealing scheduling algorithm [1, 4] that schedules threads dynamically according to available system resources. Depending on the resources availability, a method which began to execute on one processor may migrate to continue execution on another processor to create parallelism. This code migration requires a continuation mechanism, which is provided by the compiler. We support a continuation mechanism without slowing down pure Java code by creating an intermediate language called GoJava. This language is a minimal extension of Java that allows the goto statement in limited and specific circumstances. Our compilation process translates a JCilk program into an intermediate GoJava program that contains calls into the JCilk runtime system. A minimally modified GCJ compiler called Jgo compiles this GoJava program to produce Java bytecode that can be executed on any standard Java Virtual Machine [8]. Our implementation of the JCilk system is easily portable, because most parts are implemented in pure Java other than the minimal changes to the GCJ compiler. The runtime system is implemented in Java. The compiler is implemented using the Polyglot compiler toolkit [9] and the Gnu Compiler for Java (GCJ) [5]. Interested readers can refer to [2] and [7] for more implementation details of JCilk's runtime system and compiler.

Progress

We have designed a semantics for JCilk in general, and for exception handling in particular, which gracefully extends the Java language to include the Cilk primitives. This extension is "faithful" in that it obeys Java's ordinary serial semantics when a program is executed on a single processor. On multiple processors, it allows parallelism while still making it easy to reason about how a program behaves.

Regarding implementation, we have already built a working version of the JCilk system that handles the parallel exception semantics that we have designed. Currently, we are still working on improving the system performance.

Future Work

We hope to use JCilk to further explore the interaction between the sometimes-arcane world of parallel computing and the day-to-day world of commodity serial computing. In particular, there are two possible directions that we are heading. First, there is currently a sharp delineation between Cilk methods and non-Cilk Java methods. One fertile topic for future research is to design a mechanism to break this barrier between Java and JCilk. Second, JCilk supports a dynamic threading model, which is quite different from Java's static threading model. We like to eventually provide both threading models in JCilk, although at this point we are not clear how threads from two models should interact and communicate with each other. It will take some thorough consideration to come up with a sophisticated model that encompasses both threading models and incorporates them harmoniously.

Acknowledgment

The research described in this abstract represents a collaborative work with John S. Danaher, who graduated in June 2005. Special thanks to John, who took part in designing the JCilk semantics for exception handling, and developed the JCilk runtime system.

Thanks to Christine Flood for helping us running some experiments for performance study. Thanks to Dave Dice for helpful discussions regarding timing in Java. Thanks to Kunal Agrawal, Scott Ananian, Jeremy Fineman, Viktor Kuncak, Bradley Kuszmaul, Edya Ladan Mozes, Martin Rinard, and Jim Sukha of MIT CSAIL, Jan-Willem Maessen of Sun Microsystems, Gideon Stupp of Tel Aviv University, and Wong Weng Fai of National University of Singapore for helpful discussions in general.

Research Support

This research is supported in part by the Singapore-MIT Alliance and by NSF Grant ACI-0324974 and CNS-0305606. I-Ting Angelina Lee is supported by Sun Microsystems Fellowship.

References:

[1] R. D. Blumofe and C. E. Leiserson. Scheduling Multithreaded Computations by Work Stealing. In Journal of the ACM, pages 720-748, September, 1999.

[2] J. S. Danaher. The JCilk-1 runtime system. Master's thesis, Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science, June 2005.

[3] J. S. Danaher, I.-T. A. Lee, and C. E. Leiserson. The JCilk Language for Multithreaded Computing. In Proceedings of the Synchronization and Concurrency in Object-Oriented Languages (SCOOL), San Diego, California, October 2005.

[4] M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the Cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 212-223, Montreal, Quebec, Canada, June 1998. Proceedings published ACM SIGPLAN Notices, Vol. 33, No. 5, May, 1998.

[5] The GNU compiler for the Java programming language. http://gcc.gnu.org/java/, Oct. 2004.

[6] J. Gosling, B. Joy, G. Steele, and G. Bracha. The Java Language Specification Second Edition. Addison-Wesley, Boston, Massachusetts, 2000.

[7] I.-T. A. Lee. The JCilk multithreaded language. Master's thesis, Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science, August 2005.

[8] T. Lindholm and F. Yellin. The Java Virtual Machine Specification Second Edition. Addison-Wesley, Boston, Massachusetts, 2000.

[9] N. Nystrom, M. Clarkson, and A. C. Myers. Polyglot: An extensible compiler framework for Java. In Proceedings of the 12th International Conference on Compiler Construction, pages 138-152. Springer-Verlag, Apr. 2003.

[10] Supercomputing Technologies Group, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts 02139. Cilk 5.3.2 Reference Manual, Nov. 2001.