Termination Detection

With the weak synchronization scheme between the iterations, special provision must be taken to ensure that the returned solution is optimal in the `first-solution-case'. When a goal node is found in iteration , all processors working on iterations must complete their search to prove that no better solution exists.

In the `all-solutions-case' (subject of this paper) the last iteration is searched to completion until all processors examined all their assigned subtrees. Due to the varying branching degree, the subtree sizes can hardly be estimated in advance. This results in different termination times for the parallel processors. As shown in Figures 2 and 3 (compare the two bottom graphs and ) the time spent in the finishing phase is appreciable. Note however, that this will usually not occur in the search for onesolution, a case, that is more important in practice.