Title

On The Efficiency Of Parallel Backtracking

Keywords

Backtracking; depth-first search; parallel processing; speedup anamoly; superlinear speedup; tree search

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. © 1993 IEEE

Publication Date

1-1-1993

Publication Title

IEEE Transactions on Parallel and Distributed Systems

Volume

4

Issue

4

Number of Pages

427-437

Document Type

Article

Identifier

scopus

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/71.219757

Socpus ID

0027575096 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0027575096

This document is currently not available here.

Share

COinS