Parallel Multi-way Recursive Methods

  We refer to a non-private, un-synchronized, and final method (i.e. overriding or hiding is not possible) of the following form, where the different recursive method invocations in between executing pre_code and post_code can be done in parallel as a parallel multi-way recursive method:

 

Here, each targeti either denotes `MyClass' if myMethod() is a class method, or an arbitrary variable of type MyClass (including this) otherwise. If myMethod() is a void-method, there are no assignments to the different ri. Algorithms that traverse an explicit tree-like data structure or divide-and-conquer algorithms can usually be expressed in this form. Because in both cases, a virtual tree of method invocations is traversed, we will visualize the parallelization of such methods using trees.

The most straightforward way to exploit implicit parallelism in a parallel n-way recursive method is to let a running thread assign all but one of the recursive method invocations to other threads [16, 18, 31, 32]. Although our method is based on this simple approach, the analysis shown below reveals the limitation on the corresponding speed-up, and better ways of parallelizing an algorithm may exist. If n=2, for example, and each invocation divides the input into two sets of (roughly) the same size in time proportional to the remaining input size, then this approach changes the serial execution time into the parallel execution time using p=N processors, as implied by the following recurrence relations (with for handling the base-case):

Hence, in this case the best possible speedup is . Similar analysis reveals that for 2-way recursive methods in which executing pre_code and post_code takes constant time, the best possible speedup using the simple parallelization method sketched above is .

The easiest way to assign work to a limited number of processors is to let running threads assign method invocations to other threads only in the top levels of the method invocation tree. Forking and eventually joining new threads in only the top two levels of the method invocation tree, for example, assigns the method invocations of a 2-way recursive to four processors, as illustrated in figure 5.

  
Figure 5: Static Allocation

Although such a static allocation scheme may yield poor performance if the sub-trees assigned to the different processors substantially vary in size, in this paper we simply rely on the fact that most multi-way recursive methods try to keep the method invocation tree reasonably balanced. Moreover, we will show that some load imbalancing can be alleviated by starting additional threads.