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.