On the Efficiency of Parallel Backtracking

V. Nageshwara Rao; Vipin Kumar

doi:10.1109/71.219757

On the Efficiency of Parallel Backtracking

V. Nageshwara Rao, Vipin Kumar

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

58 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 language	English (US)
Pages (from-to)	427-437
Number of pages	11
Journal	IEEE Transactions on Parallel and Distributed Systems
Volume	4
Issue number	4
DOIs	https://doi.org/10.1109/71.219757
State	Published - 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

Publisher link

10.1109/71.219757

Find It

Find It at U of M Libraries

Cite this

@article{74e4c947609d4b46b3d4e822dcfe057a,

title = "On the Efficiency of Parallel Backtracking",

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.",

keywords = "Backtracking, depth-first search, parallel processing, speedup anamoly, superlinear speedup, tree search",

author = "Rao, {V. Nageshwara} and Vipin Kumar",

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.",

year = "1993",

month = apr,

doi = "10.1109/71.219757",

language = "English (US)",

volume = "4",

pages = "427--437",

journal = "IEEE Transactions on Parallel and Distributed Systems",

issn = "1045-9219",

publisher = "IEEE Computer Society",

number = "4",

}

TY - JOUR

T1 - On the Efficiency of Parallel Backtracking

AU - Rao, V. Nageshwara

AU - Kumar, Vipin

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

PY - 1993/4

Y1 - 1993/4

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

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

KW - Backtracking

KW - depth-first search

KW - parallel processing

KW - speedup anamoly

KW - superlinear speedup

KW - tree search

UR - http://www.scopus.com/inward/record.url?scp=0027575096&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027575096&partnerID=8YFLogxK

U2 - 10.1109/71.219757

DO - 10.1109/71.219757

M3 - Article

AN - SCOPUS:0027575096

SN - 1045-9219

VL - 4

SP - 427

EP - 437

JO - IEEE Transactions on Parallel and Distributed Systems

JF - IEEE Transactions on Parallel and Distributed Systems

IS - 4

ER -

On the Efficiency of Parallel Backtracking

Abstract

Bibliographical note

Keywords

Publisher link

Find It

Other files and links

Fingerprint

Cite this