Scalability of massively parallel depth-first search
Alexander Reinefeld · DIMACS series in discrete mathematics and theoretical computer science · 1995
.We analyze and compare the scalabilityoftwo generic schemes for heuristic depth-first search on highly parallel MIMD systems. The first one employs a task attraction mechanism where the work packets are generated on demand by splitting the donor's stack. Analytical and empirical analyses showthatthisstack-splitting scheme works efficiently on parallel systems with a small communication diameter and a moderate number of processing elements. The second scheme, search-frontier splitting, also employs a task attraction mechanism, but uses pre-computed work packets taken from a search-frontier level of the tree. At the beginning, a search-frontier is generated and stored in the local memories. Then, the processors expand the subtrees of their frontier nodes, communicating only when they run out of work or a solution has been found. Empirical results obtained on a 32 \\Theta 32 = 1024 node MIMD system indicate that the search-frontier splitting scheme incurs fewer overheadsand ...