next up previous
Next: Construction of a new Up: Actual Parallelization Previous: Construction of the Tree-Worker

Modification of the Method

  Subsequently, myMethod() is converted into another method myMethod_par_x() that takes an additional integer parameter d_x:

tabular445

The method-body is modified as follows. First, all invocations that appear in the method-body are renamed accordingly, and the expression `d_x+1' is added as an initial parameter. Moreover, the first n-1 recursive method invocations of the n subsequent invocations that can be executed in parallel are rewritten into the following form, where CUT_DEPTH denotes some literal integer constant selected by the compiler:

tabular454

Here, the actual parameter targeti is omitted in case myMethod_x() is a class method, and `ri =' is omitted in the else-branch if myMethod() is a void-method.

For each such rewriting, the following construct is generated before the post_code fragment to implement the appropriate synchronization. The assignment statement is omitted for a void-method:

tabular464

If ri is a local variable, it may be necessary to add a dummy assignment to the declaration of this variable to preserve the definite assignment property of Java [12], because the original assignment has been moved into two conditional statements.

After these transformations have been applied to an n-way recursive method, n-way forks will be performed in the top levels tex2html_wrap_inline2418 of the method invocation tree in case CUT_DEPTH=c. In the other levels, each separate thread continues to execute method invocations in a serial fashion (at this stage, the overhead of passing d_x can be reduced by executing an unaltered copy of the original method). Hence, if p processors are available to execute a parallel n-way recursive method, then c should be at least tex2html_wrap_inline2428 to obtain sufficient threads. Using a slightly larger cut-depth, however, may be useful to alleviate load imbalancing problems. Threads eventually join with their originating threads, until the single thread that invoked the parallel recursive method remains. Note that the join is also required in case the code fragment post_code is empty to enforce the appropriate synchronization before the method as a whole terminates.


next up previous
Next: Construction of a new Up: Actual Parallelization Previous: Construction of the Tree-Worker

ajcbik@extreme.indiana.edu