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:
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:
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
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
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.