On the Efficiency of Parallel Backtracking.
Analytical models and experimental results concerning the average case behavior ofparallel backtracking are presented. Two types of backtrack search algorithms areconsidered: simple backtracking, which does not use heuristics to order and prunesearch, and heuristic backtracking, which does. Analytical models are used to comparethe average number of nodes visited in sequential and parallel search for each case. Forsimple backtracking, it is shown that the average speedup obtained is linear when thedistribution of solutions is uniform and superlinear when the distribution of solutions isnonuniform. For heuristic backtracking, the average speedup obtained is at least linear,and the speedup obtained on a subset of instances is superlinear. Experimental results formany synthetic and practical problems run on various parallel machines that validate thetheoretical analysis are presented.
Introduction
Consider the problem of finding a solution in a state-space tree containing one or more
solutions[10, 28, 26, 6]. Backtracking, also called Depth-first Search, is a widely used technique
for solving such problems because of its storage efficiency [13, 28]. Throughout the
paper, we use the two names interchangeably. We use the acronym DFS to denote backtracking
or depth-first search on state-space trees. There are many variants of DFS algorithms,
each of which is tuned to certain types of problems. In this paper we deal with two important
simple backtracking (which does not use any heuristic information); (ii) heuristic
backtracking (which uses ordering and/or pruning heuristics to reduce search complexity).
A number of parallel formulations of DFS have been developed by various researchers[12,
7, 22, 2, 25, 23]. In one such formulation[23], N processors concurrently perform backtracking
in disjoint parts of a state-space tree. The parts of the state-space searched by different
processors are roughly of equal sizes. But the actual parts of the search space searched
by different processors and the sequence in which nodes of these subspaces are visited are
determined dynamically; and these can be different for different executions. As a result, for
some execution sequences, the parallel version may find a solution by visiting fewer nodes
than the sequential version thus giving superlinear speedup. (The speedup is defined as the
ratio of the times taken by sequential and parallel DFS.) And for other execution sequences,
it may find a solution only after visiting more nodes thus giving sublinear speedup). This
type of behavior is common for a variety of parallel search algorithms, and is referred to
as 'speedup anomaly' [18, 19]. The superlinear speedup in isolated executions of parallel
DFS has been reported by many researchers [12, 25, 22, 7, 33, 20]. It may appear that on
the average the speedup would be either linear or sublinear; otherwise, even parallel DFS
executed on sequential processor via time-slicing would perform better than sequential DFS.
This paper considers the average case speedup anomalies in parallel DFS algorithms
that are based on the techniques developed in [23, 17]. Though simple backtracking and
heuristic backtracking algorithms we analyze here use a DFS strategy, their behavior is
very different, and they are analyzed separately. We develop abstract models for the search
spaces that are traversed by these two types of DFS algorithms. We analyze and compare
the average number of nodes visited by sequential search and parallel search in each case.
For simple backtracking, we show that the average speedup obtained is (i) linear when the
distribution of solutions is uniform and (ii) superlinear when the distribution of solutions is
non-uniform. 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 (that are
"difficult" instances) is superlinear. The theoretical analysis is validated by experimental
analysis on example problems such as the problem of generating test-patterns for digital
circuits[3], N \Gammaqueens, 15-puzzle[26], and the hackers problem[31].
The result that "parallel backtrack search gives at least a linear speedup on the average"
is important since DFS is currently the best known and practically useful algorithm to solve a
number of important problems. The occurrence of consistent superlinear speedup on certain
problems implies that the sequential DFS algorithm is suboptimal for these problems and
that parallel DFS time-sliced on one processor dominates sequential DFS. This is highly
significant because no other known search technique dominates sequential DFS for some of
these problems. We have restricted our attention in this paper to state-space search on trees,
as DFS algorithms are most effective for searching trees.
The overall speedup obtained in parallel DFS depends upon two factors: search overhead
(defined as the ratio of nodes expanded by parallel and sequential search), and communication
overhead (amount of time wasted by different processors in communication, synchro-
nization, etc. They are orthogonal in the sense that their causes are completely different.
Search overhead is caused because sequential and parallel DFS search the nodes in a different
order. Communication overhead is dependent upon the target architecture and the
load balancing technique. The communication overhead in parallel DFS was analyzed in our
previously published papers[17, 16, 4, 14], and was experimentally validated on a variety of
problems and architectures. 1 In this paper, we only analyze search overhead. However, in
the experiments, which were run only on real multiprocessors, both overheads are incurred.
Hence the overall speedup observed in experiments may be less than linear (i.e., less than N
on N processors) even if the model predicts that parallel search expands fewer nodes than
sequential search. In parallel DFS, the effect of communication overhead is less significant
for larger instances (i.e., for instances that take longer time to execute). Hence, the larger
instances for each problem obey the analyses more accurately than the smaller instances.
The reader should keep this in mind when interpreting the experimental results presented
in this paper.
In Section 2, we briefly describe the two different kinds of DFS algorithms that are
being analyzed in this paper. In Section 3, we review parallel DFS. Simple backtrack search
algorithms are analyzed in Section 4 and ordered backtrack search algorithms are analyzed
in 5. Section 6 contains related research and section 7 contains concluding remarks.
In these experiments, parallel DFS was modified to find all optimal solutions, so that the number of
nodes searched by sequential DFS and parallel DFS become equal, making search overhead to be 1.
2 Types of DFS algorithms
Consider problems that can be formulated in terms of finding a solution path in an implicit
directed state-space tree from an initial node to a goal node. The tree is generated on the
fly with the aid of a successor-generator function; given a node of the tree, this function
generates its successors. Backtracking (i.e., DFS) can be used to solve these problems as
follows. The search begins by expanding the initial node; i.e., by generating its successors.
At each later step, one of the most recently generated nodes is expanded. (In some problems,
heuristic information is used to order the successors of an expanded node. This determines
the order in which these successors will be visited by the DFS method. Heuristic information
is also used to prune some unpromising parts of a search tree. Pruned nodes are discarded
from further searching.) If this most recently generated node does not have any successors
or if it can be determined that the node will not lead to any solutions, then backtracking is
done, and a most recently generated node from the remaining (as yet unexpanded) nodes is
selected for expansion. A major advantage of DFS is that its storage requirement is linear
in the depth of the search space being searched. The following are two search methods that
use a backtrack search strategy.
1. Simple Backtracking is a depth-first search method that is used to find any one
solution and that uses no heuristics for ordering the successors of an expanded node.
Heuristics may be used to prune nodes of the search space so that search can be avoided
under these nodes.
2. Ordered Backtracking is a depth-first search method that is used to find any one
solution. It may use heuristics for ordering the successors of an expanded node. It may
also use heuristics to prune nodes of the search space so that search can be avoided
under these nodes. This method is also referred to as ordered DFS[13].
3 Parallel DFS
There are many different parallel formulations of DFS[7, 15, 19, 34, 2, 8, 23] that are suitable
for execution on asynchronous MIMD multiprocessors. The formulation discussed here is
used quite commonly [22, 23, 2, 4, 14]. In this formulation, each processor searches a disjoint
part of the search space. Whenever a processor completely searches its assigned part, it
requests a busy processor for work. The busy processor splits its remaining search space
into two pieces and gives one piece to the requesting processor. When a solution is found
by any processor, it notifies all the other processors. If the search space is finite and has no
solutions, then eventually all the processors would run out of work, and the search (sequential
or parallel) will terminate without finding any solution. In backtrack search algorithms, the
search terminates after the whole search space is exhausted (i.e., either searched or pruned).
The parallel DFS algorithms we analyze theoretically differ slightly from the above description
as follows. For simplicity, the analyses of the models assumes that an initial static
partitioning of the search space is sufficient for good load balancing. But in the parallel DFS
used in all of our experimental results, the work is partitioned dynamically. The reader will
see that there is a close agreement between our experiments and analyses.
4 Analysis of Speedup in Simple Backtracking with
Information
4.1 Assumptions and Definitions
The state-space tree has M leaf nodes, with solutions occurring only among the leaf nodes.
The amount of computation needed to visit each leaf node is the same. The execution time
of a search is proportional to the number of leaf nodes visited. This is not an unreasonable
assumption, as on search trees with branching factor greater than one, the number of nodes
visited by DFS is roughly proportional to the number of leaves visited. Also, in this section
we don't model the effect of pruning heuristic explicitly. We assume that M is the number
leaf nodes in the state-space tree that has already been pruned using the pruning function.
Both sequential and parallel DFS stop after finding one solution. In parallel DFS, the
state-space tree is equally partitioned among N processors, thus each processor gets a subtree
of with M
nodes. There is at least one solution in the entire tree (otherwise both parallel
search and sequential search would visit the entire tree without finding a solution, resulting
in linear speedup). There is no information to order the search of the state-space tree; hence
the density of solutions across the search frontier is independent of the order of the search.
Solution density ae of a leaf node is the probability of the leaf node being a solution. We
assume a Bernoulli distribution of solutions; i.e., the event of a leaf node being a solution is
independent of any other leaf node being a solution. We also assume that ae !! 1.
WN denotes the average of the total number of nodes visited by N processors before
one of the processors finds a solution. W 1 is the average number of leaf nodes visited by
sequential DFS before a solution is found. Clearly, both W 1 and WN are less than or equal
to M .
Since the execution time of a search (in the sequential as well as parallel case) is proportional
to the number of nodes expanded,
WN \Theta N
Efficiency E, is the speedup divided by N . E denotes the effective utilization of computing
resources.
WN
4.2 Efficiency Analysis
Consider the search frontier of M leaf nodes being statically divided into N regions, each
with
leaves. Let the density of solutions among the leaves in the i th region be ae i .
In the parallel case, processor i searches region i, independently until one of the processors
finds a solution. In the sequential case, the regions are arranged in a random sequence and
searched in that order.
Theorem 4.1 If ae(? 0) is the density in a region and number of leaves K in the region is
large , then mean number of leaves visited by a single processor searching the region is 1
ae .
Proof: Since we have a Bernoulli distribution,
Mean number of
For large enough K, the second term in the above becomes less than 1; hence,
Mean number of trials 'aeSequential DFS selects any one of the N regions with probability 1=N , and searches it
to find a solution. Hence the average number of leaf nodes expanded by sequential DFS is 2
ae N
2 The given expression assumes that a solution is always found in the selected region, and thus only one
region has to be searched. But with probability does not have any solution, and another
region would need to be searched. Taking this into account would make the expression for W 1 more precise,
and and increase the average value of W 1 somewhat. But the reader can verify that the overall results of
the analysis will not change.
In each step of parallel DFS, one node from each of the N regions is explored simultane-
ously. Hence the probability of success in a step of the parallel algorithm is
This is approximately ae 1 (neglecting the second order terms since ae i 's are
assumed to be small). Hence
Inspecting the above equations, we see that W
HM and
AM , where HM is
the harmonic mean of the ae 0 s; AM is their arithmetic mean. Since we know that arithmetic
mean (AM) and harmonic mean (HM) satisfy the relation : AM - HM , we have W 1 - WN .
In particular,
ffl when ae i 's are equal, When solutions are uniformly
distributed, the average speedup for parallel DFS is linear.
ffl when they are different, AM ? HM , therefore W 1 ? WN . When solution densities in
different regions are non-uniform, the average speedup for parallel DFS is superlinear.
The assumption that "the event of each node being a solution is independent of the
event of other nodes being a solution" is unlikely to be true for practical problems. Still, the
above analysis suggests that parallel DFS can obtain higher efficiency than sequential DFS
provided that solutions are not distributed uniformly in the search space, and no information
about densities in different regions is available. This characteristic happens to be true for a
variety of problem spaces searched by simple backtracking.
4.3 Experimental Results
We present experimental results of the performance of parallel DFS on three problems: (i)
the hacker's problem [31] (ii) the 15-puzzle problem[26] and (iii) the N \Gammaqueens problem[6].
In all the experiments discussed in this section, both sequential and parallel DFS visit the
newly generated successors of a node in a random order. This is different from "conventional"
DFS in which successors are visited in some statically defined "left to right" order or in
"ordered" DFS in which successors are visited in some heuristic order. We visit the successors
in a random order (rather than left-to-right or heuristic order) because we are trying to
validate our model which assumes that no heuristic information is available to order the
nodes - hence any random order is as good as any other. 3 To get the average run time, each
3 As an aside, the reader should note that the ordering information does not always improve the effectiveness
of DFS. For example, experience with the IDA* algorithm on the 15-puzzle problem [11] indicates that
experiment is repeated many times. Note that, besides the random ordering of successors,
there is another source of variability in execution time of parallel DFS. This is because the
parts of the state-space tree searched by different processors are determined dynamically, and
are highly dependent on run time events beyond programmers control. Hence, for parallel
DFS, each experiment is repeated even more frequently than it is for sequential DFS.
The hacker's problem involves searching a complete binary tree in which some of the leaf
nodes are solution nodes. The path to a solution node represents a correct password among
the various binary sequences of a fixed length. There may be more than one solution, due to
wild card notation. We implemented a program on Sequent Balance 21000 multiprocessor
and experimented with different cases for up to 16 processors. Experiments were done with
two different kinds of trees. In one case, one or more solutions are distributed uniformly in
the whole search space. This corresponds to the case in which the branching points due to
wild cards are up in the tree (more than 1 solutions) or there are no wild cards (exactly one
solution). In this case, as predicted by our analysis, sequential search and parallel search do
approximately the same amount of work, hence the speed up in Parallel DFS is linear. This
case corresponds to the curve labeled as 1 in Figure 1. The efficiency starts decreasing beyond
8 processors because communication overhead is higher for larger number of processors.
In the second case, four solutions were distributed uniformly in a small subspace of the
total space and this subspace was randomly located in the whole space. This corresponds
to the case in which branching point due to characters denoted as wild cards are low in
the tree. In this case, as expected, the efficiency of parallel DFS is greater than 1, as the
regions searched by different processors tend to have different solution densities. The results
are shown in Figure 1. The fractions indicated next to each curve denotes the size of the
subspace in which solutions are located. For example, 1means that the curve is for the case
in which solutions are located (randomly) only in 1of the space . In Figure 1, the reader
would notice that there is a peak in efficiency at r processors for the case in which solutions
are distributed in 1
r fraction of the search space (see the curves labeled 1=8 and 1=16). This
happens because it is possible for one of the r processors to receive the region containing
all or most of the solutions, thus giving it a substantially higher density region compared
with other processors. Of course, since the search space in the experiments is distributed
dynamically, this above best case happens only some of the times, and the probability of its
occurrence becomes smaller as the number of processors increases. This is why the heights
of the peaks in the successive curves for decreasing values of 1=r are also decreasing.
the use of the Manhattan distance heuristic for ordering (which is the best known admissible heuristic for
15-puzzle) does not make DFS any better. On the other hand, in problems such as N \Gammaqueens, the ordering
information improves the performance of DFS substantially[9, 32].
The experiments for 15-puzzle were performed on the BBN Butterfly parallel processor
for up to 9 processors. The experiments involved instances of the 15-puzzle with uniform
distribution and non-uniform distribution of solutions. Depth bounded DFS was used to limit
the search space for each instance. Sequential DFS and parallel DFS were both executed
with a depth-bound equal to the depth of the shallowest solution nodes. The average timings
for sequential and parallel search were obtained by running each experiment 100 times (for
every 15-puzzle instance). Figure 2 shows the average speedups obtained. The instances
with uniform distribution of solutions show a near linear speedup. The maximum deviation
of speedup is indicated by the banded region. The width of the banded region is expected
to reduce if a lot more repetitions (say a 1000 for every instance) were tried. The instances
with non-uniform distribution of solutions give superlinear speedups.

Figure

3 show the efficiency versus the number of processors for the N \Gammaqueens problem.
The problem is naturally known to exhibit non uniformity in solution density[8]. Each data
point shown was obtained by averaging over 100 trials. As we can see, parallel DFS exhibits
better efficiency than sequential DFS. As the number of processors is increased for any fixed
problem size, the efficiency goes down because the overhead for parallel execution masks the
gains due to parallel execution. We expect that on larger instances of such problems, parallel
DFS will exhibit superlinear speedup even for larger number of processors.
All of these experiments confirm the predictions of the model. Superlinear speedup occurs
in parallel DFS if the density of solutions in the regions searched by different processors are
different. Linear speedup occurs when solutions are uniformly distributed in the whole
search space, which means that solution density in regions searched by different processors
in parallel is the same.
Number of processors N
Efficiency

Figure

1: Efficiency curves for the hackers problem. An efficiency greater than 1 indicates
superlinear speedup.
Number of Processors N
S Uniform dist.
Non Uniform dist.
Single soln.

Figure

2: Speedup curves for the 15-puzzle problem.
13-queens
16-queens
22-queens
Linear Speedup
Number of processors N
Figure

3: Efficiency Curves for the N-Queens problem.
5 Speedup in Parallel Ordered Depth-First Search
5.1 Assumptions and Definitions
We are given a balanced binary tree of depth d. The tree contains 2 nodes of which 2 d
are leaf nodes. Some of the 2 are solution nodes. We find one of these solutions
by traversing the tree using (sequential or parallel) DFS. A bounding heuristic is available
that makes it unnecessary to search below a non-leaf node in either of the following two
cases:
1. It identifies a solution that can be reached from that node or even identifies the node
to be a solution.
2. It identifies that no solution exists in the subtree rooted at that node, and thus makes
it unnecessary to search below the node.
When a bounding heuristic succeeds in pruning a non-leaf node, there is no need to search
further from that node. (If a node is a non-leaf node and if the bounding heuristic does not
succeed, then the search proceeds as usual under the node.) We characterize a bounding
heuristic by its success rate (1 \Gamma -); i.e. the probability with which the procedure succeeds
in pruning a node. For the purposes of our discussion we shall assume 0:5
This ensures that the effective branching factor is greater than 1. For - 0:5, the search
complexity becomes insignificant.
Consider a balanced binary tree of depth k that has been pruned using the
bounding heuristic. Let F (k) be the number of leaf nodes in this tree. Clearly, F (k) would
be no more than than 2 k .
If our given tree has no solutions, then DFS will visit F (d) leaf nodes. If the tree has one
or more solutions, then DFS will find a solution by visiting fewer leaf nodes than F (d). The
actual number of leaf nodes visited will depend upon the location of the left most solution in
the tree, which in turn will depend upon the order in which successors of nodes are visited.
In an extreme case, if the "correct" successor of each node is visited first by DFS, then a
solution will be found by visiting exactly one leaf node (as the left most node of the search
tree will be a solution). In practice, an ordering heuristic is available that aids us in visiting
the more promising node first and postponing the visit to the inferior one (if necessary) later.
We characterize an ordering heuristic by a parameter fl. The heuristic makes the correct
choice in ordering with a probability fl; i.e., fl-fraction of the time, subtree containing a
solution is visited, and the remaining (1 \Gamma fl)-fraction of the time, subtree containing no
solution is visited. Obviously, it only makes sense to consider 0:5 means
that the heuristic provides worse information than a random coin toss. When 1:0, the
ordering is perfect and the solution is found after visiting only 1 leaf node.
We shall refer to these trees as OB-trees (ordered-bounded trees), as both ordering and
bounding information is available to reduce the search. To summarize, OB-trees model search
problems where bounding and/or ordering heuristics are available to guide the search and
their error probability is constant. The reader should be cautioned that for some problems,
this may not necessarily be true.
5.2 Efficiency Analysis
We now analyze the average number of leaf nodes visited by the sequential and parallel DFS
algorithms on OB-trees. Let S(d) be the average number of leaf nodes (pruned nodes or
terminal nodes) visited by sequential search and P (d) be the sum of the average number of
leaf nodes visited by each processor in parallel DFS.
Theorem 5.1 F
Proof: See the proof of Theorem A.1 in Appendix A.Theorem 5.2 S(d) -
See the proof of Theorem A.2 in Appendix A.Thus the use of ordering and bounding heuristics in sequential DFS cuts down the effective
size of the original search tree by a large factor. The bounding heuristic reduces the effective
branching factor from 2 to approximately 2-. The ordering heuristic reduces the overall
search effort by a factor of (1 \Gamma fl). Even though OB-trees are complete binary trees, a
backtrack algorithm that uses the pruning heuristic reduces the branching factor to less
than 2.
Now let's consider the number of nodes visited by parallel DFS. Clearly, the bounding
heuristic can be used by parallel DFS just as effectively (as it is used in sequential DFS).
However, it might appear that parallel DFS cannot make a good use of the ordering heuristic,
as only one of the processors will work on the most promising part of the space whereas
other processors will work on less promising parts. But the following theorem says that this
intuition is wrong.
Theorem 5.3 For OB-trees, parallel DFS expands no more nodes on the average than sequential
DFS.
Proof: We first consider a two processor parallel DFS and later generalize the result. In
two-processor parallel DFS, the tree is statically partitioned at the root and the processors
search two trees of depth independently until at least one of them succeeds. Each
of them individually performs the sequential DFS with the help of bounding and pruning
heuristics. Note that though the second processor violates the advice of the ordering heuristic
at the root node, it follows its advice everywhere else. Consider the case in which the root
node is not pruned by the bounding heuristic. Now there are two possible cases:
Case 1: Solution exists in the left subtree. This case happens fl-fraction of the time.
In this case, sequential DFS visits S(d \Gamma 1) leaf nodes on the average, whereas parallel DFS
visits at most 2S(d \Gamma 1) leaf nodes. If the left subtree also has a solution, then parallel
DFS visits exactly 2S(d \Gamma 1) leaf nodes on the average. Otherwise (if both subtrees have a
solution), then the average work done in parallel DFS will be smaller.
Case 2: Solution does not exist in the left subtree (i.e., it exists in the right subtree). This
case happens (1\Gammafl)-fraction of the time. In this case, sequential DFS visits F (d\Gamma1)+S(d\Gamma1)
leaf nodes on the average, whereas parallel DFS visits exactly 2S(d \Gamma 1) leaf nodes.
Thus fl-fraction of the time parallel DFS visits at most S(d \Gamma 1) extra nodes, and (1 \Gamma fl)-
fraction of the time it visits F (d nodes than sequential DFS.
Hence, on the average (ignoring the case in which solution is found at the root itself 4 ),
- 0 by Theorem A.2
This result is extended to the case where we have 2 a processors performing the parallel
search, in the following theorem.
Theorem 5.4 If P a is the number of nodes expanded in parallel search with 2 a processors,
where a ? 0, then P a - P a\Gamma1 .
Proof: This theorem compares the search efficiency when 2 a\Gamma1 processors are being used to
that when 2 a processors are being used. In the first case, the entire search tree is being split
into 2 a\Gamma1 equal parts near the root and each such part is searched by one processor. In the
4 When the root is pruned we can ignore the difference between P (d) and S(d), as the tree has only one
node.
second case, each of these is again being split into two equal parts and two processors share
the work that one processor used to do. Let us compare the number of nodes expanded by
one processor in the first case with the corresponding pair of processors in the second case.
We know that the subtree we are dealing with is an OB-tree. There fore, theorem 5.3 shows
that the pair of processors do at most as much work as the single processor in the first case.
By summing over all 2 a\Gamma1 parts in the whole tree, the theorem follows. An induction on a
with this theorem shows that P (d) - S(d) holds for the case of 2 k processors performing the
parallel search.5.2.1 Superlinear Speedup on Hard to Solve Instances
Theorem 5.3 has the following important consequence. If we partition a randomly selected
set of problem instances into two subsets such that on one subset the average speedup is
sublinear, then the average speedup on the other one will be superlinear. One such partition
is according to the correctness of ordering near the root. Let us call those instances on
which the ordering heuristic makes correct decision near the root, easy-to-solve instances
and the others, hard-to-solve instances. For sequential DFS, easy-to-solve instances take
smaller time to solve than hard-to-solve instances.
For the 2-processor case, easy-to-solve instances are those fl-fraction of the total instances
in which the ordering heuristic makes correct decisions at the root. On these, parallel version
obtains an average speedup of 1 (i.e., no speedup). On the remaining instances, the average
speedup is roughly 2\Gammafl
, which can be arbitrarily high depending upon how close fl is to 1.
On 2 a processors, the easiest to solve instances are those fl a -fraction of the total instances
on which sequential search makes correct decision on the first a branches starting at the
root. The maximum superlinearity is available on the hardest to solve instances which are a
fraction of the total instances.
5.3 Experimental Results
The problem we chose to experiment with is the test generation problem that arises in
computer aided-design (CAD) for VLSI. The problem of Automatic Test Pattern Generation
(ATPG) is to obtain a set of logical assignments to the inputs of an integrated circuit that
will distinguish between a faulty and fault-free circuit in the presence of a set of faults. An
input pattern is said to be a test for a given fault if, in the presence of the fault, it produces
an output that is different for the faulty and fault-free circuits. We studied sequential and
parallel implementations of an algorithm called PODEM (Path-Oriented Decision Making
[3]) used for combinational circuits (and for sequential circuits based on the level-sensitive
scan design approach). This is one of the most successful algorithms for the problem and
it is widely used. The number of faults possible in a circuit is proportional to the number
of signal lines in it. It is known that the sequential algorithm is able to generate tests for
more than 90% of the faults in reasonable time but spends an enormous amount of time
(much more than 90% of execution time) trying to generate tests for the remaining faults.
As a result, the execution of the algorithm is terminated when it fails to generate a test
after a predefined number of node expansions or backtracks. Those faults that cannot be
solved in reasonable time by the serial algorithm are called hard-to-detect (HTD) faults[27].
In practice, it is very important to generate tests for as many faults as possible. Higher
fault coverage results in more reliable chips. The ATPG problem fits the model we have
analyzed very well for the following reasons: (i) the search tree generated is binary; (ii) For
a non-redundant fault, the problem typically has one or a small number of solutions; (iii)
a good but imperfect ordering heuristic is available; (iv) a bounding heuristic is available
which prunes the search below a node when either the pruned node itself is a solution or it
can no longer lead to solutions.
Our experiments with the ATPG problem support our analysis that on hard-to-solve in-
stances, the parallel algorithm shows a superlinear speedup. We implemented sequential and
parallel versions of PODEM on a 128 processor Symult 2010 multiprocessor. We performed
an experiment using the ISCAS-85 benchmark files as test data. More details on our implementation
and experimental results can be found in [1]. Our experiments were conducted as
follows. The HTD faults were first filtered out by picking those faults from the seven files
whose test patterns could not be found within 25 backtracks using the sequential algorithm.
The serial and parallel PODEM algorithms were both used to find test patterns for these
HTD faults. Since some of these HTD faults may not be solvable (by the sequential and/or
parallel PODEM algorithm) in a reasonable time, an upper limit was imposed on the total
number of backtracks that a sequential or parallel algorithm could make. If the sequential or
parallel algorithm exceeded this limit (the sum of backtracks made by all processors being
counted in the parallel case), then the algorithm was aborted, and the fault was classified as
undetectable (for that backtrack limit). Time taken by purely sequential PODEM and the
parallel PODEM were used to compute the speedup. These results are shown in Figure 4
for each circuit in the ISCAS-85 benchmark. In these experiments, 25600 was used as the
upperlimit for backtracks.
To test the variation of superlinearity with hardness of faults, we selected two sets of
faults. The first set consisted of those faults that the serial algorithm was able to solve after
executing a total number of backtracks (node expansions) in the range 1600-6400. Similarly,
Number of processors
speedup
Figure

4: Speedup Curves for the ATPG problem
the second set of faults was solved by the serial algorithm in the backtrack range 6400-25600.
The faults in the second set were thus harder to solve for the serial algorithm. Two of the
seven files, namely c499 and c1355, did not yield any faults for either of the two sets. We
executed the parallel algorithm for 16 to 128 processors and averaged the speedups obtained
for a given number of processors separately for the two sets of faults. The run-time for each
fault was itself the average obtained over 10 runs. These results are shown in Figure 5.
From all these results, it is clear that superlinearity increases with the increasing hardness of
instances. The degree of superlinearity decreases with the increasing number of processors
because the efficiency of parallel DFS decreases if the problem size is fixed and the number
of processors is increased[16].
Note that the above experimental results validate only the discussion in Section 5.2.1.
To validate Theorem 5.3, it would be necessary to find the number of nodes expanded by
parallel DFS even for easy to detect faults. For such faults, experimental run time will not
be roughly proportional to the number of nodes searched by parallel DFS because for small
trees communication overhead becomes significant. Superlinearity for hard-to-detect faults
was experimentally observed for other ATPG heuristics by Patil and Banerjee in [27].
6 Related Research
The occurrence of speedup anomalies in simple backtracking was studied in [22] and [8].
Monien, et. al.[22] studied a parallel formulation of DFS for solving the satisfiability problem.
In this formulation, each processor tries to prove the satisfiability of a different subformula of
the input formula. Due to the nature of the satisfiability problem, each of these subformulas
leads to a search space with a different average density of solutions. These differing solution
densities are responsible for the average superlinear speedup. In the context of a model,
Monien et al. showed that it is possible to obtain (average) superlinear speedup for the SAT
problem. Our analysis of simple backtracking (in Section 4) is done for a similar model,
but our results are general and stronger. We had also analyzed the average case behavior
of parallel (simple) backtracking in [24]. The theoretical results we present here are much
stronger than those in [24]. In [24], we showed that if the regions searched by a few of the
processors had all the solutions uniformly distributed and the regions searched by all the
rest of the processors had no solutions at all, the average speedup in parallel backtracking
would be superlinear. Our analysis in Section 4 shows that any non-uniformity in solution
densities among the regions searched by different processors leads to a superlinear speedup
on the average. The other two types of heuristic DFS algorithms we discuss are outside the
scope of both [22] and [24].
1600-64003282251751257525Number of processors

Figure

5: Speedup curves for hard-to-solve instances of the ATPG problem
If the search space is searched in a random fashion (i.e., if newly generated successors
of a node are ordered randomly) , then the number of nodes expanded before a solution
is found is a random variable (let's call it T(1)). One very simple parallel formulation of
DFS presented in [21, 8] is to let the same search space be searched by many processors
in an independent random order until one of the processors finds a solution. The total
number of nodes expanded by a processor in this formulation is again a random variable
(let's call it T(N)). Clearly, g, where each V i is a random variable. If
the average value of T(N) is less than 1
times T(1), then also we can expect superlinear
speedup[21, 8]. For certain distributions of T(1), this happens to be the case. For example, if
the probability of finding a solution at any level of the state-space tree is the same, then
has this property[21]. Note that our parallel formulation of DFS dominates the one in [21, 8]
in terms of efficiency, as in our parallel formulation there is no duplication of work. Hence,
our parallel formulation will exhibit superlinear speedup on any search space for which the
formulation in [21, 8] exhibits superlinear speedup, but the converse is not true.
For certain problems, probabilistic algorithms[29] 5 can perform substantially better than
simple backtracking. For example, this happens for problems in which the state-space tree
is a balanced binary tree (like in the Hacker's Problem discussed in Section 4.3), and if
the overall density of solutions among the leaf nodes is relatively high but solutions are
distributed nonuniformly. Probabilistic search performs better than simple backtracking for
these problems because it can make the density of solutions at the leaf nodes look virtually
uniform. The reader can infer from the analysis in Section 4 that for these kinds of search
spaces, parallel DFS also obtains similar homogenization of solution density, even though
each processor still performs enumeration of (a part of) the search space. The domain of
applicability of the two techniques (probabilistic algorithms vs sequential or parallel DFS)
however is different. When the depth of leaf nodes in a tree varies, a probabilistic search
algorithm visits shallow nodes much more frequently than deep nodes. In the state-space
tree of many problems (such as the N \Gammaqueens problem), shallow nodes correspond to failure
nodes, and solution nodes are located deep in the tree. For such problems, probabilistic
algorithms do not perform as well as simple backtracking, as they visit failure nodes more
frequently. (Note that the simple backtracking will visit a failure node exactly once.) When
the density of solutions among leaf nodes is low, the expected running time of a probabilistic
algorithm can also be very high. (In the extreme case, when there is no solution, the
probabilistic search will never terminate, whereas simple backtracking and our parallel DFS
will.) For these cases also, an enumerative search algorithm such as simple backtracking
5 A probabilistic algorithm for state space search can be obtained by generating random walks from root
node to leaf nodes until a solution is found
is superior to a probabilistic algorithm, and the parallel variant retains the advantages of
homogenization.
For ordered DFS, randomized parallel DFS algorithms such as those given in [21, 8]
will perform poorly, they are not able to benefit from the ordering heuristics. Probabilistic
algorithms have the same weakness. For decision problems, our analysis in Section 5 shows
that the utilization of ordering heuristic cuts the search down by a large factor for both the
sequential DFS and our parallel DFS. In the case of optimization problems (i.e., when we
are interested in finding a least-cost solution), randomized parallel DFS algorithms in [21, 8]
as well as probabilistic algorithms are not useful. One cannot guarantee the optimality of a
solution unless an exhaustive search is performed.
Saletore and Kale [30] present a parallel formulation of DFS which is quite different than
the ones in [22, 23, 2]. Their formulation explicitly ensures that the number of nodes searched
by sequential and parallel formulations are nearly equal. The results of our paper do not
apply to their parallel DFS.
In [5], a general model for explaining the occurrence of superlinear speedups in a variety
of search problems is presented. It is shown that if the parallel algorithm performs less work
than the corresponding sequential algorithm, superlinear speedup is possible. In this paper,
we identified and analyzed problems for which this is indeed the case.
Conclusions
We presented analytical models and theoretical results characterizing the average case behavior
of parallel backtrack search (DFS) algorithms. We showed that on average, parallel
DFS does not show deceleration anomalies for two types of problems. We also presented
experimental results validating our claims on multiprocessors. Further, we identified certain
problem characteristics which lead to superlinear speedups in parallel DFS. For problems
with these characteristics, the parallel DFS algorithm is better than the sequential DFS algorithm
even when it is time-sliced on one processor. While isolated occurrences of speedup
anomalies in parallel DFS had been reported earlier by various researchers, no experimental
or analytical results showing possibility of superlinear speedup on the average (with the
exception of results in [22, 24]) were available for parallel DFS.
A number of questions need to be addressed by further research. On problems for which
sequential DFS is dominated by parallel DFS but not by any other search technique, what is
best possible sequential search algorithm? Is it the one derived by running parallel DFS on
one processor in a time slicing mode? If yes, then what is the optimum number of processors
to emulate in this mode? In the case of ordered backtrack search, we showed that parallel
search is more efficient on hard-to-solve instances while sequential search is more efficient
on easy-to-solve instances. In practice, one should therefore use a combination of sequential
and parallel search. What is the optimal combination? This paper analyzed efficiency
of parallel DFS for certain models. It would be interesting to perform similar analysis for
other models and also for other parallel formulations of backtrack search such as those given
in [7] and in [30].

Acknowledgements

We would like to thank Sunil Arvindam and Hang He Ng for
helping us with some of the experiments. We would also like to thank Dr. James C. Browne
and Dr Vineet Singh for many helpful discussions.
APPENDICES
A Details of Analysis for Ordered DFS Algorithms.
Theorem A.1 F
Proof. It is clear that F 1. Now consider the case when k - 0. With
the root node is pruned, and thus F 1. With the remaining - probability, the root
node is not pruned, and has 2 successors. In this case, F
Hence, we have
bounding heuristic succeeds at the root, DFS visits only one leaf; otherwise
it visits only the left subtree at the root fl fraction of the time or it visits the left subtree
unsuccessfully and then visits the right subtree fraction of the time. Hence, we have,
For d ?? 1 (a moderate d suffices) we have
Hence
Using theorem A.1 we can simplify this to
Under the previous assumption d ?? 1, the - d+1 term can be ignored. The term -
becomes negligible when - is larger than 0:5, say for - 0:55. Thus
Theorem A.3
The error ignored is small.In two-processor parallel depth-first search, the tree is statically partitioned at the root
and the processors search two trees of depth d-1 independently until at least one of them
succeeds. Each of them individually performs the sequential DFS consulting the three wise
oracles. Note that though the second processor violates the advice of the ordering heuristic
at the root node, it follows its advice everywhere else. Hence
of the time the root is pruned by prune and as a liberal convention we have two
nodes expanded in the parallel search. Otherwise, two OB-trees of depth d-1 are searched,
two nodes being expanded in each step, until one of the processors succeed.
The inequality arises because the average of the minimum of two trials is not more than
the minimum of the two averages. From the formula for S(d) we have
using theorem A.1,
where the error ignored is less than 1.
From Theorem A.1 we have
The inequality becomes an equality if we restrict that there be only one solution in the entire
search tree.
Theorem A.4 On the average parallel search visits same number of nodes as sequential
search on a large randomly selected set of problem instances, with single solutions.
Proof: See above arguments.



--R

Automatic test pattern generation on multiprocessors.

An implicit enumeration algorithm to generate tests for combinatorial logic circuits.
Experimental evaluation of load balancing techniques for the hypercube.
Modeling speedup (n) greater than n.
Fundamentals of Computer Algorithms.
A parallel searching scheme for multiprocessor systems and its application to combinatorial problems.
Randomized parallel algorithms for prolog programs and backtracking applications.
A perfect heuristic for the n non-attacking queens problem
Search in Artificial Intelligence.
Personal Communication.
The use of parallelism to implement a heuristic search.

Scalable load balancing techniques for parallel computers.
Parallel branch-and-bound formulations for and/or tree search
Scalable parallel formulations of depth-first search
Parallel depth-first search
Anomalies in parallel branch and bound algorithms.
Wah Computational efficiency of parallel approximate branch-and-bound algorithms
A shared virtual memory system for parallel computing.
Superlinear speedup through randomized algorithms.
Superlinear speedup for parallel back- tracking
Parallel depth-first search
Superlinear speedup in state-space search
A parallel implementation of iterative-deepening-a*
Principles of Artificial Intelligence.
A parallel branch-and-bound algorithm for test generation

Probabilistic algorithms.
Consistent linear speedup to a first solution in parallel state-space search
The average complexity of depth-first search with backtracking and cutoff
Efficient search techniques - an empirical study of the n-queens problem
Performance and pragmatics of an OR-parallel logic programming system

--TR
Heuristics: intelligent search strategies for computer problem solving
The average complexity of depth-first search with backtracking and cutoff
DIBMYAMPERSANDmdash;a distributed implementation of backtracking
Principles of artificial intelligence
Performance of an OR-parallel logic programming system
Parallel depth first search. Part I. implementation
Parallel depth first search. Part II. analysis
Search in Artificial Intelligence
An almost perfect heuristic for the <italic>N</italic> nonattacking queens problem
Scalable parallel formulations of depth-first search
Anomalies in parallel branch-and-bound algorithms
Fundamentals of Computer Alori
Automatic Test Pattern Generation on Multiprocessors
Superlinear Speedup in Parallel State-Space Search

--CTR
Jung , M. S. Krishnamoorthy , George Nagy , Andrew Shapira, N-Tuple Features for OCR Revisited, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.18 n.7, p.734-745, July 1996
Finkelstein , Shaul Markovitch , Ehud Rivlin, Optimal schedules for parallelizing anytime algorithms: the case of independent processes, Eighteenth national conference on Artificial intelligence, p.719-724, July 28-August 01, 2002, Edmonton, Alberta, Canada
Fumiaki Okushi, Parallel cooperative propositional theorem proving, Annals of Mathematics and Artificial Intelligence, v.26 n.1-4, p.59-85, 1999
James Cheetham , Frank Dehne , Andrew Rau-Chaplin , Ulrike Stege , Peter J. Taillon, Solving large FPT problems on coarse-grained parallel machines, Journal of Computer and System Sciences, v.67 n.4, p.691-706, December
Ariel Felner , Sarit Kraus , Richard E. Korf, KBFS: K-Best-First Search, Annals of Mathematics and Artificial Intelligence, v.39 n.1-2, p.19-39, September
Daniel J. Challou , Maria Gini , Vipin Kumar , George Karypis, Predicting the Performance of Randomized Parallel An Application to Robot Motion Planning, Journal of Intelligent and Robotic Systems, v.38 n.1, p.31-53, September
G. Karypis , V. Kumar, Unstructured tree search on SIMD parallel computers: a summary of results, Proceedings of the 1992 ACM/IEEE conference on Supercomputing, p.453-462, November 16-20, 1992, Minneapolis, Minnesota, United States
Wei-Ming Lin , Wei Xie , Bo Yang, Performance analysis for parallel solutions to generic search problems, Proceedings of the 1997 ACM symposium on Applied computing, p.422-430, April 1997, San Jose, California, United States
Andrea Di Blas , Arun Jagota , Richard Hughey, Optimizing neural networks on SIMD parallel computers, Parallel Computing, v.31 n.1, p.97-115, January 2005
G. Karypis , V. Kumar, Unstructured Tree Search on SIMD Parallel Computers, IEEE Transactions on Parallel and Distributed Systems, v.5 n.10, p.1057-1072, October 1994
Ananth Grama , Vipin Kumar, State of the Art in Parallel Search Techniques for Discrete Optimization Problems, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.28-35, January 1999
Peter A. Krauss , Andreas Ganz , Kurt J. Antreich, Distributed Test Pattern Generation for Stuck-At Faults in Sequential Circuits, Journal of Electronic Testing: Theory and Applications, v.11 n.3, p.227-245, Dec. 1997
Lucas Bordeaux , Youssef Hamadi , Lintao Zhang, Propositional Satisfiability and Constraint Programming: A comparative survey, ACM Computing Surveys (CSUR), v.38 n.4, p.12-es, 2006
parallel algorithms;index termsparallel backtracking;speedup;heuristicbacktracking;search problems;backtrack search algorithms;simple backtracking