In this paper we consider alternative schemes for parallelizing
combinatorial search, and examine the factors that influence the choice
of parallelization for this important class of problems.  Using
subgraph isomorphism as a representative search problem, we show how
the density of the solution space, the number of solutions desired, the
number of available processors, and the underlying architecture affect
the choice of an efficient parallelization.  Our experiments, which
span seven different shared-memory machines, eight parallelizations of
the subgraph isomorphism algorithm, and a wide range of input graphs,
show that there is no best parallelization for this problem:  relative
performance depends on each of these factors.  In particular, on some
machines and for some inputs, a sequential depth-first search of the
solution space, applying data parallelism at each node in the search
tree, performs best.  On other machines or other inputs, parallel tree
search, with no data parallelism, performs best.  In still other cases,
a hybrid solution, containing both parallel tree search and data
parallelism works best.  From these experiences we conclude that
multiple parallelizations of a single algorithm may be needed to
achieve the best performance over a range of machines, inputs, and
problem demands, and that hybrid forms of parallelization (where data
parallelism and tree parallelism are used in tandem) are needed in some
applications.