On the Efficiency of Parallel Backtracking

V. Nageshwara Rao, Vipin Kumar

Research output: Contribution to journalArticlepeer-review

55 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)427-437
Number of pages11
JournalIEEE Transactions on Parallel and Distributed Systems
Volume4
Issue number4
DOIs
StatePublished - Apr 1993

Bibliographical note

Funding 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.

Keywords

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

Fingerprint

Dive into the research topics of 'On the Efficiency of Parallel Backtracking'. Together they form a unique fingerprint.

Cite this