Concurrency and Parallelism subgroup
Our goal is to investigate how Java may be used as a tool for teaching parallel and concurrent computing. If effective tools for teaching parallel and concurrent computing in Java can be developed, this will make it possible to teach these topics more effectively and to spread the teaching of parallel and concurrent programming more broadly through the C.S. curriculum.
Java has several strengths for parallel and concurrent computing. These include the strengths of Java as a general purpose object-oriented language:
Two particular strengths of Java for parallel and concurrent computing are that
However, one of the key objectives of parallel computing is high performance. Consequently, there are some disadvantages to the use of Java:
The following recent comments underscore the importance of the last point:
"Java atomic procedures and lightweight threads can lead programmers down the road to ruin." (Ted Lewis, "The Binary Critic," IEEE Computer, 17(3):134, March, 1997.)
"Java Monitors appear easy to use. However, a deeper analysis reveals that they can be surprisingly tricky, suffer from subtle race conditions, and are actually a low-level synchronization tool in stark contrast to the hype that the rest of Java receives as a well-engineered language. The programmer is responsible for building safe and robust synchronization structures from Java monitors." (Stephen Hartley, paper in progress)
"The Java threads model is (somewhat loosely) based on the concepts of monitors and condition-variables. These were developed in the early 1970s (by Dijkstra, Brinch-Hansen, Hoare, and others) as a structured way of using the more primitive notion of semaphores. The standard reference quoted by Sun is [C.A. Hoare, "Monitors: an operating system structuring concept," CACM, 17(10):549-557, October, 1974.).
Nevertheless, monitors and condition-variables are not easy to use. The semantics are volatile and do not compose ." (Peter Welch, "Java in the Light of Occam/CSP," in A. Bakkers, Iparallel Programming and Java, Proceedings of WOTUG 20I, v 50 of Concurrent Systems Engineering, p. 282, IOS Press, Netherlands.)
The first two drawbacks to doing parallel computing in Java are likely to fade as just-in-time compilers become more effective and operating systems facilitate the use of threads on multi-processors. However, the last point, the difficulty of reliable thread programming in Java, needs to addressed before Java can become an effective tool for teaching parallel and concurrent programming. Indeed, work on this problem is essential to the effective use of Java for concurrent programming. We are focusing on investigating tools which have been developed to solve this problem and how those tools might be useful for teaching purposes.
Before we look into such tools, we briefly consider some of the salient issues of parallel computing in general and their implications for parallel computing in Java. The most important dichotomy in parallel computing is between the shared memory multi-processor hardware and programming models and the distributed memory, message-passing hardware and programming models. Many consider the shared memory model to be easier to program, at least for people initially trained for sequential programming, whereas there are limits on the scalability of the hardware for this model. The message-passing model calls for more work from the programmer in terms of allocating processes and data to processors, but scales to very large numbers of processors, up to several thousand. As the shared memory model is scaled up, the hardware generally reaches limits for SMP machines (symmetric multi-proccessors) and must move to NUMA machines (non-uniform memory access), thereby raising some of the same issues of data distribution that is important for distributed memory machines. In both models, deadlock and other synchronization issues are very important aspects of program development. Distributed memory machines may have synchronous or asynchronous message protocols, each with its advantages and disadvantages. In either case, there may be significant overheads for message-passing on distributed memory machines, although there have been efforts in the past to develop hardware which reduces this problem (e.g. the transputer).
The object-oriented programming model blurs some of the distinctions between the shared memory and distributed memory models for parallel programming. Calling an object method is conceptually close to sending a message. Consequently, a language such as Java can, perhaps, provide a model for parallel programming which is more amenable to programmers working from an object-oriented background, leaving efficiency issues for language implementation on the underlying hardware. Some of the ways in which an object-oriented approach impacts the organization of parallel threads of execution are the following:
the calling thread blocks and a new thread is created in the called method's object to execute the method's code
Or an already existing thread in the method's object is waiting to receive the message and continue execution when the message arrives
Or a thread in the called method's object selects one of several queued messages to receive based on some criterion and that thread executes the method associated with the received message (rendezvous)
If the calling thread does not block after sending the message, then we have asynchronous rather than synchronous behavior
If the calling thread's object and the called method's object are on different machines, then we have a remote procedure call
How to Proceed
We conclude that Java needs an API for concurrent and parallel programming that overcomes the problem of low-level synchronization primitives cited above. Such an API should provide
asynchronous message passing
synchronous message passing
remote procedure call
At this time, such a Java machine does not exist. However, significant progress has already been made toward developing an API which implements a message passing paradigm for Java concurrent and parallel computing, JCSP (Java with CSP -- Communicating Sequential Processes). JCSP is under development at the University of Kent, UK, under the leadership of Peter Welch. A parallel effort called JavePP is underway at the University of Twente under the leadership of Andy Bakkers.
The development of a library of classes which provide a CSP style of message passing provides the tools needed to do more reliable concurrent programming in Java and to be able to teach concurrent and parallel programming in Java effectively. This model is based on the theoretical language CSP (Anthony Hoare, "Communicating Sequential Processes," CACM, August, 1978). CSP found its first major implementation in Occam 2, the language developed for parallel computing in conjunction with the transputer, a processor developed in the mid-1980s for embedded and parallel computing. The two versions of Java with CSP mentioned above provide free libraries which implement CSP-style message-passing using channels. Channels are intermediate objects between threads that will free the programmer from synchronization, scheduling and data transfer constructs. Channels are easy to use and one can easily reason about the program. The composition constructs provide sequential, parallel, and alternative reading/writing on a channel. These constructs can be used to avoid deadlock and free the programmer from low-level synchronization and scheduling constructs, such as monitors and semaphores. This way, a Java program can be well-structured and well-behaved. The library is written in 100% Java. Link drivers for connections over the internet have been developed, so that channels can be used to communicate between processes on different machines. Information and the free libraries for the two versions of Java with CSP can be found at the following URLs.
We have tested the software from the University of Kent, the first site listed, under Sun JDK 1.1.6 under Windows 95 and found that it works well (note -- a patch to the just-in-time compiler for JDK 1.1.6 must be installed, or else run without the jit). Over the coming months we expect these two teams to merge their efforts into one common platform.
The development of Java with CSP does not, however, solve the problem of explicitly assigning different threads to different processors for true parallel computing. At some point, the operating systems for multiprocessors should catch up and make such assignment automatic. It would also be useful if control over the assignment of threads to different processors could be under programmer control. For now, it is possible to get access to thread control on multiple processors by using Sun Microsystems JDK 1.2 for Solaris 2.6. This JDK has an interface to the native Solaris multithreading library and allows the applications programmer to set the number of physical CPUs over which the Java threads will be distributed. However, this approach in itself does nothing to hide the complexities and subtleties of Java monitors from the programmer. It may be possible to combine this approach with a tool such as Java with CSP to get both control over the number of processors and a "safe" parallel model.
There have been other efforts to incorporate parallel programming tools into Java. We plan to investigate these as time permits. They include efforts to develop an interface between Java and MPI (Message Passing Interface) or PVM (Parallel Virtual Machine), two libraries for developing message-passing parallel programs on a variety of machines or networks of workstations.
Another important effort is the Cal Tech Structured Multithreaded Programming Project, led by John Thornton and K. Mani Chandy, to develop a library for doing parallel computing on SMP machines using thread libraries in C/C++ or Fortran. Thornton's s-threads library provides a higher level interface for developing data parallel programs using threads, again hiding the details of low-level thread synchronization. It has been initially developed for the Windows NT threads and for UNIX pthreads. This project has avoided Java because of the performance penalty described above. However, as Java performance improves, it would be a natural target for this type of effort. Information on this project can be found at the following URL.
At this time there are several promising projects involving the development of tools to facilitate parallel and concurrent programming in Java. We have listed sources of information on these projects. At this time, we see the most well-developed project for providing tools which can be used for teaching parallel and concurrent programming in Java to be the Java with CSP projects. We plan to explore further how these tools can be used. In addition, we will continue to gather information on the other projects listed above.