Chris Nevison

Stephen Hartley

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:

• a powerful object-oriented language
• strong typing
• many compiler and run-time checks
• no pointers
• automatic garbage collection
• graphics library

Two particular strengths of Java for parallel and concurrent computing are that

• multi-threading is an integral part of the language
• the language is designed to facilitate networking

However, one of the key objectives of parallel computing is high performance. Consequently, there are some disadvantages to the use of Java:

• Java is interpreted and therefore slower than compiled languages
• support for multi-threading of a shared memory multi-processor is platform specific and is just beginning to appear
• multi-threading synchronization in Java is surprisingly tricky to use

The following recent comments underscore the importance of the last point:

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:

• calling a method is conceptually equivalent to placing the methods arguments into a message and sending the message to the called method's object

• A process is like an active object that has one or more threads encapsulated inside it and has its own private address space

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

• Design combinations for method invocation / message passing (channels):

• One Java virtual machine executes on a shared-memory multiprocessor or in DSM (distributed shared memory) on a distributed memory multicomputer, transparent to the programmer
• The supporting underlying OS implements the channels in shared memory or distributed memory, transparent to the programmer

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.

http://www.cs.ukc.ac.uk/projects/ofa/jcsp/

http://www.rt.el.utwente.nl/javapp/

http://www.cs.bris.ac.uk/~alan/javapp.html

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.

http://mpi.mpi-softtech.com/publications/JMPI_121797.html

http://www.ispras.ru/~dpj/

http://sbir.er.doe.gov/sbir/cycle15/phase1/abstract/70.htm

http://www.isye.gatech.edu/chmsr/jPVM/

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.

http://threads.cs.caltech.edu/

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.