We compared the performance of two parallel DFS schemes. The stack-splittingscheme employs dynamical work-load balancing right from the beginning of the search, which results in high communication overheads and initial processor idle times. Recursive splitting of the work packets generates successively smaller packets that might be too small to justify shipment to another processor. In its iterative-deepening version (PIDA*) the communication overhead increases with increasing search time.
In our parallel fixed-packet DFSthe processors start with an equal work distribution that has been generated by a redundant breadth-first search of the first few tree levels on all processors. Later on, work packets of fixed sizes are shipped to idle processors on demand.
In its iterative-deepening variant the fixed-packet DFS, named AIDA*, automatically improves the global load balance by changing ownership of the transferred work packets. As a result, the communication overhead decreases from iteration to iteration.
Unlike PIDA*, AIDA* is portable in the sense that existing sequential search routines can be linked to AIDA*'s communication routines for implementation on a large scale MIMD system.