| There has been considerable research during the past decade on
parallelizing compilers and automatic parallelization of programs. Traditionally, this research focused on scientific applications that consist
of loops and array references, typical of Fortran programs. Regrettably, this focus has limited the widespread use of automatic
parallelization in industry, where the majority of programs are written in C, C++, or more recently in Java. These programs extensively use pointer-based dynamic data structures such as linked lists and trees,
and often use recursion. These features make it difficult to directly utilize parallelizing compiler technology developed for array
structures and simple loops. The goal of the zJava (pronounced "zed Java'') project, at the University of Toronto, is to investigate automatic parallelization technology for programs that use pointer-based dynamic data structures and recursion, written using the Java programming language. The zJava system uses a novel combined compile-time/run-time approach to automatically exploit parallelism among methods in a Java program. For each method invocation, an independent thread is created to asynchronously execute the body of the method. Methods in the sequential program are analyzed at compile time to determine the data they access (parameterized by their context). A description of these data accesses is transmitted to a run-time system when the method is invoked during program execution. The run-time system uses this description to determine when an invoked method may execute as an independent thread. Although such an approach increases run-time overhead, it allows automatic parallelization of pointer-based programs, where compile-time-only approaches have been limited. A high-level overview of the zJava system is shown in the figure below. It consists of two main components: a compiler and a run-time system. The compiler analyzes the input sequential program to determine how shared variables and objects are used by every method in the program. The compiler captures this information in the form of symbolic access paths, and then collects these paths into a data access summary for each method. The compiler also re-structures the input program into a parallel threaded program that contains calls to routines in the run-time system, which create, execute, and synchronize threads. The run-time system receives the data access summaries for methods in a class when the class is loaded by the JVM. It stores these summaries in a set of data structures, which we refer to collectively as the registry. The run-time system contains code to compute run time data dependences among threads using the data access summaries stored in the registry. Threads are then synchronized according to these dependences.
|
