| We describe and evaluate a novel approach for the automatic parallelization of programs that use pointer-based dynamic data structures, written in Java. The approach exploits parallelism among methods by creating an asynchronous thread of execution for each method invocation in a program.; At compile time, methods are analyzed to characterize the data they access, parameterized by their context. A description of these data accesses is transmitted to a run-time system during program execution. The run-time system utilizes this description to determine when a thread may execute, and to enforce dependences among threads.; The focus of this thesis is on the run-time system. More specifically, we describe the static representation of data accesses in a method and the framework used by the run-time system to detect and enforce inter-thread dependences.; Experimental evaluation of an implementation of the run-time system on a 4-processor Sun multiprocessor indicates that close to ideal speedup can be obtained for a number of benchmarks. These results validate our approach as a viable one for automatic parallelization. |
