Title

On The Efficiency Of Parallel Backtracking

Title - Alternative

IEEE Trans. Parallel Distrib. Syst.

Keywords

Backtracking; Depth-1St Search; Parallel Processing; Speedup Anomoly; Superlinear Speedup; Tree Search; Generation; Algorithm; Branch; Computer Science, Theory & Methods; Engineering, Electrical & Electronic

Abstract

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.

Publication Title

Ieee Transactions on Parallel and Distributed Systems

Volume

4

Issue/Number

4

Publication Date

1-1-1993

Document Type

Article

Language

English

First Page

427

Last Page

437

WOS Identifier

WOS:A1993LH40500006

ISSN

1045-9219

Share

COinS