Termination Detection

Some parallel applications, such as search problems, invokes a large number of threads, where termination detection of all the threads is a difficult problem because there is no global control. Several algorithms (cf. [9,14]) have been proposed to solve this problem. However, when we incorporate a termination detection algorithm into a naively written parallel program, we often have to modify the structure of the original program, such as adding parameters to each function definition and invocation, sending control messages to the other objects, etc. In addition, using a different termination detection algorithm requires different modification, which results in loss of portability. To cope with this problem, we provide new language constructs fork and fork/wait for termination detection, and termination detection algorithms that are implemented at the meta-level. Special forms fork and fork/wait are similar to the asynchronous invocation form future, except that they detect global termination. The form fork/wait invokes a specified method or function, and waits for the termination of all subsequent sibling computations invoked with fork (Figure 5).

  

Figure 5: fork/wait and fork for termination detection

For example, Figure 6 is a n-queens problem using this termination detection support. The annotation at the first line declares that a termination detection algorithm called weight will be used. The top-level caller invokes function n-queens using the fork/wait form. Subsequent recursive n-queens invocations are achieved with the fork form. The top-level caller waits for the termination of all sibling n-queens computations. Note that the definition of n-queens is independent of the underlying termination detection algorithms.

  

Figure 6: Description of n-queens problem using fork and fork/wait

8#8