Title :
Work-load balancing in highly parallel depth-first search
Author :
Reinefeld, A. ; Schnecke, V.
Author_Institution :
Paderborn Center for Parallel Comput., Germany
Abstract :
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
Keywords :
iterative methods; parallel algorithms; parallel machines; resource allocation; search problems; AIDA*; communication overhead; dissimilar sizes; dynamical stack-splitting; fine-grained fixed-sized work packets; global workload distribution; highly parallel depth-first search; iterative-deepening variant; massively parallel systems; parallel depth-first search; stack-splitting schemes; work packets; work-load balancing; work-load imbalances; Algorithm design and analysis; Artificial intelligence; Concurrent computing; Cost function; Current measurement; Large-scale systems; Operations research; Parallel processing; State-space methods; Tree graphs;
Conference_Titel :
Scalable High-Performance Computing Conference, 1994., Proceedings of the
Conference_Location :
Knoxville, TN
Print_ISBN :
0-8186-5680-8
DOI :
10.1109/SHPCC.1994.296719
