2002 · 35 citations · 16 references
ComputingComputer EngineeringComputer ScienceComputer ArchitectureParallel AlgorithmsParallel ComputingCommunication OverheadLoad BalancingParallel Computing SystemsParallel SearchingDepth-first SearchLoad Balancing StrategiesLoad-balanced SearchParallel Depth-first SearchParallel SearchParallel Search AlgorithmsPerformance OverheadWork Balancing
Among the various approaches for parallel depth-first search (DFS), the stack-splitting schemes are most popular. However, as shown in the paper, dynamical stack-splitting is not suitable for massively parallel systems with several hundred processors. Initial work-load imbalances and work packets of dissimilar sizes cause a high communication overhead. We compare work-load balancing strategies of two depth-first searches and propose a scheme that uses fine-grained fixed-sized work packets. In its iterative-deepening variant (named AIDA*) the global workload distribution improves from one iteration to the next. As a consequence, the communication overhead decreases with increasing search time.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
16
Depth-first iterative-deepening
Richard E. Korf · Artificial Intelligence · 1985 · 1.6K citations
Principles of artificial intelligence
John J. McDermott · Artificial Intelligence · 1980 · 820 citations