On The Efficiency Of Parallel Backtracking

    Authors

    V. N. Rao;V. Kumar

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    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.

    Journal 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