Introduction

JCilk is a Java-based multithreaded language for parallel programming that extends the semantics of Java by introducing "Cilk-like" [1][2] 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 [5]). In JCilk, we extend this notion of abrupt completetion to implicitly abort any side computations that have been spawned off from inside a block which is being abruptly completed. A method which is signalled to abort will eventually interrupt its normal execution by throwing a CilkAbort exception. To simplify the reasoning of program states when abort happens, JCilk only permits this exception to be thrown at certain points in the method when parallel operations would be occurring anyway.

Implementation Platform

Our implementation of the JCilk language is comprised of two parts: the runtime system and the compiler. The runtime system is implemented purely in Java. The compiler is implemented using the Polyglot compiler toolkit [3] and the Gnu Compiler for Java (GCJ) [4]. The whole system is easily portable because other than the minimal changes to the GCJ compiler, most parts are implemented in pure Java.

The runtime system is based on the work-stealing scheduling algorithm used by Cilk, which allows a method which began to execute on one processor to be continued on a another processor. This migration requires limited support for continuations. To add continuations to a Java-language environment, we created an intermediate language called GoJava which extends Java to support a restricted goto statement. 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.

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 basic spawn and sync semantics. We have also built the runtime-system infrastructure necessary to implement our parallel exception semantics. Compiler support for parallel exceptions is still being developed.

Future Work

In the near term, our main goal is to complete an end-to-end system which will compile and run JCilk programs, including those which make use of our full exception semantics. The next big goal is to examine and enhance the system's performance. It seems likely that this will involve modifications to the underlying Virtual Machine to support more efficient synchronization and memory-allocation primitives. Of course, testing performance will require writing more applications in JCilk, which will also give us an opportunity to explore the power of the new semantics we have chosen.

In the long term, 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 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.

Acknowledgment

Thanks to Kunal Agrawal, Scott Ananian, Jeremy Fineman, Bradley Kuszmaul, Martin Rinard, Gideon Stupp, and Jim Sukha of MIT CSAIL and Wong Weng Fai of National University of Singapore for helpful discussions.

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] Supercomputing Technologies Group,, MIT Laboratory for Computer Science, 545 Technology Square, Cambridge, Massachusetts 02139. Cilk 5.3.2 Reference Manual, Nov. 2001.

[2] 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.

[3] 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.

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

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