It is known that isolated executions of parallel backtrack search exhibit speedup anomalies. In this paper we present analytical models and experimental results on the average case behavior of parallel backtracking. We consider two types of backtrack search algorithms: 1) simple backtracking (which does not use any heuristic information); 2) heuristic backtracking (which uses heuristics to order and prune search). We present analytical models to compare the average number of nodes visited in sequential and parallel search for each case. For simple backtracking, we show that the average speedup obtained is 1) linear when distribution of solutions is uniform and 2) superlinear when distribution of solutions is nonuniform. For heuristic backtracking, the average speedup obtained is at least linear (i.e., either linear or superlinear), and the speedup obtained on a subset of instances (called difficult instances) is superlinear. We also present experimental results over many synthetic and practical problems on various parallel machines, that validate our theoretical analysis.
|Original language||English (US)|
|Number of pages||11|
|Journal||IEEE Transactions on Parallel and Distributed Systems|
|State||Published - Apr 1993|
Bibliographical noteFunding Information:
Manuscript received October 1, 1990; revised August 15, 1991. This work was supported by Army Research Office Grant DAAG29-84-K-0060 to the Artificial Intelligence Laboratory, University of Texas at Austin and by Army Research Office Grant 28408-MA-SDI to the University of Minnesota and by the Army High Performance Computing Research Center at the University of Minnesota. V. N. Rao is with the Department of Computer Sciences, University of Central Florida, Orlando, FL 32816. V. Kumar is with the Computer Science Department, University of Minnesota, Minneapolis, MN 55455. IEEE Log Number 9206270.
- depth-first search
- parallel processing
- speedup anamoly
- superlinear speedup
- tree search