ON THE EFFICIENCY OF PARALLEL BACKTRACKING

It is known that isolated executions of parallel backtrack search exhi bit speedup anomalies. In this paper we present analytical models and experimental results on the average case behavior of parallel backtrac king. We consider two types of backtrack search algorithms: 1) simple backtracking (which does not use any heuristic information); 2) heuris tic backtracking (which uses heuristics to order and prune search). We present analytical models to compare the average number of nodes visi ted in sequential and parallel search for each case. For simple backtr acking, we show that the average speedup obtained is 1) linear when di stribution of solutions is uniform and 2) superlinear when distributio n of solutions is nonuniform. For heuristic backtracking, the average speedup obtained is at least linear (i.e., either linear or superlinea r), and the speedup obtained on a subset of instances (called difficul t instances) is superlinear. We also present experimental results over many synthetic and practical problems on various parallel machines, t hat validate our theoretical analysis.