Conclusions

  In this paper, we have presented a number of transformations that can be used by a restructuring compiler to exploit some forms of implicit parallelism in Java programs. In particular, we have shown how implicit parallelism in loops and multi-way recursive methods can be made explicit by means of the multi-threading mechanism of the language. Automatically exploiting implicit parallelism simplifies the task of the programmer and makes the parallelization less error-prone. Moreover, because parallelism is expressed in Java itself, the transformed program remains portable. Speedup can be obtained on any platform that supports the true parallel execution of threads, whereas only a slight overhead is induced on uni-processors.

A series of experiments have been conducted on an IBM RS/6000 G30 to show the potential of this approach. We have illustrated the loop parallelization method in detail with some simple loop examples, and we have shown that speedups with an efficiency over can be obtained. Different scheduling policies and a wait()/notifyAll()- and busy-waiting-implementation of random synchronization were explored. Moreover, the parallelization of multi-way recursive methods has been illustrated in detail. Good speedup can be obtained for problems in which the method invocation trees are well-balanced, provided that no explicit memory allocation is performed. For methods in which each invocation requires time proportional to the remain input size (e.g. quick-sorting), speedup is limited by the initial linear terms that appear in the best parallel execution time that can be obtained using the simple parallelization method of this paper. Some load imbalancing that is inherent to using a static allocation scheme can be alleviated by increasing the cut-depth to start a few additional threads.

A prototype restructuring compiler that implements the transformations of this paper is available. More information can be found at the HP-Java home page of the Indiana University: http://www.extreme.indiana.edu/hpjava/